Материал: Основы математического моделирования. курс лекций. Перова А.В

4.Анализ оценок.

4.1.Если j 0 j 1,n, то получено оптималь-

ное решение.

4.2. Если существует хотя бы одна оценка j > 0 , для

которой aij 0 i 1,m, то целевая функция не ограничена

снизу на множестве допустимых решений (ЗЛП не имеет решения).

4.3.Из всех оценок j > 0 выбирается максимальная:

k max j j : j 0

Переменная xk, которой соответствует максимальная оценка, становится на текущей итерации базисной, а k-й столбец объявляется ведущим тсолбцом.

5. Определение ведущей строки. Для этого находятся отношение правых частей ограничений к положительным элементам ведущего столбца и среди них выбирается минимальное:

i : a ik 0

S-я строка объявляется ведущей строкой. Элемент, находящийся в симплекс-таблице на пересечении s-й строки и k-го столбца ask, называется ведущим элементом.

6. Пересчет элементов симплекс-таблицы. При этом элементы ведущей строки as1,…, asn, bs делятся на ведущий элемент ask. Пересчет остальных элементов осуществляется по

Пусть ask – ведущий элемент. Элемент aij – пересчитывается следующим образом:

70

7. Переход к шагу 3 Оптимальное решение определяется следующим обра-

зом: базисные переменные приравниваются соответствующим правым частям, остальные нулю.

Пример 3 Решить задачу определения производственного плана, представленную в примере 1.

В примере 1 была построена математическая модель данной задачи. Приведем ее к канонической форме:

F=-7x1-3x2-6x3-12x4 min; 3x1+x2+2x3+4x4 +x5 =440; x1+8x2+6x3+2x4+x6 =200; x1+4x2+7x3+2x4 +x7 =320;

xj 0, j=1.7.

Базисными переменными в данном случае будут пере-

менные x1,x5,x6 .

Решение задачи иллюстрируется симплексной табл. 6.

71

Так как после третьей итерации все оценки j 0, получено оптимальное решение. Оптимальный план имеет следующий вид:

x1*=40; x2*=0; x3*=0; x4*=80; x5*=0; x6*=0; x7*=120; F*=1240.

Таким образом, для того, чтобы прибыль от производства всей продукции была максимальна при имеющихся ограниченных ресурсах, необходимо выпустить 40 единиц продукции 1-го вида и 80 единиц продукции 4-го вида. Продукция 2- го и 3-го видов при этом не выпускается. Прибыль при этом равна 1240.

Так как значения дополнительных переменных в полученном оптимальном решении x5*=0 и x6*=0, то первое и второе ограничения выполняются при этом как строгие равенства, следовательно, трудовые ресурсы и сырье полностью используются при производстве продукции. Финансовые ресурсы при производстве продукции используются не полностью (имеется запас в 120 единиц).

Как было указано выше, решение ЗЛП симплексным методом начинается с указания какого-либо первоначального опорного плана. Для ЗЛП, записанной в канонической форме, можно непосредственно указать опорный план, если среди векторов Aj, компонентами которых служат коэффициенты при переменных в системе ограничений данной задачи, есть m единичных (т.е., имеются m базисных переменных). Однако для многих ЗЛП, записанных в канонической форме, не всегда можно сразу определить опорный план. Рассмотрим задачу. В данном случае к каждому i-му уравнению системы ограничений добавляется неотрицательная переменная xn+i , называемая искусственной переменной. Так как введение искусственных переменных, в отличие от дополнительных, меняет множество решений задачи, то они вводятся также и в выражение для целевой функции с очень большим коэффициентом M > 0 (тогда в процессе решения задачи минимизации искусственные переменные будут стремиться к нулю).

72

В результате получается задача, называемая расширенной по отношению к исходной:

j 1

x j 0 , j 1, n m .

В результате может быть указан первоначальный опорный план. Искусственные переменные приравниваются к правым частям (xn+i=bi), остальные – нулю (x j 0 j 1, n ). То-

гда целевая функция примет вид:

n m

F c jx j M bi min ,

а оценки j в данном случае будут складываться из двух частей, одна из которых зависит от М, а другая не зависит:

m m

j c i a ij c j M a ij c j . j 1 i 1

Исходные данные расширенной задачи заносят в сим- плекс-таблицу, которая содержит на строку больше, чем

73

обычная. В последнюю, (m + 2)-ю строку оценок таблицы записывают коэффициенты при M, а в (m + 1)-ю - слагаемые, не содержащие M.

Так как знак j определяется знаком коэффициента, стоящего при M, ведущий столбец (и соответственно базисную переменную) выбирают по наибольшему положительному элементу (m + 2)-й строки таблицы. Пересчет симплекстаблицы при переходе от одного опорного плана к другому производят по общим правилам симплексного метода. Итерационный процесс по (m + 2)-й строке ведут до тех пор, пока

1)либо все искусственные переменные не будут исключены из базиса;

2)либо не все искусственные переменные будут исключены, но (m + 2)-я строка не содержит больше положительных элементов.

Впервом случае полученное базисное решение соответствует некоторому опорному плану исходной задачи, (m+2)-я строка таблицы вычеркивается и решение задачи продолжают обычным симплексными методом. Во втором случае, если элемент, стоящий в (m + 2)-й строке столбца B положителен, задача не имеет решения, если он равен нулю, то базис содержит по крайней мере один из векторов искусственного базиса.

Если в процессе решения задачи какая-либо искусственная переменная выводится из базиса, то соответствующий столбец симплекс-таблицы можно вычеркнуть и не пересчитывать (т.к. эту переменную не имеет смысла вводить ни в один из последующих базисов).

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

Пример 4. Решить задачу о диете, представленную в примере 2.

В примере 2 была построена математическая модель данной задачи. Приведем ее к канонической форме, при этом для упрощения расчетов второе ограничение разделим на 2:

F=6x1+x2+x3 min;

74