Ее начальный опорный план будет иметь вид

X0 = (0; 0; K; 0; b1; b2 ; K; bm ) ,

1442443

n

w(X0 ) = −b1 −b2 −K−bm .

Замечание. Если некоторые из ограничительных уравнений системы имеют предпочтительный вид (т.е. содержат базисную переменную), то искусственные переменные в них не вводят (что упрощает решение задачи).

1.4. Геометрическая интерпретация и графическое решение задач линейного программирования

Рассмотрим задачу линейного программирования симметричного вида относительно двух переменных:

1.Любое из неравенств (1.14) на плоскости Ох1х2 определяет некоторую полуплоскость.

2.Система неравенств (1.14)−(1.15) определяет выпуклое множество (выпуклый многоугольник, неограниченную выпуклую многоугольную область, пустую область или точку), которое совпадает с многогранником решений D.

16

1.4.2. Геометрическая интерпретация целевой функции

При изменении z получают семейство параллельных прямых, назы-

ваемых линиями уровня.

2. Вектор коэффициентов целевой функции c = (c1; c2 ) называется градиентом функции. Он перпендикулярен линиям уровня.

наибольшего убывания целевой функции.

1.4.3. Графическое решение задач линейного программирования

Суть графического метода решения задач ЛП основывается на следующих утверждениях:

1) совокупность опорных планов задачи ЛП совпадает с системой вершин многогранника решений;

2) целевая функция достигает оптимального значения в вершине многогранника решений.

Для практического решения задачи (1.13) – (1.15) необходимо: 1) построить с учетом системы ограничений область допустимых

решений D (многогранник планов);r 2) построить вектор градиента c ;

3)построить перпендикулярно к нему в области допустимых решений одну из прямых семейства z = const;

4)искомая точка экстремума Xopt найдется параллельным пе-

ремещением вспомогательной прямой z = const в направлении вектора cr (если ищется zmax ) и в направлении вектора − c (если

ищется zmin );

5) координаты точки Xopt можно определить, решив совместно уравнения прямых, пересекающихся в этой точке, или по чертежу.

17

Замечание. Если оптимальное значение целевая функция принимает более чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой линейной

комбинацией этих вершин. Выпуклой линейной комбинацией точек X1 , X2 , …, Xk

1.4.4. Задача со многими переменными

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

1)выделить некоторый базис переменных в системе ограничительных уравнений;

2)опустить базисные переменные и перейти к эквивалентной системе неравенств;

3)выразить целевую функцию через свободные переменные;

4)полученную двумерную задачу рушить обычным графическим способом;

5)найдя две координаты оптимального решения, подставить их

вограничительные уравнения и определить остальные координаты оптимального плана.

Пример 4. Решить задачу линейного программирования из примера 1 графическим способом:

z = 3x1 + 2x2 + x3 → max ,

xj ≥ 0, j =1,3.

Решение. Это задача с тремя переменными. Ее можно решить графически, если в канонической или симметричной записи будет присутствовать не более двух свободных переменных. Приведем данную задачу к симметричному виду. Для этого из 2-го уравнения

выразим базисную переменную x3 :

x3 = 4 − x1 ,

18

подставим ее значение в целевую функцию:

z = 3x1 + 2x2 + x3 = 3x1 + 2x2 + 4 − x1 = 2x1 + 2x2 + 4 → max .

Так как x3 ≥ 0 , то 4 − x1 ≥ 0 , что равносильно неравенству

x1 ≤ 4 . Следовательно, система ограничений примет следующий симметричный вид:

Полученную двумерную задачу решим обычным графическим способом.

1. Так как x1 ≥ 0 , x2 ≥ 0 , то область допустимых решений будет находиться в первой координатной четверти. На плоскости Ox1x2 (рис. 1.1) построим прямые, порождаемые уравнениями:

зок длиной b.)

2. Относительно каждой прямой определим полуплоскость, соответствующую исходным неравенствам

19

Чтобы определить полуплоскость, соответствующую 1-му нера-

x1 +2x2 ≤12 ( 0 + 2 0 ≤ 12 0 ≤ 12 ). Если неравенство выполняется, то точка принадлежит данной полуплоскости, в противном

начала (0; 0) и конца (2; 2) стрелкой. Перпендикулярно к нему построим одну из прямых семейства z = 2x1 +2x2 +4 = const . На-

пример, при x1 = x2 =1 получим z = 8. Заметим, что эта прямая параллельна l3 : 2x1 +2x2 =14 .

4. Вспомогательную прямую z = 8 будем параллельно перемещать в направлении вектора c (так как ищется zmax ) до последней точки пересечения с областью допустимых решений D. В нашем случае прямая zmax совпадает с прямой l3 : 2x1 +2x2 =14 . Поэто-

= (2; 5; 2);

20

2) для Xopt2 = (4; 3) получим: x3 = 4 − x1 = 4 −4 = 0 Xopt2 = = (4; 3; 0).

Рис. 1.1

5. Для аналитической записи любого оптимального решения Xopt необходимо составить выпуклую линейную комбинацию

21