Графический метод решения ЗЛП с n переменными

С помощью графического метода может быть решена ЗЛП, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если n и m связаны соотношением n-m=2. Действительно, пусть поставлена ЗЛП:

найти минимальное значение линейной функции Z=C₁x₁+С₂x₂+...+С_n x_n при ограничениях

x_j 0_, (j=1,2,…,n ).

где все уравнения линейно независимы и выполняется соотношение n-m =2.

Используя метод Жордана - Гаусса, производим т исключений, в результате которых базисными неизвестными будут, например, т первых неизвестных x₁,x₂,..., x_m, а свободными - два последних: .x_m+1 и x_n, т. е. система ограничений приняла вид

С помощью уравнений преобразованной системы выражаем линей­ную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные - неотрицательные: x_j 0 (j=1,2,..., т),отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу: найти минимальное значение линейной функции Z = C^'_m+1x_m+1 + C^'_nx_nпри ограничениях

Преобразованная задача содержит два неизвестных; решая ее графическим методом, находим оптимальные значения x_m+1 и х_n, а затем, подставляя их в (1.34), находим оптимальные значения x₁,x₂,…x_m.

Пример. Графическим методом найти оптимальный план ЗЛП Z=2х₁-х₂+x₃-3x₄+4х₅®max при ограничениях x_j 0 (j=1,2,..., 5).

Решение. Используя метод Жордана — Гаусса, производим 3 полных исключения неизвестных х₁, х₂, х₃.

X1	X2	X3	X4	X5	B
	-1 -1 -2		-18 -21 -43		-4
	-1	-2 -1	-18		-4
		-2	-3 -4
			-4	-3

В результате приходим к системе:

(1)

откуда х₁=6-х₄+3х₅, х₂=70-7­х₄-10х₅, х₃=20+4х₄-5х₅. (2) Подставляя эти значения в линейную функцию и отбрасывая в системе (1) базисные переменные, получаем задачу, выраженную только через свободные неизвестные переменные х₄ и х₅: найти максимальное значение линейной функции Z= 6x₄ +15x₅-38 при ограничениях

Построим многогранник решений и линейную функцию в системе координат x₄0x₅ . Из рис. заключаем, что линейная функция принимает максимальное значение в угловой точкеВ, которая лежит на пересечении прямых 2 и 3. В результате решения системы

находим:x₄ = 2,x₅= 28/5. Максимальное значение функция Z_max =- 38+ +12+84-58.

Для отыскания оптимального плана исходной задачи, подставляем в (2) найденные значения x₄ и х₅. Окончательно получаем: х₁ = 104/5, х₂ =0, х₃ =0, х₄ = 2, x₅ = 28/5.

Контрольные вопросы

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

Рекомендованная литература: [ 2, 5, 8, 11, 12]

Тема 5. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Розглянуті питання з теми:

5.1. Геометрическая интерпретация симплексного метода

Алгоритм симплекс-метода

5.3. Пример отыскания максимума линейной функции

5.4. Пример отыскания минимума линейной функции

5.5. Симплексные таблицы

5.6. Метод искусственного базиса