9.7. решение задачи линейного программирования симплекс-методом

9.7. решение задачи линейного программирования симплекс-методом

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

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

Если на очередном шаге удается установить оптимальность опорного решения или неограниченность целевой функции на допустимом множестве, то следующий шаг не выполняется.

Предположим, что перед выполнением очередного шага сим-плекс-таблица для задачи (9.7)—(9.9) приведена к базису

А' •"' \> Ак+1> •••> Аг (9-14) некоторого опорного решения а. Можно считать, что среди оценок этого базиса есть положительные оценки (в противном случае а — оптимальное решение). Выберем любую из положительных оценок, например 6^ > 0.

В симплекс-таблице, приведенной к базису (9.14), рассмотрим элементы

a[s, a'h, а'ь, а'п (9.15)

5-го столбца и соответствующие свободные члены

а,d,,dk,dr. (9.16)

Можно считать, что среди элементов (9.15) есть положительные (в противном случае целевая функция не ограничена снизу на допустимом множестве). В этом случае необходимо рассмотреть все отношения вида

4, где 4 > 0, (9.17)

als

233

т.е. отношения свободного члена к соответствующему элементу s-ro столбца при условии, что последний положителен.

Среди отношений (9.17) выбираем наименьшее. Если

то симплекс-таблицу приводим к новому базису

(9.18)

т.е. из базиса (9.14) исключаем вектор Ai , а вместо него вводим

вектор А.

Если Э > 0 (так заведомо случится, если исходное опорное решение не вырождено), то базис (9.18) является базисом нового опорного решения Р такого, что /ф) </(а).

Если же 0 = 0, то (9.18) является новым базисом исходного опорного решения а.

Если задача линейного программирования в канонической форме не имеет вырожденных опорных решений, то через конечное число шагов симплекс-метода она будет решена.

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

Для предотвращения зацикливания необходимо уточнить правило перехода к новому базису. Сделать это можно, например, следующим образом.

Среди оценок базиса (9.14) выбираем положительную оценку с наименьшим номером. Если 8S — такая оценка, а наименьшее из отношений (9.17) определено неоднозначно, берем

наименьшее отношение —fс наименьшим номером к.

^ks

О Пример. Для изготовления продукции используют три вида сырья. При этом можно применять любой из четырех способов производства. Запасы сырья, расход и количество продукции, производимой за 1 ч работы, по каждому способу приведены в табл. 9.5.

234

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

