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

Пример.

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

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

Решение.

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

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

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

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

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

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

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

Решив систему уравнений, получим: x1 = 0.8, x2 = 3.6
Откуда найдем максимальное значение целевой функции:
F(X) = -3*0.8 + 4*3.6 = 12

Решение получилось не целочисленным.
Множество допустимых решений задачи с отмеченными на нем целочисленными точками представлено на рис. 5.
Перемещение линии уровня целевой функции F(X) в направлении, задаваемом ее градиентом, показывает, что наибольшее значение F(X)=10 она примет в точке (2, 4).

загрузка...