 |
 |
 |
 |
|
 |
 |
14
неограниченный многогранник, а поведение целевой функции будет характеризоваться поверхностями
(плоскостями) уровня.
Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается
полезным. В частности, он может быть применен не только к задачам с двумя переменными и
ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых n - m = 2, где n —
количество переменных, а m — ранг матрицы А.
Действительно, можно выбрать две произвольные переменные х
j1
,x
j2
и, используя систему уравнений,
выразить через них остальные переменные
где
?
j
(x
j1
, x
j2
) —линейные функции.
Подставив выражения (1.9) в целевую функцию, мы получим эквивалентную задачу
при ограничениях
Последняя ЗЛП может быть решена графически.
1.2.3. Основные теоремы линейного программирования. Рассмотрим некоторые теоремы.
Отражающие фундаментальные свойства задач линейного программирования и лежащие в основе
методов их решения. Они по существу обобщают на случай задач с произвольным количеством
переменных те свойства, которые мы наблюдали в двумерном случае.
Теорема 1.1. Если целевая функция f принимает максимальное значение в некоторой точке
множества допустимых планов D, то она принимает это значение и в некоторой угловой точке
данного множества.
Доказательство.
Чтобы не усложнять изложение, ограничимся тем случаем, когда множество D ограничено, и,
следовательно, является выпуклым многогранником.
Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых
множеств:
Если D — замкнутое ограниченное выпуклое множество, имеющее конечное число угловых точек,
то любая точка х ? D может быть представлена в виде выпуклой комбинации угловых точек D*.
* Строгое доказательство данного утверждения см., например, в [14].
Пусть х¹, х²,…,х
m
— угловые точки множества
D, а х*
— точка, в которой целевая функция f
достигает максимума.
На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой