Задача 5.1.
F = 2x1 + 3x2
max при ограничениях:x1 + Зx2 <= 18,
2x1 + x2 <= 16,
x2 <= 5,
3x1 <= 21,
Рис. 5.2
Решение. С помощью дополнительных неотрицательных переменных перейдем к
системе уравнений. В данном случае все дополнительные переменные вводятся
со знаком "плюс", так как все неравенства имеют вид "<=
" [см. систему ограничений (1.26)].
Получим систему ограничений в виде:
x1 + Зx2 +x3 = 18,
2x1 + x2 +x4 = 16,
x2 +x5 = 5,
3x1 +x6 = 21,
Для нахождения первоначального базисного решения разобьем переменные на две
группы - основные и неосновные. Так как определитель, составленный из
коэффициентов при дополнительных переменных x3, x4,
x5, x6, отличен от нуля, то
эти переменные можно взять в качестве основных на первом шаге решения задачи.
При выборе основных переменных на первом шаге не обязательно составлять
определитель из их коэффициентов и проверять, равен ли он нулю.
Достаточно воспользоваться следующим правилом:
|
В качестве основных переменных на первом шаге следует выбрать (если возможно)
такие m переменных, каждая из которых входит только в одно из m
уравнений системы ограничений, при этом нет таких уравнений системы, в которые
не входит ни одна из этих переменных. |
Дополнительные переменные удовлетворяют этому правилу. Если выбранные по этому
правилу переменные имеют те же знаки, что и соответствующие им свободные члены
в правых частях уравнений, то полученное таким образом базисное решение будет
допустимым. В данном случае так и получилось.
I ш а г . Основные переменные: x3, x4, x5,
x6.
Неосновные переменные: x1, x2.
Выразим основные переменные через неосновные:
x3 = 18 - x1 - З x2
x4 = 16 - 2 x1 - x2,
x5 = 5 - x2 (5.3)
x6 = 21 - 3x1
Положив неосновные переменные равными нулю, т.е. x1 =
0, x2 = 0, получим базисное решение Х1 = (0; 0;
18; 16; 5; 21), которое является допустимым и соответствует вершине 0(0;0)
многогранника OABCDE на рис. 5.2. Поскольку это решение допустимое,
нельзя отбросить возможность того, что оно оптимально. Выразим линейную
функцию через неосновные переменные:
F = 2 x1 + З x2. При решении X1
значение функции равно f(X 1).
Легко понять, что функцию F можно увеличить за счет увеличения
любой из неосновных переменных, входящих в выражение для F c
положительным коэффициентом. Это можно осуществить, перейдя к такому новому
допустимому базисному решению, в котором эта переменная будет основной, т.е.
принимать не нулевое, а положительное значение (если новое решение будет
вырождено, то функция цели сохранит свое значение). При таком переходе одна
из основных переменных перейдет в неосновные, а геометрически произойдет
переход к соседней вершине многоугольника, где значение линейной функции
"лучше" (по крайней мере "не хуже"). В данном примере
для увеличения F можно переводить в основные либо x1,
либо x2, так как обе эти переменные входят в выражение для
F со знаком "плюс". Для определенности в такой ситуации будем
выбирать переменную, имеющую больший коэффициент, т.е. в данном случае
x1 (такое правило выбора не всегда дает наименее трудоемкое
решение, иногда имеет смысл провести предварительные специальные оценки).
Система (5.3) накладывает ограничения на рост переменной x2.
Поскольку необходимо сохранять допустимость решений, т.е. все переменные
должны оставаться неотрицательными, то должны выполняться следующие
неравенства (при этом x1 = 0 как неосновная переменная):
x3 = 18 - З x2 >=
0, откуда x2 <=
18/3.
x4 = 16 - x2 >=
0, откуда x2 <=
16/1.
x5 = 5 - x2 >=
0, откуда x2 <=
5/1.
X6 = 21 - x1, (5.3)
Каждое уравнение системы (5.3), кроме последнего, определяет оценочное
отношение - границу роста переменной x2, сохраняющую
неотрицательность соответствующей переменной. Эта граница определяется
абсолютной величиной отношения свободного члена к коэффициенту при
x2 при условии, что эти числа имеют разные знаки. Последнее
уравнение системы не ограничивает рост переменной x2, так
как данная переменная в него не входит (или формально входит с нулевым
коэффициентом). В этом случае условимся обозначать границу символом
.
Такой же символ будем использовать, когда свободный член и коэффициент при
переменной в уравнении имеют одинаковые знаки, так как и в этом случае нет
ограничений на рост переменной.
Не накладывает ограничений на рост переменной, переводимой в основные, и такое
уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая
переменная имеет положительный коэффициент. И в этом случае граница
обозначается символом .
Обратите внимание, что при нулевом свободном члене и отрицательном
коэффициенте при переводимой переменной уравнение ограничивает рост этой
переменной нулем. (любое положительное ее значение вносит отрицательную
компоненту в следующее базисное решение.
Очевидно, что сохранение неотрицательности всех переменных (допустимость
решения) возможно, если не нарушается ни одна из полученных во всех уравнениях
границ. В данном примере наибольшее возможное значение для переменной
x2 определяется как x2 = min {18/3; 16/1; 5/1;
} = 5. При x2 = 5 переменная x5 обращается в
нуль и переходит в неосновные.
Уравнение, где достигается наибольшее возможное значение переменной,
переводимой в основные (т.е. где оценка минимальна), называется
разрешающим. В данном случае - это третье уравнение. Разрешающее
уравнение будем выделять рамкой в системе ограничений.
II шаг. Основные переменные: x2, x3,
x4, x6. Неосновные переменные: x1,
x5.
Выразим новые основные переменные через новые неосновные, начиная с
разрешающего уравнения (его используем при записи выражения для
x2):
x3 = 18- x1 - 3(5 - x5),
x4 = 16- 2x1 - (5 - x5),
x6 = 21 - 3x1,
или
x3 = 3 - x1 + 3x5,
x4 = 11- 2x1 + x5,
x6 = 21 - 3x1,
Второе базисное решение X2 = (0; 5; 3; 11; 0; 21) является допустимым и
соответствует вершине А (0;5) на рис. 5.2. Геометрическая интерпретация
перехода от Х1 к X2 ~ переход от вершины
О к соседней вершине А на многоугольнике решений OABCDE.
Выразив линейную функцию через неосновные переменные на этом шаге,
получаем:
F = 2 x1 + 3 x2 = 2 x1 +
3(5 - x5) = 15 + 2 x1 - 3 x5.
Значение линейной функции F2 = F(X2) = 15.
Изменение значения линейной функции легко определить заранее как произведение
наибольшего возможного значения переменной, переводимой в основные, на ее
коэффициент в выражении для линейной функции; в данном случае
F1=5*3=15,
F2 = F1 + F1
=0 + 15=15.
Однако значение F2 не является максимальным, так как повторяя
рассуждения I шага, обнаруживаем возможность дальнейшего увеличения линейной
функции за счет переменной x1, входящей в выражение для F с
положительным коэффициентом. Система уравнений (5.4) определяет наибольшее
возможное значение для x1: x1 =
min{
; 3/1; 11/2; 7} = 3. Второе уравнение является разрешающим, переменная x3
переходит в неосновные, при этом D
F1=3*2=6.
III шаг. Основные переменные: x1, x2,
x4, x6. Неосновные переменные:
x3, x5.
Как и на II шаге, выражаем новые основные переменные через новые
неосновные, начиная с разрешающего уравнения (его используем при записи
выражения для x1). После преобразований получаем:
Базисное решение X3 = (3; 5; 0; 5; 0; 12) соответствует
вершине В (3,5). Выражаем линейную функцию через неосновные переменные:
F = 2x1 + Зx2 = 2(3 - x3 + Зx5)
+ 3(5 - x5) = 21 - 2x3+ 3
x5, F3 = F(X3) = 21. Проверяем:
F3 - F2 = 21 - 15 = 6 = D
F2. Третье допустимое базисное решение тоже не является
оптимальным, поскольку при неосновной переменной х5 в
выражении линейной функции через неосновные переменные содержится
положительный коэффициент. Переводим х5 в основную
переменную. При определении наибольшего возможного значения для
х5 следует обратить внимание на первое уравнение в системе
(5.5), которое не дает ограничений на рост х5,
так как свободный член и коэффициент при х5 имеют одинаковые
знаки. Поэтому х5 =
min{
; 5; 1; 12/9} = 1. Третье уравнение является
разрешающим, и переменная х4 переходит в неосновные;
D
F3 = 1 * 3 = 3.
IV шаг. Основные переменные: x1, х2,
х5, х6. Неосновные переменные:
х3, х4.
После преобразований получим:
x1 = 6 + x3/5 - 3x4/5,
x2 = 4 - 2x3/5 + x4/5,
x5 = 1 + 2x3/5 - x4/5,
x6 = 3 - 3x3/5 + 9x4/5,
Базисное решение Х4 = (6; 4; 0; 0; 1; 3)
соответствует вершине С(6; 4) на рис. 5.2.
Линейная функция, выраженная через неосновные переменные, имеет вид:
F = 24 - 4x3/5 - 3x4/5. Это выражение не
содержит положительных коэффициентов при неосновных переменных, поэтому
значение F4 = F(X4) = 24 максимальное. Функцию F
невозможно еще увеличить, переходя к другому допустимому базисному решению,
т.е. решение Х4 оптимальное. Вспоминая экономический смысл
всех переменных, можно сделать следующие выводы.
Прибыль предприятия принимает максимальное значение 24 руб. при реализации
6 единиц продукции Р1(x1 = 6) и 4 единиц
продукции P2(x2 = 4).
Дополнительные переменные x3, х4,
х5, х6 показывают разницу между
запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов.
При оптимальном плане производства x3 = x4 = 0, т.е.
остатки ресурсов S1 и S2 равны нулю, а
остатки ресурсов S3 и S4 равны
соответственно 1 и 3 единицам.