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

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

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

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

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

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

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

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

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

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

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

загрузка...