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

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

Ресурс	Изделие 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 единицы. Всего, следовательно, необходимо 1⋅xA+2⋅xB+3⋅xC1⋅xA+2⋅xB+3⋅xC единиц. Так как у нас 35 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 35: 1⋅xA+2⋅xB+3⋅xC≤351⋅xA+2⋅xB+3⋅xC≤35

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

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

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

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

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

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

Начальное решение может быть любое, но должно удовлетворять ограничениям задачи. Если мы записали производственную задачу в форме, приведенной выше, начальное решение найти очень просто. Это решение с нулевым доходом, когда мы ничего не производим. То есть, 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 —

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

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

То переменная 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

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

Она не зависит от переменных 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

Обратите внимание на клетки таблицы, выделенные жирным. В каждом столбце у нас один из коэффициентов — единица, а остальные нули. Таких столбцов на любом этапе решения у нас должно быть столько, сколько в задаче ограничений, то есть, в нашем случае, три. Причем единички должны быть на пересечении одинаковых столбца и строки, то есть, как в нашем случае, x1−x1x1−x1, x2−x2x2−x2, x3−x3x3−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	353≈11,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	2−2⋅132−2⋅13	3−2⋅233−2⋅23	2−2⋅12−2⋅1	0−2⋅130−2⋅13	1−2⋅01−2⋅0	0−2⋅00−2⋅0	45−2⋅35345−2⋅353
x3x3	3−133−13	1−231−23	1-1	0−130−13	0-0	1-0	40−35340−353
F	−4+6⋅13−4+6⋅13	−5+6⋅23−5+6⋅23	−6+6⋅1−6+6⋅1	0+6⋅130+6⋅13	0+6⋅00+6⋅0	0+6⋅00+6⋅0	0+6⋅3530+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	13−13⋅113−13⋅1	23−13⋅1823−13⋅18	1−13⋅01−13⋅0	13−13⋅(−18)13−13⋅(−18)	0−13⋅00−13⋅0	0−13⋅380−13⋅38	353−13⋅858353−13⋅858
x2x2	43−43⋅143−43⋅1	53−43⋅1853−43⋅18	0−43⋅00−43⋅0	−23−43⋅(−18)−23−43⋅(−18)	1−43⋅01−43⋅0	0−43⋅380−43⋅38	653−43⋅858653−43⋅858
	1	1818	0	−18−18	0	3838	858858
F	−2+2⋅1−2+2⋅1	−1+2⋅18−1+2⋅18	0+2⋅00+2⋅0	2+2⋅(−18)2+2⋅(−18)	0+2⋅00+2⋅0	0+2⋅380+2⋅38	70+2⋅85870+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	0−58⋅00−58⋅0	58−58⋅158−58⋅1	1−58⋅01−58⋅0	38−58⋅(−13)38−58⋅(−13)	0−58⋅230−58⋅23	−18−58⋅(−13)−18−58⋅(−13)	658−58⋅5658−58⋅5
	0	1	0	−13−13	2323	−13−13	55
xAxA	1−18⋅01−18⋅0	18−18⋅118−18⋅1	0−18⋅00−18⋅0	−18−18⋅(−13)−18−18⋅(−13)	0−18⋅230−18⋅23	38−18⋅(−13)38−18⋅(−13)	858−18⋅5858−18⋅5
F	0+34⋅00+34⋅0	−34+34⋅1−34+34⋅1	0+34⋅00+34⋅0	74+34⋅(−13)74+34⋅(−13)	0+34⋅230+34⋅23	34+34⋅(−13)34+34⋅(−13)	3654+34⋅53654+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=5, xB=5xB=5, xA=10xA=10, или, как часто записывают решение таких задач — (10,5,5)(10,5,5). При этом можно посчитать значение получаемого дохода (целевой функции), а можно и не считать — оно посчитано за нас в правой нижней ячейке последней таблицы — 9595. Проверим это. Подставим в нашу целевую функцию получившееся решение:

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

Выводы

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