Целочисленное программирование. Графический метод

Пример.

Задачу линейного программирования решить графическим способом. F = x1-2x2 → min.

2x1-x2≥4(1)
-x1+2x2≤7(2)
-4x1+3x2≥-12(3)
x1+3x2≥18(4)
x1≥0(5)
x2≥0(6)
где x1, x1 - целые числа.

Решение.

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

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

или

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

Границы области допустимых решений

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

Рассмотрим целевую функцию задачи F = x1-2x2 → min.
Построим прямую, отвечающую значению функции F = 0: F = x1-2x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Рисунок 3 - Пример решения графическим методом

Равный масштаб

Рисунок 4 - Линейное программирование. Графический метод

Область допустимых решений представляет собой многоугольник.

Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
2x1-x2≥4
-x1+2x2≤7

Решив систему уравнений, получим: x1 = 5, x2 = 6
Откуда найдем минимальное значение целевой функции:
F(X) = 1*5 - 2*6 = -7
Поскольку функция цели F(x) параллельна прямой (2), то на отрезке BD функция F(x) будет принимает одно и тоже минимальное значение.
Для определения координат точки D решим систему двух линейных уравнений:
-x1+2x2≤7
-4x1+3x2≥-12

Решив систему уравнений, получим: x1 = 9, x2 = 8
Откуда найдем минимальное значение целевой функции:
F(X) = 1*9 - 2*8 = -7

Решение получилось целочисленным.

загрузка...