Целочисленные ЗЛП, графический метод решения в случае двух переменных.

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

В системе координат X ₁0 X ₂ находят область допустимых решений, строят вектор C и линию уровня. Перемещая линию уровня по направлению C для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты.

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

Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координата вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора C.

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

Пример: Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для чего в одном из цехов необходимо установить дополнительное оборудование, требующее м² площади. На приобретение дополнительного оборудования фирма выделила 10 тыс. ден. ед., при этом она может купить оборудование двух видов. Приобретение одного комплекта оборудования 1-го вида стоит 1 тыс. ден. ед., 2-го вида — 3 тыс. ден. ед. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования 2-го вида — на 4 ед.

Зная, что для установки одного комплекта оборудования 1-го вида требуется 2м² площади, а для оборудования 2-го вида — 1м² площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение: Составим математическую модель задачи.

Предположим, что фирма приобретает комплектов дополнительного оборудования 1-го вида и комплектов оборудования 2-го вида.

Математическая модель задачи будет иметь вид:

при ограничениях:

,

, , .

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

Рис. 41.1

OABC — область допустимых решений (ОДР). Оптимальное решение задача имеет в точке B (9/5,41/15) при этом максимальное значение целевой функции составляет 218/15 ед. Полученное оптимальное решение не целочисленное. Условию целочисленности переменных удовлетворяют координаты 12 точек, принадлежащих ОДР. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник OABC многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами.

Строим вектор . Линию уровня перемещаем по направлению ,

получим в точке E (1, 3) максимальное значение целевой функции

(ед.)

Ответ: Фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида, что обеспечит ей при имеющихся ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 ед. в смену.