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

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

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

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

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

Сколько всего потребуется ресурса R1? Для изделия A необходима 1 единица данного ресурса, для изделия B - 2 единицы, а для изделия C - 3 единицы. Всего, следовательно, необходимо $1\cdot{x_A}+2\cdot{x_B}+3\cdot{x_C}$ единиц. Так как у нас 35 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 35: $1\cdot{x_A}+2\cdot{x_B}+3\cdot{x_C}\leq35$

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

$$\begin{array}{l} \left\{ {\begin{array}{*{20}{c}} {{x_A} + 2{x_B} + 3{x_C} \le 35}\\ {2{x_A} + 3{x_B} + 2{x_C} \le 45}\\ {3{x_A} + {x_B} + {x_C} \le 40} \end{array}} \right.\\ {x_A},{x_B},{x_C} \ge 0\\ F({x_A},{x_B},{x_C}) = 4{x_A} + 5{x_B} + 6{x_C} \to \max \end{array}$$

Начинаем решение задачи симплекс-методом

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

$$x_A+2\cdot{x_B}+3\cdot{x_C}\leq35$$

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

$$x_A+2\cdot{x_B}+3\cdot{x_C}+x_1=35$$

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

$$\begin{array}{l} \left\{ {\begin{array}{*{20}{c}} {{x_A} + 2{x_B} + 3{x_C} + {x_1} = 35}\\ {2{x_A} + 3{x_B} + 2{x_C} + {x_2} = 45}\\ {3{x_A} + {x_B} + {x_C} + {x_3} = 40} \end{array}} \right.\\ {x_A},{x_B},{x_C},{x_1},{x_2},{x_3} \ge 0\\ F({x_A},{x_B},{x_C}) = 4{x_A} + 5{x_B} + 6{x_C} \to \max \end{array}$$

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

Начальное решение может быть любое, но должно удовлетворять ограничениям задачи. Если мы записали производственную задачу в форме, приведенной выше, начальное решение найти очень просто. Это решение с нулевым доходом, когда мы ничего не производим. То есть, $x_A,x_B,x_C=0$. При этом у нас не тратится ни одного ресурса со склада, следовательно, $x_1=35,x_2=45,x_3=40$. Такое решение можно записать в виде $(0,0,0,35,45,40)$ - то есть, в скобках просто последовательно перечислить переменные (сначала "основные", а потом "введенные нами").

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

1. Чтобы найти число столбцов данной таблицы, необходимо прибавить 2 к общему числу переменных нашей задачи. В нашей задаче 6 переменных - $x_A,x_B,x_C,x_1,x_2,x_3$, следовательно, наша таблица будет иметь 8 столбцов.
2. Чтобы найти число строк данной таблицы, необходимо прибавить 2 к числу переменных начального решения, не равных нулю. В начальном решении три переменных не равно нулю - $x_1,x_2,x_3$, следовательно, наша таблица будет иметь 5 строк.

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_1$
$x_2$
$x_3$
F

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

$$2x_A+3x_B+2x_C+x_2=45$$

То переменная $x_C$ входит в это уравнение с коэффициентом 2. В строку $x_3$ и столбец $x_2$ необходимо поставить цифру $0$ - так как, если рассмотреть ограничение номер 3 - как раз то, в которое входит переменная $x_3$ -

$$3x_A+x_B+x_C+x_3=40$$

То переменная $x_2$ вообще не входит в это уравнение, то есть, входит в это уравнение с коэффициентом 0. В строку $x_3$ и столбец $x_3$ необходимо поставить цифру $1$ - так как, если рассмотреть ограничение номер 3 - как раз то, в которое входит переменная $x_3$ -

$$3x_A+x_B+x_C+x_3=40$$

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_1$	1	2	3	1	0	0
$x_2$	2	3	2	0	1	0
$x_3$	3	1	1	0	0	1
F

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_1$	1	2	3	1	0	0	35
$x_2$	2	3	2	0	1	0	45
$x_3$	3	1	1	0	0	1	40
F

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

$$F({x_A},{x_B},{x_C}) = 4{x_A} + 5{x_B} + 6{x_C} \to \max$$

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_1$	1	2	3	1	0	0	35
$x_2$	2	3	2	0	1	0	45
$x_3$	3	1	1	0	0	1	40
F	-4	-5	-6	0	0	0	0

Обратите внимание на клетки таблицы, выделенные жирным. В каждом столбце у нас один из коэффициентов - единица, а остальные нули. Таких столбцов на любом этапе решения у нас должно быть столько, сколько в задаче ограничений, то есть, в нашем случае, три. Причем единички должны быть на пересечении одинаковых столбца и строки, то есть, как в нашем случае, $x_1-x_1$, $x_2-x_2$, $x_3-x_3$.

Итерация 1

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

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B	$\frac{B}{x_C}$
$x_1$	1	2	3	1	0	0	35	$\frac{35}{3}\approx11,67$
$x_2$	2	3	2	0	1	0	45	$\frac{45}{2}=22,5$
$x_3$	3	1	1	0	0	1	40	$\frac{40}{1}=40$
F	-4	-5	-6	0	0	0	0

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
	$\frac{1}{3}$	$\frac{2}{3}$	1	$\frac{1}{3}$	0	0	$\frac{35}{3}$
$x_2$	2	3	2	0	1	0	45
$x_3$	3	1	1	0	0	1	40
F	-4	-5	-6	0	0	0	0

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

1. Чтобы во второй строке, в столбце $x_C$ число 2 превратить в ноль, вычтем из второй строки две первых.
2. Чтобы в третьей строке, в столбце $x_C$ число 1 превратить в ноль, вычтем из третьей строки первую.
3. Чтобы в последней строке, в столбце $x_C$ число -6 превратить в ноль, добавим к последней строке шесть первых.

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	$\frac{1}{3}$	$\frac{2}{3}$	1	$\frac{1}{3}$	0	0	$\frac{35}{3}$
$x_2$	$2-2\cdot\frac{1}{3}$	$3-2\cdot\frac{2}{3}$	$2-2\cdot1$	$0-2\cdot\frac{1}{3}$	$1-2\cdot0$	$0-2\cdot0$	$45-2\cdot\frac{35}{3}$
$x_3$	$3-\frac{1}{3}$	$1-\frac{2}{3}$	1-1	$0-\frac{1}{3}$	0-0	1-0	$40-\frac{35}{3}$
F	$-4+6\cdot\frac{1}{3}$	$-5+6\cdot\frac{2}{3}$	$-6+6\cdot1$	$0+6\cdot\frac{1}{3}$	$0+6\cdot0$	$0+6\cdot0$	$0+6\cdot\frac{35}{3}$

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	$\frac{1}{3}$	$\frac{2}{3}$	1	$\frac{1}{3}$	0	0	$\frac{35}{3}$
$x_2$	$\frac{4}{3}$	$\frac{5}{3}$	0	$-\frac{2}{3}$	$1$	$0$	$\frac{65}{3}$
$x_3$	$\frac{8}{3}$	$\frac{1}{3}$	0	$-\frac{1}{3}$	0	1	$\frac{85}{3}$
F	-2	-1	0	2	0	0	70

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

Итерация 2

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

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B	$\frac{B}{x_A}$
$x_C$	$\frac{1}{3}$	$\frac{2}{3}$	1	$\frac{1}{3}$	0	0	$\frac{35}{3}$	$\frac{35}{3}:\frac{1}{3}=35$
$x_2$	$\frac{4}{3}$	$\frac{5}{3}$	0	$-\frac{2}{3}$	$1$	$0$	$\frac{65}{3}$	$\frac{65}{3}:\frac{4}{3}=\frac{65}{4}=16,25$
$x_3$	$\frac{8}{3}$	$\frac{1}{3}$	0	$-\frac{1}{3}$	0	1	$\frac{85}{3}$	$\frac{85}{3}:\frac{8}{3}=\frac{85}{8}=10,625$
F	-2	-1	0	2	0	0	70

Мы нашли отношения для каждой строки, и для переменной $x_3$ отношение получилось наименьшим. Поэтому именно данную переменную необходимо убрать из базиса, заменив, как мы определили выше, переменной $x_A$. Прежде всего, найдем значение элемента на пересечении найденной строки и найденного столбца. Он равен $\frac{8}{3}$. И нам нужно всю найденную строку на этот элемент поделить:

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	$\frac{1}{3}$	$\frac{2}{3}$	1	$\frac{1}{3}$	0	0	$\frac{35}{3}$
$x_2$	$\frac{4}{3}$	$\frac{5}{3}$	0	$-\frac{2}{3}$	$1$	$0$	$\frac{65}{3}$
	1	$\frac{1}{8}$	0	$-\frac{1}{8}$	0	$\frac{3}{8}$	$\frac{85}{8}$
F	-2	-1	0	2	0	0	70

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

1. Чтобы в первой строке, в столбце $x_A$ число $\frac{1}{3}$ превратить в ноль, вычтем из первой строки третью, умноженную на $\frac{1}{3}$.
2. Чтобы во второй строке, в столбце $x_A$ число $\frac{4}{3}$ превратить в ноль, вычтем из второй строки третью, умноженную на $\frac{4}{3}$
3. Чтобы в последней строке, в столбце $x_A$ число -2 превратить в ноль, добавим к последней строке две третьих.

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	$\frac{1}{3}-\frac{1}{3}\cdot1$	$\frac{2}{3}-\frac{1}{3}\cdot\frac{1}{8}$	$1-\frac{1}{3}\cdot0$	$\frac{1}{3}-\frac{1}{3}\cdot(-\frac{1}{8})$	$0-\frac{1}{3}\cdot0$	$0-\frac{1}{3}\cdot\frac{3}{8}$	$\frac{35}{3}-\frac{1}{3}\cdot\frac{85}{8}$
$x_2$	$\frac{4}{3}-\frac{4}{3}\cdot1$	$\frac{5}{3}-\frac{4}{3}\cdot\frac{1}{8}$	$0-\frac{4}{3}\cdot0$	$-\frac{2}{3}-\frac{4}{3}\cdot(-\frac{1}{8})$	$1-\frac{4}{3}\cdot0$	$0-\frac{4}{3}\cdot\frac{3}{8}$	$\frac{65}{3}-\frac{4}{3}\cdot\frac{85}{8}$
	1	$\frac{1}{8}$	0	$-\frac{1}{8}$	0	$\frac{3}{8}$	$\frac{85}{8}$
F	$-2+2\cdot1$	$-1+2\cdot\frac{1}{8}$	$0+2\cdot0$	$2+2\cdot(-\frac{1}{8})$	$0+2\cdot0$	$0+2\cdot\frac{3}{8}$	$70+2\cdot\frac{85}{8}$

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	0	$\frac{5}{8}$	1	$\frac{3}{8}$	0	$-\frac{1}{8}$	$\frac{65}{8}$
$x_2$	0	$\frac{3}{2}$	0	$-\frac{1}{2}$	1	$-\frac{1}{2}$	$\frac{15}{2}$
$x_A$	1	$\frac{1}{8}$	0	$-\frac{1}{8}$	0	$\frac{3}{8}$	$\frac{85}{8}$
F	0	$-\frac{3}{4}$	0	$\frac{7}{4}$	0	$\frac{3}{4}$	$\frac{365}{4}$

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

Итерация 3

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B	$\frac{B}{x_B}$
$x_C$	0	$\frac{5}{8}$	1	$\frac{3}{8}$	0	$-\frac{1}{8}$	$\frac{65}{8}$	$\frac{65}{8}:\frac{5}{8}=13$
$x_2$	0	$\frac{3}{2}$	0	$-\frac{1}{2}$	1	$-\frac{1}{2}$	$\frac{15}{2}$	$\frac{15}{2}:\frac{3}{2}=5$
$x_A$	1	$\frac{1}{8}$	0	$-\frac{1}{8}$	0	$\frac{3}{8}$	$\frac{85}{8}$	$\frac{85}{8}:\frac{1}{8}=85$
F	0	$-\frac{3}{4}$	0	$\frac{7}{4}$	0	$\frac{3}{4}$	$\frac{365}{4}$

Мы нашли отношения для каждой строки, и для переменной $x_2$ отношение получилось наименьшим. Поэтому именно данную переменную необходимо убрать из базиса, заменив, как мы определили выше, переменной $x_B$. Прежде всего, найдем значение элемента на пересечении найденной строки и найденного столбца. Он равен $\frac{3}{2}$. И нам нужно всю найденную строку на этот элемент поделить:

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	0	$\frac{5}{8}$	1	$\frac{3}{8}$	0	$-\frac{1}{8}$	$\frac{65}{8}$
	0	1	0	$-\frac{1}{3}$	$\frac{2}{3}$	$-\frac{1}{3}$	$5$
$x_A$	1	$\frac{1}{8}$	0	$-\frac{1}{8}$	0	$\frac{3}{8}$	$\frac{85}{8}$
F	0	$-\frac{3}{4}$	0	$\frac{7}{4}$	0	$\frac{3}{4}$	$\frac{365}{4}$

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

1. Чтобы в первой строке, в столбце $x_B$ число $\frac{5}{8}$ превратить в ноль, вычтем из первой строки вторую, умноженную на $\frac{5}{8}$.
2. Чтобы в третьей строке, в столбце $x_B$ число $\frac{1}{8}$ превратить в ноль, вычтем из третьей строки вторую, умноженную на $\frac{1}{8}$.
3. Чтобы в последней строке, в столбце $x_B$ число $-\frac{3}{4}$ превратить в ноль, добавим к последней строке вторую, умноженную на $\frac{3}{4}$.

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	$0-\frac{5}{8}\cdot0$	$\frac{5}{8}-\frac{5}{8}\cdot1$	$1-\frac{5}{8}\cdot0$	$\frac{3}{8}-\frac{5}{8}\cdot(-\frac{1}{3})$	$0-\frac{5}{8}\cdot\frac{2}{3}$	$-\frac{1}{8}-\frac{5}{8}\cdot(-\frac{1}{3})$	$\frac{65}{8}-\frac{5}{8}\cdot5$
	0	1	0	$-\frac{1}{3}$	$\frac{2}{3}$	$-\frac{1}{3}$	$5$
$x_A$	$1-\frac{1}{8}\cdot0$	$\frac{1}{8}-\frac{1}{8}\cdot1$	$0-\frac{1}{8}\cdot0$	$-\frac{1}{8}-\frac{1}{8}\cdot(-\frac{1}{3})$	$0-\frac{1}{8}\cdot\frac{2}{3}$	$\frac{3}{8}-\frac{1}{8}\cdot(-\frac{1}{3})$	$\frac{85}{8}-\frac{1}{8}\cdot5$
F	$0+\frac{3}{4}\cdot0$	$-\frac{3}{4}+\frac{3}{4}\cdot1$	$0+\frac{3}{4}\cdot0$	$\frac{7}{4}+\frac{3}{4}\cdot(-\frac{1}{3})$	$0+\frac{3}{4}\cdot\frac{2}{3}$	$\frac{3}{4}+\frac{3}{4}\cdot(-\frac{1}{3})$	$\frac{365}{4}+\frac{3}{4}\cdot5$

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

	$x_A$	$x_B$	$x_C$	$x_1$	$x_2$	$x_3$	B
$x_C$	0	0	1	$\frac{7}{12}$	$-\frac{5}{12}$	$\frac{1}{12}$	$5$
$x_B$	0	1	0	$-\frac{1}{3}$	$\frac{2}{3}$	$-\frac{1}{3}$	$5$
$x_A$	1	0	0	$-\frac{1}{12}$	$-\frac{1}{12}$	$\frac{5}{12}$	10
F	0	0	0	$\frac{3}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	95

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

Итерация 4

Итерация 3 закончена, начинаем такую же итерацию 4. Прежде чем выполнять очередную итерацию, необходимо проверить, идеально ли наше решение? В последней строке НЕТ отрицательных элементов, следовательно, наше решение ОПТИМАЛЬНО. Осталось лишь записать получившееся решение. Как мы помним, всего у нас шесть переменных - $x_A,x_B,x_C,x_1,x_2,x_3$, и из них только три в базисе - $x_A,x_B,x_C$ (строки в итоговой таблице). Следовательно, остальные три переменных - $x_1,x_2,x_3$ равны нулю. Но, на самом деле, они нам и неинтересны, потому что мы ввели их сами - это остатки ресурсов на складах (то есть, у нас совсем не осталось ресурсов на складах - мы использовали все, что было). Значения же переменных $x_A, x_B, x_C$ мы получили в последнем столбце таблицы: $x_C=5$, $x_B=5$, $x_A=10$, или, как часто записывают решение таких задач - $(10,5,5)$. При этом можно посчитать значение получаемого дохода (целевой функции), а можно и не считать - оно посчитано за нас в правой нижней ячейке последней таблицы - $95$. Проверим это. Подставим в нашу целевую функцию получившееся решение:

$$F({x_A},{x_B},{x_C}) = 4{x_A} + 5{x_B} + 6{x_C}$$ $$F({x_A},{x_B},{x_C}) = 4\cdot10 + 5\cdot5 + 6\cdot5 = 40+25+30=95$$

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

Выводы

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

Далее: 2.1.3. Решение ЗЛП в Excel 2010, 2.1.4. Решение ЗЛП в Excel 2003

Полезное по теме

• Примеры решений задач ЛП симплексным способом
• Готовые контрольные по линейному программированию
• Заказать решение задачи симплекс-методом