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

Пусть математическая модель задачи имеет вид: целевая функция:

Т = X! - х2 —> гпах;

система ограничений:

-2х, 2 < 2; х, - 2 < 2; х, 2 < 5.

Добавим новые переменные (х3, х4, х5) и запишем ограничения в виде равенств

-2Х] + х2 + х

з

х, - 2х2 + х4 = 2;

х, + х2 + х5 = э.

Систему равенств разрешаем относительно переменных: х3, х4, х5, которые выбираем в качестве базисных. Тогда переменные: х15 х2 будут свободными.

х3 = 2 + 2Х| - х2; х4 = 2 -Х| + 2х2; х5 = 5 - х, - х2.

При значениях X! =х2= 0 базисные переменные удовлетворяют условию неотрицательности. Чтобы проиллюстрировать решение за-

дачи в двухмерном пространстве на плоскости в координатах свободных переменных: х,, х2, построим прямые х3, х4, х5, задавая соответственно х3 = 0, х4 = 0, х5 = 0 (рис. 4.9). В результате получим многоугольник ос1^ базисных решений, вершины которого представляют опорные базисные решения, причем в каждой вершине многоугольника сразу две базисные переменные равны нулю. Линия целевой функции / проходит под углом 45°, так как коэффициенты при свободных переменных х, и х2 равны.

Схема построения многоугольника базисных решений

Рис. 4.9. Схема построения многоугольника базисных решений

Координаты вершины Ь многоугольника odcbg соответствуют гпах /, = 4—1 = 3.

 
< Пред   СОДЕРЖАНИЕ     След >