Каждому из неравенств (6.7) на графике рис
6.1 соответствует полуплоскость, в пределах которой находятся все допустимые данным неравенством значения переменной величины Xj (j = 1, 2,..., 6).
(6.6)
Рис. 6.1.
х.
Так, неравенству х1 > 0 соответствует полуплоскость вправо от оси х2 (граница ее заштрихована).
Неравенству х3 = 8хх + 12х2 — 16 > 0 соответствует полуплоскость вправо и вверх от линии граничного значения данного неравенства (при х3 = 0). Уравнение этой линии
х, +3 / 2х2 -2=0.
Таким же образом можно построить границы, определяемые другими уравнениями.
Неравенствам (6.7) соответствует некоторая область — шести-угольник ABCDEF, образованный границами упомянутых выше полуплоскостей. Эта область может быть названа областью допустимых планов, поскольку любая точка в ее пределах отвечает требованиям наложенных ограничений (6.3).
Из всех допустимых планов нас интересует оптимальный план, при котором функция цели у достигает минимума.
Целевой функции соответствует семейство параллельных прямых. Рассмотрим одну из них, проходящую через начало координат, что будет иметь место при у = 22,8. При этом х2 = Зх,.
Интересующая нас прямая у = 22,8, как видно из рис. 6.1, имеет наклон вправо от оси х2. Задаваясь различными значениями у, получим семейство прямых линий, параллельных прямой у = 22,8, проходящей через точку 0. При этом чем меньше будет значение у, тем, очевидно, правее будет располагаться соответствующая прямая.
Поскольку мы добиваемся минимального значения у, то нас будет интересовать прямая, расположенная в наибольшем удалении вправо от прямой у = 22,8 и проходящая через многоугольник ABCDEF, — прямая ymil1.
Единственной точкой, соответствующей оптимальному плану, будет та вершина многоугольника ABCDEF (рис. 6.1), которая одновременно принадлежит области допустимых планов и отвечает требованию минимизации целевой функции у, — вершина С. Из уравнения прямой ВС, проходящей через точку С, следует, что Л", = 4. Из уравнения прямой DC, проходящей через ту же точку, следует, что х2 = 0.
Подставляя полученные значения х1 = 4 и х2 = 0 в уравнения (6.5), определим величины остальных переменных, составляющих оптимальный план:
х3 = 16; х4 = 0; х5 = 10;
х6 = 8.
Таким образом, оптимальный план будет следующим:
= 4;
х2 = 0;
*3 = 16;
X, = 0;
х5 = 10;
*6 = 8.
Линейная форма величины издержек при этом будет минимальной:
24 . 8 „ 228 132 ,, /сп\
у = ——х4+ — х0+ = = 13,2. (6.9)
10 10 10 10
На практике встречается ряд задач, аналогичных рассмотренному примеру, но требующих максимизации целевой функции (например, величины дохода или прибыли).
При решении этих задач целевая функция рассчитывается по формуле, аналогичной (6.2):
/ = С1Х1 +С2Х2 +...+С]Х] +с*х„, (6.10)
где у — целевая функция, подлежащая максимизации. Отличие заключается в том, что знаки перед всеми постоянными коэффициентами меняются на обратные (с* = - с*).
Вычислительные методы линейного программирования
Рассмотренная геометрическая интерпретация задачи линейного программирования возможна лишь при наличии двух независимых переменных. При трех переменных наглядное представление существенно усложняется, так как в этом случае имеет место некоторый выпуклый многогранник в трехмерном пространстве, соответствующий объему допустимых планов.
При количестве переменных более трех задача теряет геомет-рическую наглядность, так как трудно представить себе, например, четырехмерное пространство. Однако идея получения решения, рассмотренного выше, сохраняет смысл и для случая многомерного пространства.
На основе этой идеи создан и разработан один из основных методов решения задач линейного программирования — так называемый симплекс-метод.
Симплекс-метод является алгебраической формой решения задачи линейного программирования, вытекающей из только что рассмотренного геометрического представления. При обосновании симплекс-метода будем прибегать к уже рассмотренному выше двухмерному случаю, что позволит достаточно просто перейти от геометрического представления к его алгебраической аналогии.
Первый шаг. Найти допустимый план, соответствующий одной из вершин области допустимых планов.
Второй шаг. Проверить, оптимален ли найденный план. Если оптимален, вычисления окончены. Если нет — следующий план.
Третий шаг. Переход к другой вершине (другому допустимому плану), в которой значение целевой функции меньше, проверка его на оптимальность и т. д.
Поэтому первым шагом должно быть получение координат одной из вершин многоугольника (многогранника) допустимых планов. Для этого необходимо преобразовать систему уравнений таким образом, чтобы с ее помощью можно было легко получать координаты вершин многоугольника (многогранника) области допустимых планов.
Анализируя рис. 6.1, можно заметить, что в каждой из вершин две из переменных обращаются в нуль. Поэтому мы должны принять две переменные равными нулю, а затем найти остальные четыре из системы уравнений (6.3). В совокупности все переменные дадут один из допустимых планов, соответствующих некоторой вершине.
Чтобы преобразовать систему уравнений описанным образом, необходимо выразить каждую из неизвестных хь х2, ..., хт через остальные.
(6.11)
Такая возможность существует лишь в случае, если определитель:
/
«11 «12 • • «1,„ 4
«21 «22 • «2,„
V «иг 1 «,„2 • ^тп у
Если это условие выполняется, то величины хь х2, ..., хт называют базисными. Каждый базис соответствует определенной вершине.
Преобразуем систему уравнений (6.3) так, чтобы, приравнивая две переменные нулю (например, х5 = 0, х6 = 0), можно было получить значение базисных величин хь х2, х3 и х4 — координаты одной из вершин многоугольника.
Предварительно убедимся, что определитель, составленный из коэффициентов при этих неизвестных в уравнениях (6.3), не равен нулю.
Действительно,
11
о 2 0,
Это дает нам право считать, что величины хь х2, х3 и х4 являются базисными и система (6.3) может быть разрешена относительно их.
Все необходимые преобразования будем производить с матрицей коэффициентов уравнений (6.3):
161 10 76 24
О 2 О 3
1
О 2 О
(6.12)
