Задач линейного программирования

с п переменными

Графическим методом можно решить задачи линейного программирования, имеющие каноническую форму и удовлетворяющие условию n - r ≤ 2,

где п— число неизвестных системы;

r — ранг системы векторов-условий (число линейно независимых уравнений системы).

Если уравнения системы ограничений линейно независимы, то r = т,

где т — число уравнений.

Рассмотрим алгоритм метода на конкретном примере.

Пример. Решить графическим методом задачу

F(X)=x ₁+ x ₂+5 x ₃+3 x ₄→ max

Решение. Проверяем, применим ли графический метод при решении данной задачи.

Нетрудно видеть, что любые два из векторов-условий, например линейно независимы, так как их координаты непропорциональны.

Поэтому ранг системы векторов-условий r= 2.

Находим п – r = 4 - 2= 2 ≤ 2. Следовательно, метод применим.

Приведем систему уравнений-ограничений к равносильной, с помощью линейных преобразований, предварительно записав её в матричной форме:

.

Таким образом, получили систему: .

Выразим переменные х ₁ и х ₂:

х ₂=4-2 х ₃- х ₄

х ₁=9-2 х ₂-3 х₃ -3 х ₄=9-2(4-2 х ₃- х ₄)-3 х₃ -3 х ₄=9-8+4 х ₃+2 х ₄ -3 х₃ -3 х ₄=1+ х₃ - х ₄

Т.к. х ₁≥0 и х ₂≥0, то систему уравнений мы записываем в виде системы неравенств:

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

F (X)= 1+ х₃ - х ₄+4-2 х ₃- х ₄+5 х ₃+3 х ₄=

=5+4 х ₃+ х ₄ → max

,

х ₃≥0, х ₄≥0.

Изобразим на плоскости систему координат О х ₁ х ₂ и построим граничные прямые области допустимых решений.

Находим оптимальное решение эквивалентной задачи и соответствующее ему максимальное значение целевой функции: С (2,0), F (C)=5+4·2+0=13.

Используем систему ограничений исходной задачи, приведенную к каноническому виду, и оптимальное решение задачи с двумя переменными для нахождения оптимального решения исходной задачи:

х ₂=4-2 х ₃- х ₄=4-2·2-0=0,

х ₁=1+ х₃ - х ₄=1+2-0=3.

Следовательно,

X= (3,0,2,0);

F (X)=3+0+5·2+3·0=13.

Ответ: max F (X)= 13, при X= (3,0,2,0).