Обозначаем через х. время использования/-го способа производства (/'= 1, 2, 3, 4), получаем задачу линейного программирования

/ = 12xj + 7х2 + 18х3 + 10х4(тах),

Xj + 2х2 + х3 < 18,

• Ху + х2 + 2х3 + х4 < 30,

хх + Зх2 + Зх3 + 2х4 < 40,

ху>0, у = 1,2, 3,4.

Сведем эту задачу к канонической задаче минимизации:

/' = -12хх 7х2 18х3 10x4(min),

х^ + 2х2 + х3 + х^ 18,

• Xj + х2 + 2х3 + х4 + х6 = 30,

х, + Зх2 + Зх3 + 2х4 + х7 = 40,

ху>0, j= 1,2, 3,4, 5, 6, 7, и составим симплекс-таблицу:

Симплекс-таблица оказывается приведенной к базису А5, А6, А7 опорного решения а, = (0; 0; 0; 0; 18; 30; 40), при этом/'(otj) = 0.

235

Выбираем положительную оценку 8t = 12 и составляем следующие отношения: 18/1, 30/1, 40/1. Так как наименьшее среди них 18/1, то необходимо перейти к базису Av А6, А1. Для этого достаточно выполнить жорданово преобразование всей таблицы с ведущим элементом аи = 1. Имеем

Базис Av А6, А1 является базисом опорного решения ос2 = (18; 0; 0; 0; 0; 12; 22). При этом/'(ос2) = -216.

Выбираем оценку 84 = 10 > 0 и составляем отношения: 12/1, 22/2. Наименьшим среди них является 22/2. Следовательно, переходим к базису Av А4, А6. Получим

Все оценки базиса Av А4, А6 не положительны. Следовательно, ос3 = (18; 0; 0; 11; 0; 1; 0) — оптимальное решение канонической задачи минимизации. Поэтому р = (18; 0; 0; 11) — оптимальное решение исходной задачи. При этом/(Р) = 326.

Таким образом, для того чтобы выпустить наибольшее количество продукции при имеющихся запасах сырья, необходимо в течение 18 ч использовать первый способ производства и в течение 11ч — четвертый. В результате будет произведено 326 единиц продукции. •

236

9.8. Метод искусственного базиса для отыскания начального опорного решения

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

Рассмотрим задачу линейного программирования в канонической форме:

/ = XYy.x,.(min), (9.19)

7=1

^aijXj =bt, i = ,2,...,m, (9.20)

7=1

Xj >0, y = l,2,...,«. (9.21)

Без ограничения общности можно считать, что Ь. > 0, і = 1, 2, т. Для отыскания опорного решения задачи (9.19)—(9.21) строим вспомогательную задачу:

от

ф = 2>>.(min), (9.22)

п

J^ayXj + Уі = Ъ„ / = 1,2,...,т, (9.23)

7=1

Xj>0,j=,2,...,n; Уі>0,і=,2,...,т. (9.24) Свойства вспомогательной задачи:

Г. Вспомогательная задача (9.22)—(9.24) всегда имеет оптимальное решение.

2°. Вектор Р = (0, 0,0, bv b2,bm) является опорным решением задачи (9.22)-(9.24).

Таким образом, принимая вектор Р за начальное опорное решение, вспомогательную задачу можно решить симплекс-методом.

Пусть Р° = (Xj, х2, х°, у°, у2, у°) — оптимальное опорное решение задачи (9.22)—(9.24).

Если у®=у2 =... = у® = 0, то а = (x°v х2,х®) — опорное решение исходной задачи (9.19)—(9.21). Если же среди чисел у®, у2, у® есть положительные, то исходная задача (9.19)—(9.21) имеет пустое допустимое множество.

237

Таким образом, всегда можно либо найти опорное решение исходной задачи, либо установить ее неразрешимость.

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

Взаимно двойственные задачи линейного программирования имеют следующий вид:

и т

/ = 2уЛ(тах), (9.25) <р = ^ЬіУі(тіп), (9.29)

j=i і=і

п т

^aijXj = й„ / є I, (9.26) 2°^. = ур j є NJ, (9.30)

7=1 i=l

/сЖ = {1,2,. ..,m},

n m

^aijXj < bt, і є MI, (9.27) ^ауУі > ур j є /, (9.31)

j=i <=і

х.>0, jsJ, (9.28) у.>0, ієМІ. (9.32)

/сЛГ={1,2,...,л},

При этом задача максимизации (9.25)—(9.28) называется прямой (или исходной) задачей, а задача минимизации (9.29)—(9.32) — двойственной к ней.

Во взаимно двойственных задачах всегда:

одна из задач является задачей максимизации, а другая — задачей минимизации, в системе ограничений задачи максимизации неравенства записаны со знаком <, а в системе ограничений задачи минимизации — со знаком >;

каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения, при этом ограничению, записанному в виде неравенства, соответствует переменная, связанная условием неотрицательности;

матрица условий одной задачи получается из матрицы условий другой задачи с помощью транспонирования;

коэффициенты целевой функции одной задачи соответственно равны свободным членам системы ограничений другой задачи.

238

О Пример. Взаимно двойственными являются следующие задачи:

/= 5xj х2 + 8х3 х4(тах),

~ь х^ ~ь *7 х^ — 2^

JC^ J^2 ~г" 5.х^ х^ ^ 3) Х-^ х^ Н" Зх^ И7.Х4 — 5,

xt > 0, х3 > 0;

9 = 2^ + 3^ + 5^3(111111),

'2уу + з>2 + Уз ^ 5,

5л Уг Уз = -1,

-Уі + 5j>2 + Ьъ > 8,

7Уі ~ У2 + 7 Уз = у2>О.0

Частные случаи взаимно двойственных задач: 1. Если I = М = {, 2, т), а /= N = {1, 2, л}, то имеем несимметричную пару взаимно двойственных задач:

я т

f = ^yjXj(max), ф = 5^y,(min),

7=1

i=l

Xflj^ Y/> У = 1,2,...,п. i=i

ХаЛ' = г = 1,2,...,/и,

7=1

ху>0, у = 1, 2,...,«;

2. Если/=0, aJ=N= {1, 2,и}, то получим симметричную пару взаимно двойственных задач:

f = XYy^(max),

У=1

л

Ха»*у А> г" = 2,...,т,

y=i

ху>0, 7=1,2,и;

Ф ХА^Дтіп),

»=і

/и

Ха^ Ъ У = 1,2,...,и,

У,>0,

i=i

ти.

Простейшие свойства взаимно двойственных задач:

Г. Если а — допустимое решение прямой задачи (9.25)—(9.28),

а Р — допустимое решение двойственной задачи (9.29)—(9.32), то

Да)<Ф(Р).

2°. Если аир — допустимые решения соответственно прямой и двойственной задач и /(ос) = ф(Р), то а и р — оптимальные решения этих задач.

239