Решение задачи линейного программирования методом Гомори
Введение
Задачи, которые мы решали ранее всегда давали целочисленный ответ. Это происходило потому, что исходные данные были подобраны специальным образом. Но так бывает не всегда.
Гораздо чаще в ответе получаются дробные величины - например, нужно произвести 2,5 единицы изделия A и 3,44 единицы изделия B. Допустимо ли такое решение? Тут все зависит от условий задачи. Если мы производим, например, муку и сахар в килограммах - такое решение вполне допустимо. 2,5 единицы изделия A - это 2 килограмма 500 грамм муки, а 3,44 единицы изделия B это 3 килограмма 440 грамм сахара. Однако представьте, что изделие A - это компьютеры, а изделие B - это MP3-плееры. Как можно произвести 3,44 единицы MP3-плеера? Очевидно, что никак. В таких случаях говорят, что необходимо решить задачу целочисленного линейного программирования, подразумевая, что в ответе обязательно должны получиться целые числа.
Для решения целочисленных задач был разработан специальный метод под названием Метод Гомори. На самом деле, метод Гомори это всего лишь "надстройка" над обычным симплекс-методом, который мы изучили в прошлых главах. Идея метода Гомори заключается в том, что можно решить задачу обычным симплекс-методом, получив (возможно) нецелочисленное решение, а потом для каждой нецелочисленной переменной добавить "поправочное" ограничение, которое во-первых, сделает эту переменную целочисленной, а во-вторых, минимальным образом повлияет на значение целевой функции.
Алгоритм метода Гомори
Итак, понятно, что нам необходимо сначала просто решить задачу симплекс-методом, а затем для каждой нецелочисленной переменной в решении немного "подправить" ее значение. То есть, схема метода Гомори примерно следующая:
- Решить исходную производственную задачу обычным симплекс-методом;
- Убедиться, что ответ получился нецелочисленным. Если он целочисленный, то задача решена;
- Умножить значения в последней строке (строка F) на -1;
- Пока в ответе остались нецелочисленные переменные, делать следующее:
- Среди нецелочисленных значений в получившемся решении выбрать переменную, для которой необходимо составить дополнительное ограничение (как это сделать будет объяснено в нижеприведенном примере);
- К исходной задаче добавить специальным образом составленное ограничение для выбранной переменной (опять же, в примере будет показано, как именно это сделать). Это приведет к появлению еще одной вспомогательной переменной;
- К полученной задаче применить один этап симплекс-метода, причем убрать появившуюся вспомогательную переменную, и добавить какую-то из исходных (какую именно также будет объяснено в примере).
- Предыдущий шаг (шаг 4) необходимо выполнять, пока все решение не станет целочисленным. Метод Гомори гарантирует, что на каком-либо шаге это точно произойдет.
Решение производственной задачи методом Гомори
Решим методом Гомори ту же самую производственную задачу, которую решали ранее Симплекс-методом, но изменим в ней одно число - чтобы решение с использованием Симплекс-метода получилось нецелочисленным:
| Ресурс | Изделие A | Изделие B | Изделие C | Сколько ресурса на складах |
| R1 | 1 | 2 | 3 | 35 |
| R2 | 4 | 3 | 2 | 45 |
| R3 | 3 | 1 | 1 | 40 |
| Прибыль | 4 | 5 | 6 |
Как обычно, запишем систему ограничений нашей задачи и целевую функцию в виде неравенств. Обозначим за $x_A, x_B$ и $x_C$ количество производимых изделий A, B и C, соответственно. Так как весь процесс был подробно описан ранее, приведем только результат:
$$\begin{array}{l} \left\{ {\begin{array}{*{20}{c}} {{x_A} + 2{x_B} + 3{x_C} \le 35}\\ {4{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_1},{x_2},{x_3}$:
$$\begin{array}{l} \left\{ {\begin{array}{*{20}{c}} {{x_A} + 2{x_B} + 3{x_C} + {x_1} = 35}\\ {4{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)$ - то есть, в скобках просто последовательно перечислить переменные (сначала "основные", а потом "введенные нами").
Запишем симплекс-таблицу. Как это делается было подробно объяснено тут.
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | B | |
| $x_1$ | 1 | 2 | 3 | 1 | 0 | 0 | 35 |
| $x_2$ | 4 | 3 | 2 | 0 | 1 | 0 | 45 |
| $x_3$ | 3 | 1 | 1 | 0 | 0 | 1 | 40 |
| F | -4 | -5 | -6 | 0 | 0 | 0 | 0 |
Итерация 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$ | 4 | 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$ | 4 | 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. Но вот остальные числа не равны нулю. Так давайте их сделаем такими.
- Чтобы во второй строке, в столбце $x_C$ число 2 превратить в ноль, вычтем из второй строки две первых.
- Чтобы в третьей строке, в столбце $x_C$ число 1 превратить в ноль, вычтем из третьей строки первую.
- Чтобы в последней строке, в столбце $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$ | $4-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{10}{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
Прежде чем выполнять очередную итерацию, необходимо проверить, оптимально ли наше решение? В последней строке есть отрицательные элементы, следовательно, наше решение не оптимально.
Выберем самое большое по модулю отрицательное значение -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{10}{3}$ | $\frac{5}{3}$ | 0 | $-\frac{2}{3}$ | 1 | 0 | $\frac{65}{3}$ | $\frac{65}{3}:\frac{10}{3}=\frac{65}{10}=6,5$ |
| $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_2$ отношение получилось наименьшим. Поэтому именно данную переменную необходимо убрать из базиса, заменив, как мы определили выше, переменной $x_A$. Прежде всего, найдем значение элемента на пересечении найденной строки и найденного столбца. Он равен $\frac{10}{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}$ |
| 1 | $\frac{1}{2}$ | 0 | $-\frac{1}{5}$ | $\frac{3}{10}$ | 0 | $\frac{65}{10}$ | |
| $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_2$. Это потому, что $x_2$ - больше не базисная переменная. Нам же необходимо, чтобы базисной стала переменная $x_A$. Первое требование к базисным переменным для нее выполняется - есть столбец $x_A$, и у него во второй строке число 1. Но вот остальные числа не равны нулю. Так давайте их сделаем такими.
- Чтобы в первой строке, в столбце $x_A$ число $\frac{1}{3}$ превратить в ноль, вычтем из первой строки вторую, умноженную на $\frac{1}{3}$.
- Чтобы в третьей строке, в столбце $x_A$ число $\frac{8}{3}$ превратить в ноль, вычтем из третьей строки вторую, умноженную на $\frac{8}{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}{2}$ | $1-\frac{1}{3}\cdot0$ | $\frac{1}{3}-\frac{1}{3}\cdot(-\frac{1}{5})$ | $0-\frac{1}{3}\cdot\frac{3}{10}$ | 0 | $\frac{35}{3}-\frac{1}{3}\cdot\frac{65}{10}$ |
| 1 | $\frac{1}{2}$ | 0 | $-\frac{1}{5}$ | $\frac{3}{10}$ | 0 | $\frac{65}{10}$ | $x_3$ | $\frac{8}{3}-\frac{8}{3}\cdot1$ | $\frac{1}{3}-\frac{8}{3}\cdot\frac{1}{2}$ | $0-\frac{1}{3}\cdot0$ | $-\frac{1}{3}-\frac{8}{3}\cdot(-\frac{1}{5})$ | $0-\frac{8}{3}\cdot\frac{3}{10}$ | $1-\frac{8}{3}\cdot0$ | $\frac{85}{3}-\frac{8}{3}\cdot\frac{65}{10}$ |
| F | $-2+2\cdot1$ | $-1+2\cdot\frac{1}{2}$ | $0+2\cdot0$ | $2+2\cdot(-\frac{1}{5})$ | $0+2\cdot\frac{3}{10}$ | $0+2\cdot0$ | $70+2\cdot\frac{65}{10}$ |
Проводим математические действия и получаем итоговую таблицу.
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | B | |
| $x_C$ | 0 | $\frac{1}{2}$ | 1 | $\frac{2}{5}$ | $-\frac{1}{10}$ | 0 | $\frac{19}{2}$ |
| $x_A$ | 1 | $\frac{1}{2}$ | 0 | $-\frac{1}{5}$ | $\frac{3}{10}$ | 0 | $\frac{13}{2}$ | $x_3$ | 0 | -1 | 0 | $\frac{1}{5}$ | $-\frac{4}{5}$ | 1 | 11 |
| F | 0 | 0 | 0 | $\frac{8}{5}$ | $\frac{3}{5}$ | 0 | 83 |
Теперь вторая строка у нас выражает базисную переменную $x_A$, так как действительно, в столбце $x_A$ одно значение равно 1, а остальные - 0. Итерация выполнена.
Итерация 3
Прежде чем выполнять очередную итерацию, необходимо проверить, оптимально ли наше решение? В последней строке нет отрицательных элементов, следовательно, наше решение оптимально. Если записать значения интересующих нас переменных $x_A,x_B,x_C$, то получим, что $x_A=\frac{13}{2};x_B=0;x_C=\frac{19}{2}$. Значения получились нецелые. Следовательно, необходимо применить метод Гомори. По методу Гомори нам необходимо добавить еще одно ограничение к нашей задаче. Сперва необходимо определить, для какой нецелой переменной мы будем составлять дополнительное ограничение. У нас две нецелых переменных - $x_C$ и $x_A$. Чтобы определить, для какой именно, необходимо найти дробные части чисел, стоящих в соответствующих строках, столбце B.
- Число, стоящее в строке $x_C$, столбце B равно $\frac{19}{2}$. Можно записать его как $9\frac{1}{2}$. Его дробная часть равна $\frac{1}{2}$
- Число, стоящее в строке $x_A$, столбце B равно $\frac{13}{2}$. Можно записать его как $6\frac{1}{2}$. Его дробная часть равна $\frac{1}{2}$
Среди данных дробных частей нужно найти наибольшую, и именно для этой переменной мы будем составлять дополнительное ограничение. Однако у нас дробные части получились равными, поэтому просто берем первую - $x_C$. Составляем для переменной $x_C$ ограничение. Оно будет иметь вид:
$$q_C-q_{CA}\cdot{x_A}-q_{CB}\cdot{x_B}-q_{CC}\cdot{x_C}-q_{C1}\cdot{x_1}-q_{C2}\cdot{x_2}-q_{C3}\cdot{x_3}\leq0$$Для любой другой переменной будет точно такая же формула, только в ней индексы у коэффициентов $q$ будут не $C$, а какие-то другие
Разберемся что тут что. Очевидно, что $x_A,x_B,x_C,x_1,x_2,x_3$ - переменные нашей задачи. Для нахождения коэффициентов $q$ будем использовать числа первой строки, так как именно там содержатся данные по нашей переменной $x_C$. Значение $q_C$ это просто дробная часть числа в строке $x_C$ и столбце свободных членов B. Значение этой клетки равно $\frac{19}{2}=9\frac{1}{2}$. Очевидно, что целая часть здесь 9, а дробная $\frac{1}{2}$. Следовательно, $q_C=\frac{1}{2}$.
- Значение коэффициента $q_{CA}$ это дробная часть числа, находящегося в строке $x_C$, столбце $x_A$. Там находится число 0, и очевидно, что его дробная часть также равна 0. $q_{CA}=0$
- Значение коэффициента $q_{CB}$ это дробная часть числа, находящегося в строке $x_C$, столбце $x_B$. Там находится число $\frac{1}{2}$, и очевидно, что его дробная часть также равна $\frac{1}{2}$. $q_{CB}=\frac{1}{2}$
- Значение коэффициента $q_{CC}$ это дробная часть числа, находящегося в строке $x_C$, столбце $x_C$. Там находится число 1, и очевидно, что его дробная часть равна 0. $q_{CC}=0$
- Значение коэффициента $q_{C1}$ это дробная часть числа, находящегося в строке $x_C$, столбце $x_1$. Там находится число $\frac{2}{5}$, и очевидно, что его дробная часть также равна $\frac{2}{5}$. $q_{C1}=\frac{2}{5}$
- Значение коэффициента $q_{C2}$ это дробная часть числа, находящегося в строке $x_C$, столбце $x_2$. Там находится число $-\frac{1}{10}$. Для отрицательных чисел дробная часть определяется немного не так, как для положительных, и равна разности нашего числа и следующего целого отрицательного числа, меньшего, чем нашего. Для числа $-\frac{1}{10}$ следующее меньшее целое отрицательное число это $-1$, и, следовательно, $q_{С2}=-\frac{1}{10}-(-1)=\frac{9}{10}$
- Значение коэффициента $q_{C3}$ это дробная часть числа, находящегося в строке $x_C$, столбце $x_3$. Там находится число 0, и очевидно, что его дробная часть также равна 0. $q_{C3}=0$
Подставив найденные коэффициенты, получим еще одно ограничение:
$$\frac{1}{2}-\frac{1}{2}\cdot{x_B}-\frac{2}{5}\cdot{x_1}-\frac{9}{10}\cdot{x_2}\leq0$$Однако это ограничение в виде неравенства, а у нас все ограничения в виде равенств. Поэтому превратим данное ограничение в равенство, добавив еще одну неотрицательную переменную $x_4$:
$$-\frac{1}{2}\cdot{x_B}-\frac{2}{5}\cdot{x_1}-\frac{9}{10}\cdot{x_2}+x_4=-\frac{1}{2}$$Занесем данное ограничение еще одной строкой в симплекс-таблицу, кроме того, не забудем, что появился новый столбец $x_4$, а также изменим знак последней строки - так всегда делается при начале работы по методу Гомори:
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | B | |
| $x_C$ | 0 | $\frac{1}{2}$ | 1 | $\frac{2}{5}$ | $-\frac{1}{10}$ | 0 | 0 | $\frac{19}{2}$ |
| $x_A$ | 1 | $\frac{1}{2}$ | 0 | $-\frac{1}{5}$ | $\frac{3}{10}$ | 0 | 0 | $\frac{13}{2}$ | $x_3$ | 0 | -1 | 0 | $\frac{1}{5}$ | $-\frac{4}{5}$ | 1 | 0 | 11 | $x_4$ | 0 | $-\frac{1}{2}$ | 0 | $-\frac{2}{5}$ | $-\frac{9}{10}$ | 0 | 1 | $-\frac{1}{2}$ |
| F | 0 | 0 | 0 | $-\frac{8}{5}$ | $-\frac{3}{5}$ | 0 | 0 | -83 |
Теперь продолжаем работать по практически обычному симплекс-методу. Правда теперь будет отличаться правило определения того, какую переменную необходимо убрать из базиса, а какую оставить. По правилам метода Гомори, убирать надо всегда только что введенную переменную, то есть, $x_4$. А вот чтобы определить, какую необходимо ввести, необходимо найти частные от деления значений последней строки (F) на значения предпоследней строки (так как именно в ней переменная $x_4$). Найдем эти частные (кроме только что введенной переменной $x_4$ и столбца B, а также тех столбцов, где приходится делить на ноль):
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | B | |
| $x_C$ | 0 | $\frac{1}{2}$ | 1 | $\frac{2}{5}$ | $-\frac{1}{10}$ | 0 | 0 | $\frac{19}{2}$ |
| $x_A$ | 1 | $\frac{1}{2}$ | 0 | $-\frac{1}{5}$ | $\frac{3}{10}$ | 0 | 0 | $\frac{13}{2}$ | $x_3$ | 0 | -1 | 0 | $\frac{1}{5}$ | $-\frac{4}{5}$ | 1 | 0 | 11 | $x_4$ | 0 | $-\frac{1}{2}$ | 0 | $-\frac{2}{5}$ | $-\frac{9}{10}$ | 0 | 1 | $-\frac{1}{2}$ |
| F | 0 | 0 | 0 | $-\frac{8}{5}$ | $-\frac{3}{5}$ | 0 | 0 | -83 |
| $\frac{F}{x_4}$ | - | 0 | - | 4 | $\frac{2}{3}$ | - | - | - |
Наименьшее значение мы получили для столбца с переменной $x_B$ - 0. Следовательно именно переменную $x_B$ необходимо ввести в базис. Определяем, какое число стоит на пересечении строки $x_4$ и столбца $x_B$ - это число $-\frac{1}{2}$. Поэтому делим всю строку $x_4$ на это число:
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | B | |
| $x_C$ | 0 | $\frac{1}{2}$ | 1 | $\frac{2}{5}$ | $-\frac{1}{10}$ | 0 | 0 | $\frac{19}{2}$ |
| $x_A$ | 1 | $\frac{1}{2}$ | 0 | $-\frac{1}{5}$ | $\frac{3}{10}$ | 0 | 0 | $\frac{13}{2}$ | $x_3$ | 0 | -1 | 0 | $\frac{1}{5}$ | $-\frac{4}{5}$ | 1 | 0 | 11 | 0 | 1 | 0 | $\frac{4}{5}$ | $\frac{9}{5}$ | 0 | -2 | 1 |
| F | 0 | 0 | 0 | $-\frac{8}{5}$ | $-\frac{3}{5}$ | 0 | 0 | -83 |
Из четвертой строки исчезло название строки - $x_4$. Это потому, что $x_4$ - больше не базисная переменная. Нам же необходимо, чтобы базисной стала переменная $x_B$. Первое требование к базисным переменным для нее выполняется - есть столбец $x_B$, и у него в четвертой строке число 1. Но вот остальные числа не равны нулю. Так давайте их сделаем такими.
- Чтобы в первой строке, в столбце $x_B$ число $\frac{1}{2}$ превратить в ноль, вычтем из первой строки четвертую, умноженную на $\frac{1}{2}$.
- Чтобы во второй строке, в столбце $x_B$ число $\frac{1}{2}$ превратить в ноль, вычтем из второй строки четвертую, умноженную на $\frac{1}{2}$
- Чтобы в третьей строке, в столбце $x_B$ число $-1$ превратить в ноль, добавим к третьей строке четвертую
- Последнюю строку не трогаем, так как в последней строке, столбце $x_B$ и так ноль
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | B | |
| $x_C$ | $0-\frac{1}{2}\cdot0$ | $\frac{1}{2}-\frac{1}{2}\cdot1$ | $1-\frac{1}{2}\cdot0$ | $\frac{2}{5}-\frac{1}{2}\cdot\frac{4}{5}$ | $-\frac{1}{10}-\frac{1}{2}\cdot\frac{9}{5}$ | $0-\frac{1}{2}\cdot0$ | $0-\frac{1}{2}\cdot(-2)$ | $\frac{19}{2}-\frac{1}{2}\cdot1$ |
| $x_A$ | $1-\frac{1}{2}\cdot0$ | $\frac{1}{2}-\frac{1}{2}\cdot1$ | $0-\frac{1}{2}\cdot0$ | $-\frac{1}{5}-\frac{1}{2}\cdot\frac{4}{5}$ | $\frac{3}{10}-\frac{1}{2}\cdot\frac{9}{5}$ | $0-\frac{1}{2}\cdot0$ | $0-\frac{1}{2}\cdot(-2)$ | $\frac{13}{2}-\frac{1}{2}\cdot1$ | $x_3$ | 0+0 | -1+1 | 0+0 | $\frac{1}{5}+\frac{4}{5}$ | $-\frac{4}{5}+\frac{9}{5}$ | 1+0 | 0-2 | 11+1 | $x_B$ | 0 | 1 | 0 | $\frac{4}{5}$ | $\frac{9}{5}$ | 0 | -2 | 1 |
| F | 0 | 0 | 0 | $-\frac{8}{5}$ | $-\frac{3}{5}$ | 0 | 0 | -83 |
Проводим математические действия и получаем итоговую таблицу.
| $x_A$ | $x_B$ | $x_C$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | B | |
| $x_C$ | 0 | 0 | 1 | 0 | -1 | 0 | 1 | 9 |
| $x_A$ | 1 | 0 | 0 | $-\frac{3}{5}$ | $-\frac{3}{5}$ | 0 | 1 | 6 | $x_3$ | 0 | 0 | 0 | 1 | 1 | 1 | -2 | 12 | $x_B$ | 0 | 1 | 0 | $\frac{4}{5}$ | $\frac{9}{5}$ | 0 | -2 | 1 |
| F | 0 | 0 | 0 | $-\frac{8}{5}$ | $-\frac{3}{5}$ | 0 | 0 | -83 |
Проверяем, получили ли мы целочисленное решение. Да, получили. Мы получили решение $x_A=6,x_B=1,x_C=9$, причем значение целевой функции (правая нижняя клетка таблицы с противоположным знаком) равно 83, что, кстати, совпадает со значением целевой функции в исходной (нецелочисленной) задачи. Поэтому, можно сказать, что переход к целочисленности не изменяет значения дохода фирмы. Так, однако бывает не всегда, и чаще всего доход фирмы при переходе к целочисленности немного падает.
Выводы
Так как мы получили целочисленное решение, то задача решена. Если бы какие-то из переменных снова были бы нецелочисленными, процесс нужно было бы повторить - найти одну из нецелочисленных переменных, составить для нее дополнительное ограничение, получив еще одну вспомогательную переменную, а затем сделать шаг симплекс-метода, уберя ее из базиса. После какого-то шага мы бы точно получили целочисленное решение (как и в этом случае).
Мы научились решать производственную задачу, и умеем выдавать такой результат, который обеспечивает максимальную прибыль. Однако при этом мы совсем не учитываем остатки на складах. То есть, мы конечно гарантируем, что используем не больше ресурсов, чем есть, однако вполне возможно, что на складах останутся излишки. Что обычно делают предприятия, если у них на складах образуются излишки ресурсов? На самом деле, можно много чего сделать:
- Можно их продать, и тем самым повысить прибыль (целевую функцию);
- Можно поменять одни ресурсы на другие (если такое возможно), и, может быть, тогда прибыль увеличится;
- Можно обдумать выпуск нового товара, который потребляет как раз тот ресурс, которого у нас излишек. Может быть, тогда наша прибыль увеличится.
Обычное решение производственной задачи не дает ответов на вопросы подобного рода. Однако существуют методы, позволяющие получить такие ответы. Один из этих методов - решение "двойственной" задачи. Его мы рассмотрим в следующем разделе.
