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

Пример.

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

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

Решение.

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

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

или

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

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

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

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

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

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

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

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

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

Решив систему уравнений, получим: x1 = 16.25, x2 = 18.75
Откуда найдем максимальное значение целевой функции:
F(X) = 90*16.25 + 210*18.75 = 5400
Поскольку функция цели F(x) параллельна прямой (2), то на отрезке CB функция F(x) будет принимает одно и тоже максимальное значение.
Для определения координат точки B решим систему двух линейных уравнений:
3x1+7x2≤180
x1=0

Решив систему уравнений, получим: x1 = 0, x2 = 25.7143
Откуда найдем максимальное значение целевой функции:
F(X) = 90*0 + 210*25.7143 = 5400

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

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