Математическая экономика

вующим значениям из столбца β. Искомое наименьшее значение целевой функции yinf = γ0 . Заметим, что при отыскании наибольшего значения

ЦФ искомому решению будет соответствовать симплекс-таблица, в которой все коэффициенты γ1,..., γm положительны. Если среди коэффициен-

тов γ1,..., γm в строке для y имеется хотя бы один неотрицательный, то следует преобразовать таблицу. Для этого нужно:

1)выделить столбец, содержащий такой коэффициент (если их несколько, то выбирают наибольший по модулю); этот столбец называют

разрешающим;

2)анализируя коэффициенты α, стоящие в этом столбце, выделить из них положительные и вычислить отношения β/ α в соответствующих

строках; строку, для которой это отношение минимально, называют раз-

решающей;

3) выделить элемент αks , стоящий в разрешающей строке и разре-

шающем столбце; его называют разрешающим (или генеральным, или ведущим);

4)в клетке, содержащей разрешающий элемент, в правом нижнем углу записать величину, обратную ему, т.е. λ =1/ αks ;

5)все остальные элементы разрешающей строки умножить на λ, и результат записать в нижней части тех же клеток;

6)все элементы разрешающего столбца (кроме αks ) умножить на

( −λ) и результат записать в нижней части тех же клеток;

7)выделить (подчеркнуть или обвести рамкой) в разрешающей строке верхние числа, а в разрешающем столбце – все нижние числа (за исключением разрешающего элемента);

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

9)переписать таблицу, заменив:

– “бывшую” свободную переменную на базисную и наоборот

( xs ↔ xk );

–элементы разрешающей строки и столбца – числами, записанными

внижние части тех же клеток;

–каждый из остальных элементов – суммой чисел, стоящих в верх-

них и нижних частях тех же клеток.

Пример. Найти xi ≥ 0 , при которых y =10 + x1 − 2x2 + 4x3 принимает

наименьшее значение и выполняются условия:

x1 + 3x2 − x3 + x4 =9; − x1 − 2x2 + x3 + x6 =5;

− 2x1 + 6x2 −3x3 + x5 = 6; − 2x1 + x2 − 4x3 + x7 =3.

41

Решение. Представим систему уравнений в виде:

x4 =9 − x1 −3x2 + x3; x6 =5 + x1 + 2x2 − x3; x5 = 6 + 2x1 − 6x2 + 3x3; x7 =3 + 2x1 − x2 + 4x3.

Тем самым переменные x1,..., x7 разделены на свободные ( x1, x2 , x3) и базисные ( x4 , x5, x6 , x7 ). Отметим, что это разбиение соответствует начальному плану, так как все свободные коэффициенты в полученной системе положительны.

Эту систему уравнений и выражение для ЦФ представляем в виде табл. 2.2. В ней выделяем ведущий столбец, соответствующий положительному коэффициенту в выражении для y. Этот столбец соответствует переменной x2 . Находим для элементов этого столбца отношение β/ α и выбираем наименьшее из них. Получаем ведущую строку, соответствующую переменной x5 . Заполняем части клеток таблицы по описанному выше алгоритму и переходим к новой табл. 2.3, в которой x2 и x5 поменялись местами, элементы разрешающей строки и столбца заменены нижними числами тех же клеток, а остальные элементы получены как сумма верхних и нижних чисел.

В полученной табл. 2.3 все коэффициенты при переменных xi в строке для y отрицательны. Это означает оптимальность решения, соответ-

ствующего табл. 2.3: x1 = x3 = x5 = 0, x4 = 6, x2 =1, x6 = 7, x7 = 2 , yinf =8.

42

§ 2.4. Отыскание начального опорного решения методом искусственного базиса

Для использования симплекс-метода при решении КЗЛП нужно из переменных x1,..., xn какие-либо m переменных выбрать в качестве базис-

ных, а затем уравнения системы представить в виде (2.31), причем свободные члены β в получаемых выражениях должны быть неотрицательны.

Такое представление соответствует некоторому опорному плану, который можно использовать в качестве начального для симплекс-метода. Для его отыскания можно применить метод искусственных переменных, реализуемый в одной из двух возможных модификаций [1, 3, 32].

М-метод (метод штрафов)

Поясним его сущность на следующем примере. Найти наименьшее

В этой задаче m = 2; n = 4; (n – m) = 2. Отметим, что данную систему легко разрешить относительно x3, x4 :

x3 = −2 + x1 + x2 ; x4 = 6 − 2x1 − x2 ,

но получаемое опорное решение ( x1 = 0, x2 = 0, x3 = −2, x4 = 4 ) оказывается недопустимым, так как x3 < 0 .

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

и, следовательно, для (2.39) и (2.40) можно непосредственно использовать

43

Заключительной таблице, в которой все коэффициенты при переменных в строке для ~y отрицательны, соответствует искомое оптимальное

решение, в котором все вспомогательные переменные оказались равными

44

нулю, а остальные переменные принимают значения хi = 0; x2 = 6; x3 = 4; x4 = 0, образующие решение исходной задачи.

Двухэтапный метод

При реализации рассмотренного выше М-метода на ЦВМ необходимо задать и ввести в программу некоторое конкретное большое число, например М = 100 000. При этом вклад коэффициентов исходной целевой функции, например, 1 и 3 в коэффициенты, определяющие вспомогательную функцию ~y , например 2М + 1 = 200 001 и 2М + 3 = 200 003, будет

мал. В таком случае из-за ошибок округления, возникающих при использовании ЦВМ, процесс вычислений может оказаться нечувствительным к значениям исходных коэффициентов, что может привести к ошибочным результатам [32]. Этих трудностей можно избежать, используя ту же идею искусственного базиса, но решая задачу в два этапа.

