Приведем задачу к каноническому виду

Необходимо перейти от системы неравенств к системе уравнений.

Для этого необходимо ввести новые переменные.

Система (5) преобразуется:

 

x₁+ x₂*3+x₃=1800

x₁+ x₂+x₄=1000               

x₁+ x₂*2+x₅=1500    (8)

x₁+ x₂-x₆=700

x_i≥0 i=1..6

 

Найдем базисные и опорные решения

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n-m неосновных переменных равны нулю. Число базисных решений ограниченно C^m_n. В нашем случае m=4 n=6. Максимальное число базисных решений равно 15. Базисные решения находятся занулением неосновных переменных и последующим решением получившихся систем уравнений.

Набор X Базисное решение

x₁x₂x₃x₄ ⁽¹⁾     (-100;800;-500;300;0;0)

x₁x₂x₃x₅ ⁽²⁾     линейная зависимость

x₁x₂x₃x₆ ⁽³⁾     (500;500;-200;0;0;300)

x₁x₂x₄x₅ ⁽⁴⁾     (150;550;0;300;250;0) F=3050

x₁x₂x₄x₆ ⁽⁵⁾     (900;300;0;-200;0;500)

x₁x₂x₅x₆ ⁽⁶⁾     (600;400;0;0;100;300) F=3200

x₁x₃x₄x₅ ⁽⁷⁾ (700;0;1100;300;800;0) F=1400

x₁x₃x₄x₆ ⁽⁸⁾     (1500;0;300;-500;0;800)                       (9)

x₁x₃x₅x₆ ⁽⁹⁾     (1000;0;800;0;500;300) F=2000

x₁x₄x₅x₆ ⁽¹⁰⁾    (1800;0;0;-800;-300;1100)

x₂x₃x₄x₅ ⁽¹¹⁾    (0;700;-300;300;100;0)

x₂x₃x₄x₆ ⁽¹²⁾    (0;750;-450;250;0;50)

x₂x₃x₅x₆ ⁽¹³⁾    (0;1000;-1200;0;-500;300)

x₂x₄x₅x₆ ⁽¹⁴⁾    (0;600;0;400;300;-100)

x₃x₄x₅x₆ ⁽¹⁵⁾    (0;0;1800;1000;1500;-700)

Найдем опорные решения. Базисное решение называется опорным, если оно допустимое при данных условиях. В нашем случае, все значения переменных должны быть ≥0.

Этому условию удовлетворяют следующие выборы:

 ⁽⁴⁾  (150;550;0;300;250;0) F=3050

 ⁽⁶⁾ (600;400;0;0;100;300) F=3200  (10)

 ⁽⁷⁾ (700;0;1100;300;800;0) F=1400

 ⁽⁹⁾ (1000;0;800;0;500;300) F=2000

 

Они являются опорными решениями. Обозначим эти точки на графике. (Рис 2.) Видим, что эти точки ограничивают область значений, образованную пересечениями линий ограничения.

Рис. 2. Опорные решения

 

Критерий F Достигает максимального значения 3200 на наборе ⁽⁶⁾ (600;400;0;0;100;300) При x₁=600; x₂=400

А значит, что графически задача была решена правильно!

Изменение основных переменных

Преобразуем систему (8) сделав основными переменными x₄ и x₅ . Для этого необходимо в каждой строчке системы (8) оставить по одной переменной: x₁,x₂,x₃,x₆ с единичными коэффициентами, а остальные переменные выразить через x₄,x₅

 

Получим:

x₁+2*x₄-x₅=500

x₂-x₄+x₅=500

-x₃-x₄+2*x₅=200            (11)

-x₆+x₄=300

x_i≥0 i=1..6

 

Систему (11) можно преобразовать в систему неравенств:

2*x₄-x₅≤500

-x₄+x₅≤500

-x₄+2*x₅≥200 (12)             x₄≥300

x_i≥0 i=1..6

 

F=3500+x₄-3*x₅  (13)

 

(3)

Оптимальная точка также является опорная точка (6) из системы (10). Следовательно, при замене основных переменных решение оптимизационной задачи остается тем же.

Выводы

 

1) Область допустимых решений – выпуклое множество

2) Это многоугольник (многогранник)

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

4) Базисное решение системы m линейных уравнений с n переменными – частное решение системы, в которой все n-m неосновных переменных равны нулю. В нашем случае m=4 n=6.

5) Вижу, что опорное решение (базисное решение (6)) совпадает с угловой точкой (см. Рис 2, Рис 3)

6) Количество базисных решений не превышает числа сочетаний из числа переменных n по числу ограничений m =C^m_n. В нашем случае ≤ C⁴₆ =15

7) Базисных решений может быть меньше в следующих случаях:

 

а) Если границы полуплоскости параллельны. Не всякие переменные можно выразить, если вектора условий линейно зависимы, определитель матрицы =0. Система решений не имеет.

 

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

На границе каждой полуплоскости одна из переменных обращается в 0.

Порядок печати:

 

1) 1;2-1;9;

 

2) 6;3-4;5;

 

3) 1;7-8;1;