Обобщение графического метода решения задач линейного программирования

Вообще, с помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если N и M связаны соотношением N — M = 2.

Действительно, пусть поставлена задача линейного программирования.

Найти минимальное значение линейной функции Z = С1×1+С2×2+… +СNxN при ограничениях.

a11×1 + a22×2 + … + a1NХN = b1.

(2.3)a21×1 + a22×2 + … + a2NХN = b2.

.. .. .. .. .. .. .. .

aМ1×1 + aМ2×2 + … + aМNХN = bМ.

xj 0 (j = 1, 2, …, N).

где все уравнения линейно независимы и выполняется cоотношение N — M = 2.

Используя метод Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х1, х2, …, хM, а свободными — два последних: хМ+1, и хN, т. е. система ограничений приняла вид.

x1 + a1, М+1xМ+1 + a1NХN = b1.

x2 + a2, М+1xМ+1 + a2NХN = b2.

.. .. .. .. ... .

xМ + aМ, М+1×2 + aМNХN = bМ.

xj 0 (j = 1, 2, …, N).

задача линейное программирование С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные — неотрицательные: хj 0 (j = 1, 2, …, M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу.

Найти минимальное значение линейной функции.

Z = СМ+1хМ+1+СNxN при ограничениях.

a1,М+1xМ+1 + a1NХN b1.

a2,М+1xМ+1 + a2NХN b2.

.. .. .. ... .

aМ, М+1xМ+1 + aМNХN bМ.

xМ+1 0, хN 0.

Преобразованная задача содержит два неизвестных; решая ее графическим методом, находим оптимальные значения xМ+1 и хN, а затем, подставляя их в (2.4), находим оптимальные значения х1, х2, …, хM.