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

Постановка задачи

Так как симплекс-метод можно применять при любом числе производимых товаров и любом числе используемых ресурсов, то возьмем задачу посложнее — с тремя ресурсами и тремя товарами:

Ресурс Изделие A Изделие B Изделие C Сколько ресурса на складах
R1 1 2 3 35
R2 2 3 2 45
R3 3 1 1 40
Прибыль 4 5 6

Точно так же, как в предыдущем пункте, попробуем записать систему ограничений нашей задачи и целевую функцию в виде неравенств. Обозначим за xA,xBxA,xB и xCxCколичество производимых изделий A, B и C, соответственно. Больше не будем расписывать весь процесс подробно, покажем лишь получение первого ограничения

Сколько всего потребуется ресурса R1? Для изделия A необходима 1 единица данного ресурса, для изделия B — 2 единицы, а для изделия C — 3 единицы. Всего, следовательно, необходимо 1xA+2xB+3xC1⋅xA+2⋅xB+3⋅xC единиц. Так как у нас 35 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 35: 1xA+2xB+3xC351⋅xA+2⋅xB+3⋅xC≤35

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

⎧⎩⎨⎪⎪xA+2xB+3xC352xA+3xB+2xC453xA+xB+xC40xA,xB,xC0F(xA,xB,xC)=4xA+5xB+6xCmax{xA+2xB+3xC≤352xA+3xB+2xC≤453xA+xB+xC≤40xA,xB,xC≥0F(xA,xB,xC)=4xA+5xB+6xC→max

Начинаем решение задачи

Чтобы начать решать производственную задачу симплекс-методом, необходимо, как и в случае графического метода, наши неравенства превратить в равенства. Рассмотрим первое неравенство:

xA+2xB+3xC35xA+2⋅xB+3⋅xC≤35

Что означает это выражение? Оно означает, что количество потребляемых ресурсов R1 не должно быть больше количества, которое у нас на складе. Но оно вполне может быть и меньше, например, 30. Тогда некоторое количество ресурсов останется на складе неиспользованными. Обозначим это число (обратите внимание, оно не должно быть меньше нуля) за x1x1. Если его добавить к числу использованных ресурсов, должно получиться ровно 35:

xA+2xB+3xC+x1=35xA+2⋅xB+3⋅xC+x1=35

Точно так же, добавим переменные x2x2 и x3x3 (число оставшихся на складе ресурсов вида R2 и R3) ко второму и третьему ограничениям. В итоге получим следующую систему ограничений:

⎧⎩⎨⎪⎪xA+2xB+3xC+x1=352xA+3xB+2xC+x2=453xA+xB+xC+x3=40xA,xB,xC,x1,x2,x30F(xA,xB,xC)=4xA+5xB+6xCmax{xA+2xB+3xC+x1=352xA+3xB+2xC+x2=453xA+xB+xC+x3=40xA,xB,xC,x1,x2,x3≥0F(xA,xB,xC)=4xA+5xB+6xC→max

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

Начальное решение может быть любое, но должно удовлетворять ограничениям задачи. Если мы записали производственную задачу в форме, приведенной выше, начальное решение найти очень просто. Это решение с нулевым доходом, когда мы ничего не производим. То есть, xA,xB,xC=0xA,xB,xC=0. При этом у нас не тратится ни одного ресурса со склада, следовательно, x1=35,x2=45,x3=40x1=35,x2=45,x3=40. Такое решение можно записать в виде (0,0,0,35,45,40)(0,0,0,35,45,40) — то есть, в скобках просто последовательно перечислить переменные (сначала «основные», а потом «введенные нами»).

После того, как мы это сделали, необходимо составить симплекс-таблицу. У нее будут следующие параметры:

  1. Чтобы найти число столбцов данной таблицы, необходимо прибавить 2 к общему числу переменных нашей задачи. В нашей задаче 6 переменных — xA,xB,xC,x1,x2,x3xA,xB,xC,x1,x2,x3, следовательно, наша таблица будет иметь 8 столбцов.
  2. Чтобы найти число строк данной таблицы, необходимо прибавить 2 к числу переменных начального решения, не равных нулю. В начальном решении три переменных не равно нулю — x1,x2,x3x1,x2,x3, следовательно, наша таблица будет иметь 5 строк.

Построим данную таблицу. В первой строке запишем наши переменные, а в первом столбце — переменные, не равные нулю (они будут в дальнейшем называться «базисные»):

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
x1x1
x2x2
x3x3
F

Заполнять эту таблицу очень просто. Чтобы заполнить все столбцы, кроме последнего, и все строки, кроме последней, необходимо подставить в клетки таблицы коэффициенты в соответствующих ограничениях. Например, в строку x2x2 и столбец xCxC необходимо поставить цифру 22 — так как, если рассмотреть ограничение номер 2 — как раз то, в которое входит переменная x2x2 —

2xA+3xB+2xC+x2=452xA+3xB+2xC+x2=45

То переменная xCxC входит в это уравнение с коэффициентом 2. В строку x3x3 и столбец x2x2 необходимо поставить цифру 00 — так как, если рассмотреть ограничение номер 3 — как раз то, в которое входит переменная x3x3 —

3xA+xB+xC+x3=403xA+xB+xC+x3=40

То переменная x2x2 вообще не входит в это уравнение, то есть, входит в это уравнение с коэффициентом 0. В строку x3x3 и столбец x3x3 необходимо поставить цифру 11 — так как, если рассмотреть ограничение номер 3 — как раз то, в которое входит переменная x3x3 —

3xA+xB+xC+x3=403xA+xB+xC+x3=40

То переменная x3x3 входит в это уравнение с коэффициентом 1. Заполним подобным образом все коэффициенты:

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
x1x1 1 2 3 1 0 0
x2x2 2 3 2 0 1 0
x3x3 3 1 1 0 0 1
F

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

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
x1x1 1 2 3 1 0 0 35
x2x2 2 3 2 0 1 0 45
x3x3 3 1 1 0 0 1 40
F

И, наконец, в последнюю строку записываем коэффициенты целевой функции при соответствующих переменных с противоположным знаком. Как можно видеть из выражения нашей целевой функции —

F(xA,xB,xC)=4xA+5xB+6xCmaxF(xA,xB,xC)=4xA+5xB+6xC→max

Она не зависит от переменных x1,x2,x3x1,x2,x3, следовательно, в этих столбцах необходимо поставить нули. Кроме того, в правую нижнюю клетку ставим текущее значение целевой функции. Так как мы пока ничего не производим, значит и прибыли не получаем, и значение целевой функции равно нулю.

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
x1x1 1 2 3 1 0 0 35
x2x2 2 3 2 0 1 0 45
x3x3 3 1 1 0 0 1 40
F -4 -5 -6 0 0 0 0

Обратите внимание на клетки таблицы, выделенные жирным. В каждом столбце у нас один из коэффициентов — единица, а остальные нули. Таких столбцов на любом этапе решения у нас должно быть столько, сколько в задаче ограничений, то есть, в нашем случае, три. Причем единички должны быть на пересечении одинаковых столбца и строки, то есть, как в нашем случае, x1x1x1−x1x2x2x2−x2x3x3x3−x3.

Итерация 1

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

Выберем самое большое по модулю отрицательное значение -6 в столбце xCxC, эту переменную необходимо добавить к нашему базису (то есть, ввести ее в одну из строк слева). Но тогда одну из переменных текущего базиса (x1,x2,x3x1,x2,x3) необходимо убрать. Чтобы узнать, какую, необходимо найти для каждой базисной переменной (каждой строки) отношение свободного члена (значения в столбце B) к коэффициенту в строке xCxC (переменной, которую, как мы решили выше, необходимо ввести в базис). Обратите внимание, что это отношение должно существовать, и оно должно быть положительно. Если это не так, мы просто пропускаем соответствующую строку

xAxA xBxB xCxC x1x1 x2x2 x3x3 B BxCBxC
x1x1 1 2 3 1 0 0 35 35311,67353≈11,67
x2x2 2 3 2 0 1 0 45 452=22,5452=22,5
x3x3 3 1 1 0 0 1 40 401=40401=40
F -4 -5 -6 0 0 0 0

Мы нашли отношения для каждой строки, и для первой строки отношение получилось наименьшим. Поэтому именно данную строку (то есть, переменную x1x1) необходимо убрать из базиса, заменив, как мы определили выше, переменной xCxC. Как это сделать? Прежде всего, найдем значение элемента на пересечении найденной строки и найденного столбца. Он равен 3 (в таблице выше он подчеркнут). И нам нужно всю найденную строку на этот элемент поделить:

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
1313 2323 1 1313 0 0 353353
x2x2 2 3 2 0 1 0 45
x3x3 3 1 1 0 0 1 40
F -4 -5 -6 0 0 0 0

Обратите внимание, из первой строки исчезло название строки — x1x1. Это потому, чтоx1x1 — больше не базисная переменная. Она была бы базисной, если бы был столбец x1x1, в котором была бы одна единица, а остальные нули. Но такого столбца больше нет. Теперь первая строка не выражает никакой базисной переменной. Нам же необходимо, чтобы базисной стала переменная xCxC. Первое требование к базисным переменным для нее выполняется — есть столбец xCxC, и у него в первой строке число 1. Но вот остальные числа не равны нулю. Так давайте их сделаем такими.

  1. Чтобы во второй строке, в столбце xCxC число 2 превратить в ноль, вычтем из второй строки две первых.
  2. Чтобы в третьей строке, в столбце xCxC число 1 превратить в ноль, вычтем из третьей строки первую.
  3. Чтобы в последней строке, в столбце xCxC число -6 превратить в ноль, добавим к последней строке шесть первых.
xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 1313 2323 1 1313 0 0 353353
x2x2 22132−2⋅13 32233−2⋅23 2212−2⋅1 02130−2⋅13 1201−2⋅0 0200−2⋅0 45235345−2⋅353
x3x3 3133−13 1231−23 1-1 0130−13 0-0 1-0 4035340−353
F 4+613−4+6⋅13 5+623−5+6⋅23 6+61−6+6⋅1 0+6130+6⋅13 0+600+6⋅0 0+600+6⋅0 0+63530+6⋅353

Проводим математические действия и получаем итоговую таблицу.

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 1313 2323 1 1313 0 0 353353
x2x2 4343 5353 0 23−23 11 00 653653
x3x3 8383 1313 0 13−13 0 1 853853
F -2 -1 0 2 0 0 70

Теперь первая строка у нас выражает базисную переменную xCxC, так как действительно, в столбце xCxC одно значение равно 1, а остальные — 0. Итерация выполнена.

Итерация 2

Хорошо. Итерация 1 закончена, начинаем такую же итерацию 2. Прежде чем выполнять очередную итерацию, необходимо проверить, идеально ли наше решение? В последней строке есть отрицательные элементы, следовательно, наше решение не оптимально.

Выберем самое большое по модулю отрицательное значение -2 в столбце xAxA, эту переменную необходимо добавить к нашему базису, а одну из переменных текущего базиса (xC,x2,x3xC,x2,x3) необходимо убрать. Чтобы узнать, какую, необходимо найти для каждой базисной переменной отношение свободного члена к коэффициенту в строке xAxA (переменной, которую, как мы решили выше, необходимо ввести в базис).Обратите внимание, что это отношение должно существовать, и оно должно быть положительно. Если это не так, мы просто пропускаем соответствующую строку

xAxA xBxB xCxC x1x1 x2x2 x3x3 B BxABxA
xCxC 1313 2323 1 1313 0 0 353353 353:13=35353:13=35
x2x2 4343 5353 0 23−23 11 00 653653 653:43=654=16,25653:43=654=16,25
x3x3 8383 1313 0 13−13 0 1 853853 853:83=858=10,625853:83=858=10,625
F -2 -1 0 2 0 0 70

Мы нашли отношения для каждой строки, и для переменной x3x3 отношение получилось наименьшим. Поэтому именно данную переменную необходимо убрать из базиса, заменив, как мы определили выше, переменной xAxA. Прежде всего, найдем значение элемента на пересечении найденной строки и найденного столбца. Он равен 8383. И нам нужно всю найденную строку на этот элемент поделить:

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 1313 2323 1 1313 0 0 353353
x2x2 4343 5353 0 23−23 11 00 653653
1 1818 0 18−18 0 3838 858858
F -2 -1 0 2 0 0 70

Из третьей строки исчезло название строки — x3x3. Это потому, что x3x3 — больше не базисная переменная. Нам же необходимо, чтобы базисной стала переменная xAxA. Первое требование к базисным переменным для нее выполняется — есть столбец xAxA, и у него в третьей строке число 1. Но вот остальные числа не равны нулю. Так давайте их сделаем такими.

  1. Чтобы в первой строке, в столбце xAxA число 1313 превратить в ноль, вычтем из первой строки третью, умноженную на 1313.
  2. Чтобы во второй строке, в столбце xAxA число 4343 превратить в ноль, вычтем из второй строки третью, умноженную на 4343
  3. Чтобы в последней строке, в столбце xAxA число -2 превратить в ноль, добавим к последней строке две третьих.
xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 1313113−13⋅1 23131823−13⋅18 11301−13⋅0 1313(18)13−13⋅(−18) 01300−13⋅0 013380−13⋅38 35313858353−13⋅858
x2x2 4343143−43⋅1 53431853−43⋅18 04300−43⋅0 2343(18)−23−43⋅(−18) 14301−43⋅0 043380−43⋅38 65343858653−43⋅858
1 1818 0 18−18 0 3838 858858
F 2+21−2+2⋅1 1+218−1+2⋅18 0+200+2⋅0 2+2(18)2+2⋅(−18) 0+200+2⋅0 0+2380+2⋅38 70+285870+2⋅858

Проводим математические действия и получаем итоговую таблицу.

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 0 5858 1 3838 0 18−18 658658
x2x2 0 3232 0 12−12 1 12−12 152152
xAxA 1 1818 0 18−18 0 3838 858858
F 0 34−34 0 7474 0 3434 36543654

Теперь третья строка у нас выражает базисную переменную xAxA, так как действительно, в столбце xAxA одно значение равно 1, а остальные — 0. Итерация выполнена.

Итерация 3

Итерация 2 закончена, начинаем такую же итерацию 3. Прежде чем выполнять очередную итерацию, необходимо проверить, идеально ли наше решение? В последней строке есть отрицательный элемент, следовательно, наше решение не оптимально. Этот элемент один, в столбце xBxB, эту переменную необходимо добавить к нашему базису, а одну из переменных текущего базиса (xC,x2,xAxC,x2,xA) необходимо убрать. Чтобы узнать, какую, необходимо найти для каждой базисной переменной отношение свободного члена к коэффициенту в строке xBxB (переменной, которую, как мы решили выше, необходимо ввести в базис). Обратите внимание, что это отношение должно существовать, и оно должно быть положительно. Если это не так, мы просто пропускаем соответствующую строку

xAxA xBxB xCxC x1x1 x2x2 x3x3 B BxBBxB
xCxC 0 5858 1 3838 0 18−18 658658 658:58=13658:58=13
x2x2 0 3232 0 12−12 1 12−12 152152 152:32=5152:32=5
xAxA 1 1818 0 18−18 0 3838 858858 858:18=85858:18=85
F 0 34−34 0 7474 0 3434 36543654

Мы нашли отношения для каждой строки, и для переменной x2x2 отношение получилось наименьшим. Поэтому именно данную переменную необходимо убрать из базиса, заменив, как мы определили выше, переменной xBxB. Прежде всего, найдем значение элемента на пересечении найденной строки и найденного столбца. Он равен 3232. И нам нужно всю найденную строку на этот элемент поделить:

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 0 5858 1 3838 0 18−18 658658
0 1 0 13−13 2323 13−13 55
xAxA 1 1818 0 18−18 0 3838 858858
F 0 34−34 0 7474 0 3434 36543654

Из второй строки исчезло название строки — x2x2. Это потому, что x2x2 — больше не базисная переменная. Нам же необходимо, чтобы базисной стала переменная xBxB. Первое требование к базисным переменным для нее выполняется — есть столбец xBxB, и у него в третьей строке число 1. Но вот остальные числа не равны нулю. Так давайте их сделаем такими.

  1. Чтобы в первой строке, в столбце xBxB число 5858 превратить в ноль, вычтем из первой строки вторую, умноженную на 5858.
  2. Чтобы в третьей строке, в столбце xBxB число 1818 превратить в ноль, вычтем из третьей строки вторую, умноженную на 1818.
  3. Чтобы в последней строке, в столбце xBxB число 34−34 превратить в ноль, добавим к последней строке вторую, умноженную на 3434.
xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 05800−58⋅0 5858158−58⋅1 15801−58⋅0 3858(13)38−58⋅(−13) 058230−58⋅23 1858(13)−18−58⋅(−13) 658585658−58⋅5
0 1 0 13−13 2323 13−13 55
xAxA 11801−18⋅0 1818118−18⋅1 01800−18⋅0 1818(13)−18−18⋅(−13) 018230−18⋅23 3818(13)38−18⋅(−13) 858185858−18⋅5
F 0+3400+34⋅0 34+341−34+34⋅1 0+3400+34⋅0 74+34(13)74+34⋅(−13) 0+34230+34⋅23 34+34(13)34+34⋅(−13) 3654+3453654+34⋅5

Проводим математические действия и получаем итоговую таблицу.

xAxA xBxB xCxC x1x1 x2x2 x3x3 B
xCxC 0 0 1 712712 512−512 112112 55
xBxB 0 1 0 13−13 2323 13−13 55
xAxA 1 0 0 112−112 112−112 512512 10
F 0 0 0 3232 1212 1212 95

Теперь вторая строка у нас выражает базисную переменную xBxB, так как действительно, в столбце xBxB одно значение равно 1, а остальные — 0. Итерация выполнена.

Итерация 4

Итерация 3 закончена, начинаем такую же итерацию 4. Прежде чем выполнять очередную итерацию, необходимо проверить, идеально ли наше решение? В последней строке НЕТ отрицательных элементов, следовательно, наше решение ОПТИМАЛЬНО. Осталось лишь записать получившееся решение. Как мы помним, всего у нас шесть переменных — xA,xB,xC,x1,x2,x3xA,xB,xC,x1,x2,x3, и из них только три в базисе — xA,xB,xCxA,xB,xC (строки в итоговой таблице). Следовательно, остальные три переменных — x1,x2,x3x1,x2,x3 равны нулю. Но, на самом деле, они нам и неинтересны, потому что мы ввели их сами — это остатки ресурсов на складах (то есть, у нас совсем не осталось ресурсов на складах — мы использовали все, что было). Значения же переменныхxA,xB,xCxA,xB,xC мы получили в последнем столбце таблицы: xC=5xC=5xB=5xB=5xA=10xA=10, или, как часто записывают решение таких задач — (10,5,5)(10,5,5). При этом можно посчитать значение получаемого дохода (целевой функции), а можно и не считать — оно посчитано за нас в правой нижней ячейке последней таблицы — 9595. Проверим это. Подставим в нашу целевую функцию получившееся решение:

F(xA,xB,xC)=4xA+5xB+6xCF(xA,xB,xC)=4xA+5xB+6xC
F(xA,xB,xC)=410+55+65=40+25+30=95F(xA,xB,xC)=4⋅10+5⋅5+6⋅5=40+25+30=95

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

Выводы

Видно, что в процессе решения нам понадобилось заполнять множество таблиц и делать много скучных вычислений. Поэтому было бы неплохо, если бы работу за нас выполнил компьютер. Такая возможность существует — в программе Microsoft Excel есть специальная функция Поиск решений, которая может решить задачу линейного программирования за нас. Как это сделать, мы рассмотрим в следующих двух главах — для Microsoft Excel 2003 (и более старых версий) и для Microsoft Excel 2007 (и более новых версий).

Информация