Скачать:  mod-laba-1.zip [34,79 Kb] (cкачиваний: 13)

Кафедра АИТ

Лабораторная работа №1

по дисциплине: «Моделирование систем и моделей»

на тему: «Линейное программирование»

Теоретическая часть

Постановка задачи линейного программирования

В задачах линейного программирования критерий оптимальности

(1)

где С – заданный коэффициент, который может быть отрицательным и положительным.

Выражение (1) называют линейной формой.

На любой процесс накладываются ограничения, которые могут быть заданы в виде неравенств или в смешанном виде.

Систему ограничений в общем виде можно записать следующим образом:

(2)

a₁₁…a_mn – могут быть как отрицательными, так и положительными;

b₁…b_m– только положительные.

Если x₁…x_n рассматриваем как параметры какого-либо технологического процесса, то они должны быть неотрицательными:

Если ограничение задано в виде неравенства, то его необходимо преобразовать в равенство, путем добавления ещё одной переменной х_n+1. Эта переменная называется выравнивающей или балансовой.

Например, для неравенства (1) из системы (2) можем записать:

Для выражения (2) в системе (2) можно записать:

Предположим, что необходимо определить наибольшее или наименьшее значение линейной функции вида

a₀…a_n – постоянные коэффициенты;

х – факторы.

Область допустимых значений независимых переменных на плоскости является многоугольником, ограниченным прямыми, уравнения которых задаются ограничениями на переменные х₁, х₂, например системой (2).

Для каждой точки плоскости функция l принимает некоторые значения l=l₁. Множество всех таких точек образуют прямую , перпендикулярную вектору k (k₁, k₂), выходящему из начала координат. Если эту прямую перемещать параллельно самой себе в положительном направлении, то функция будет возрастать, а в противоположном направлении – убывать.

Предположим, что при движении прямой l или l₁, направление вектора k, прямая пересекает вершину некоторого многоугольника. В этом случае она будет опорной, и может принимать наибольшее или наименьшее значение.

При дальнейшем перемещении прямая пересечет другую вершину многоугольника и будет называться опорной прямой l.

Из всех возможных оптимальных вариантов выбираем наибольшее или наименьшее.

Рассмотрим аналитический метод.

Для аналитического метода система ограничений задается в таком же виде как система (2) в виде равенств или неравенств. Среди неотрицательных решений системы необходимо найти такое, которое максимизировала или минимизировала линейную функцию следующего вида:

n – число аргументов или факторов.

Алгоритм решения состоит из следующих этапов:

1. необходимо убедиться в совместимости системы линейных уравнений. Для этого определим ранг системы и ранг расширенной матрицы. В случае равенства двух рангов система имеет общее решение. Работа симплекс метода начинается с выбора так называемого опорного решения, которое содержит r базисных переменных и (n-r) свободных переменных. Число базисных переменных определяем по рангу.

2. необходимо выразить базисные переменные x₁, x₂…x_r через свободные. В результате система (2) может быть преобразована к следующему виду:

(3)

Затем целевую функцию необходимо выразить через свободные переменные, то есть если подставить в линейную форму l вместо базисных переменных их выражения через свободные переменные из системы (3), то получим выражение следующего вида:

Систему (3) называют системой, приведенной к единичному базису.

3. принимая все свободные переменные равными 0, найдем значение базисных переменных:

Таким образом, получаем первое решение системы: .

Это решение системы можно назвать допустимым. Полученные значения аргументов подставляем в линейную формуl и получаем первое базисное значение линейной формы: .

В случае, если необходимо найти минимум целевой функции, из всех переменных необходимо выбрать переменную с максимальным по модулю отрицательным коэффициентом.

При переходе к новому опорному решению наиболее значимую переменную включают в число базисных, а другая переменная переходит в число свободных. Таким образом, далее меняем одну из свободных переменных с таким расчетом, чтобы значение целевой функции l уменьшалась при решении задачи минимума или же увеличивалась при нахождении максимума. Критерием окончания поиска минимума являются положительные значения коэффициентов.

РАСЧЕТНАЯ ЧАСТЬ

Максимизировать линейную форму вида при заданных ограничениях

1. Определим, имеет ли система общее решение. Для этого определим ранг расширенной и обычнрй матрицы:

= 2

= 2

2. Так как обе матрицы равны, система совместна. Так как ранг равен 2, то число базисных переменных также равно 2. Примем за базисные переменные х₃, х₄, а за свободные – х₁, х₂.

3. Найдем первое допустимое решение: (0, 0, 1, 1)

Так как коэффициенты в целевой функции для х₁ и х₂ не отрицательные, то данное решение не является оптимальным. Продолжаем поиск.

Определим до какого значения можно увеличивать х₁:

подставим в систему

х₁ увеличиваем до 0,5, так как при этом условие переменные будут неотрицательные, но при этом х₃ = 0. Следовательно, теперь х₁ является базисной, а х₃– свободной. Переходим к новому решению:

Так как коэффициент в целевой функции для х₂ не отрицательный, то данное решение не является оптимальным. Продолжаем поиск.

Определим до какого значения можно увеличивать х_2:

подставим в систему:

х₂ увеличиваем до , так как при этом условие переменные будут неотрицательные, но при этом х₄ = 0. Следовательно, теперь х₂ является базисной, а х₄ – свободной. Переходим к новому решению.

Видим, что значение целевой функции R увеличилось, коэффициенты в R отрицательные, следовательно, дальнейшее увеличение целевой функции невозможно. Таким образом, являются оптимальными значениями, обеспечивающими максимальное значение целевой функции .

Графический метод

2x₁+x₂<1

x₁+2x₂<1

x₁>0,x2</sub>>0</sub>

x₂

1

1/2

1/2 1 x₁