На первом этапе систему ограничений-равенств с введенными вспомогательными переменными ~xi рассматривают совместно с целевой функ-

цией ~y , равной сумме всех вспомогательных переменных. Если в результате решения этой задачи получается наименьшее значение ~y = 0 и, следо-

~

вательно, все xi = 0, то исходная задача имеет допустимое решение. Получаемое при этом распределение основных переменных xi на свободные и

базисные соответствует некоторому опорному плану.

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

На 1-м этапе нужно решить задачу об отыскании наименьшего зна-

преобразований этой таблицы представлены в табл. 2.8 – 2.10. Полученное в табл. 2.10 минимальное значение ~y оказалось равным нулю, что означает наличие допустимого решения исходной задачи. При этом мы получили распределение переменных на базисные x1, x3 и свободные x2 , x4 . Связь между ними определяется табл. 2.11, в которой вспомогательные переменные удалены, а исходная функция y соответствующей подстановкой выра-

45

жена через x2 , x4 . Применяя к ней симплекс-преобразования, получаем результат, представленный в табл. 2.12. Он совпадает с решением, полученным выше с помощью М-метода.

1-й этап

2-й этап

Следует отметить, что количество необходимых итераций М-метода и двухэтапного метода всегда одинаково [32] .

46

§ 2.5. Двойственные задачи линейного программирования

Рассмотрим две связанные между собой задачи ЛП.

Задача 1. Найти n переменных xi ≥ 0 (i =1,2,...n), при которых ЦФ

принимает наибольшее значение и выполняются m условий-ограничений:

принимает наименьшее значение и выполняются n условий-ограничений:

Указанные задачи образуют так называемую двойственную пару. При этом вторая задача называется двойственной по отношению к исходной (прямой) задаче. Она формулируется согласно следующим правилам.

1. Число переменных ui в двойственной задаче (ДЗ) равно числу ог-

раничений (2.43) в прямой задаче (ПЗ). Число ограничений (2.45) в ДЗ равно числу переменных в ПЗ.

2. Коэффициенты при неизвестных в ЦФ исходной задачи являются правыми частями неравенств-ограничений (2.45) ДЗ, а правые части системы неравенств исходной задачи входят в качестве коэффициентов в це-

страняться не на все переменные, а в систему ограничений (2.43) могут

47

входить как неравенства, так и строгие равенства. Это отражается на формулировке двойственной задачи следующим образом. Если xi ≥ 0 , то i-е

условие в системе (2.45), входящей в двойственную задачу, является неравенством вида "≥". Если же xi может принимать любые значения, то i-е

соотношение в (2.45) представляет собой равенство. Если j-е ограничение в исходной задаче является неравенством "≤", то в двойственной задаче u j ≥ 0 . В противном случае u j может принимать любые значения [1].

Между решением прямой и двойственной задач существует тесная связь, которая проявляется, в частности, в следующем.

1. Если одна из пары двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем

y* = max [ y(x)] = z* = min[z(u )].

Если же x – произвольный допустимый план исходной задачи, а y –

произвольный план двойственной задачи, то y(x) ≤ z(u ).

2. Если одна из пары двойственных задач не имеет решения из-за того, что ЦФ не ограничена (для исходной задачи – сверху и для двойственной – снизу), то другая задача тоже не имеет решения из-за отсутствия допустимых решений.

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

Пусть исходная задача решена симплекс-методом, для чего она предварительно сведена к канонической форме, а затем для нее найден допустимый опорный план, по которому составлена начальная симплекстаблица, например табл. 2.13. Выполняя соответствующие симплекс-

48

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

Для получения решения двойственной задачи необходимо:

–составить список переменных xi , которые вошли как базисные в конечную симплекс-таблицу; для рассматриваемого примера это [x4 , x5, x1];

–записать строку коэффициентов при этих переменных в исходной

ЦФ, фигурирующей в начальной симплекс-таблице dT =[5 0 3] (если некоторой переменной, например x5 , не оказалось среди свободных пере-

менных, определяющих ЦФ в начальной таблице, то соответствующий коэффициент в указанной строке принимается равным нулю);

–составить список переменных, которые вошли как базисные в начальную симплекс-таблицу, в рассматриваемом случае [x2, x5, x6];

–для каждой из этих m переменных записать столбец из m чисел по следующему правилу: если эта переменная в конечной таблице оказалась свободной переменной, то нужно выписать соответствующий ей столбец из этой таблицы; если же переменная (в данном примере x5 ) оказалась в

конечной таблице в списке базисных, то записывается столбец, в котором в строке, соответствующей этой базисной переменной, проставляется 1, а остальные позиции заполняются нулями; в результате получается квадратная матрица

49

– искомое решение двойственной задачи получается перемножением строки d Т и матрицы Q:

Пример. Исходная задача состоит в отыскании переменных x1 ≥ 0 и x2 ≥ 0, при которых ЦФ y = 2x1 + 7x2 принимает наибольшее значение, и выполняются условия: −2x1 +3x2 ≤14; x1 + x2 ≤8 . Необходимо сформу-

лировать и решить двойственную для нее задачу.

Решение

ДЗ будет состоять в отыскании значений u1 ≥ 0, u2 ≥ 0 , при которых ЦФ z =14u1 + 8u2 принимает наименьшее значение и выполняются усло-

вия − 2u1 + u2 ≥ 2; 3u1 + u2 ≥ 7 .

Отметим, что в рассматриваемой двойственной паре n = m = 2, поэтому обе задачи можно легко решить графически. Соответствующие построения представлены на рис. 2.6. В результате получается:

Рис. 2.6

Найдем теперь решение ПЗ симплекс-методом. Для этого, используя дополнительные переменные, сводим ее к канонической задаче об отыска-

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

50