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

Необходимо найти максимальное значение целевой функции F = 5X1+6X2 → max, при системе ограничений:
2x1+2x2≤13(1)
3x1+4x2≤22(2)
x1≥0(3)
x2≥0(4)
где x1, x1 - целые числа.Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

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

Границы области

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

Целевая функция F(x) → max

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

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

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

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

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

Методические пояснения: решение задачи получено с помощью сервиса Целочисленное программирование. Графический метод

загрузка...