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

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

Дана задача линейного программирования

f=y1xl + y2x2(max), (9.5)

аПх1 + а2х2 — А'

а2Л + °22х2 ^2> ^ q

.атх + ат2х2 ^ Ал>

в которую входят только два неизвестных Ху и х2. 224

Каждое из неравенств системы (9.6) определяет на координатной плоскости (xv х2) некоторую полуплоскость. Следовательно, допустимое множество Q задачи (9.5), (9.6) есть пересечение конечного числа полуплоскостей, т.е. некоторая многоугольная область на плоскости (хр х2).

Для решения задачи (9.5), (9.6) графическим методом необходимо:

построить многоугольную область Q;

провести перпендикулярно вектору Г = (Yj, y2) прямую / так, чтобы она пересекала область Q;

перемещать прямую / параллельно самой себе в направлении вектора Г до тех пор, пока она не перестанет пересекать область Q (для задачи минимизации прямую / необходимо перемещать в противоположном направлении).

Если при таком перемещении прямая / все время будет пересекать область Q, то целевая функция не ограничена сверху на допустимом множестве и задача (9.5), (9.6) не имеет оптимального решения (рис. 9.1).

В противном случае пересечение области Q с прямой / в том ее положении, когда дальнейшее перемещение дает пустое пересечение с Q, является множеством оптимальных решений задачи (9.5), (9.6) (рис. 9.2).

О Пример. Предприятие располагает тремя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 ч работы первым способом выпускается 20 единиц продукции, а вторым способом — 30 единиц. Количество сырья (кг) того или иного вида, расходуемого за 1 ч при различных способах производства, и запасы сырья (кг) приведены в табл. 9.1.

225

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

Обозначим через х, и х2 время использования (ч) соответственно первого и второго способов производства. Имеем задачу линейного программирования

/= 20xj + 30x2(max), 'IOjcj + 20х2 < 100, • 20*! + 10х2 < 100, 15*! + 15х2 < 90, Xj > 0, х2 0,

которую можно решить графическим способом. На рис. 9.3 изображены допустимое множество Q и оптимальное решение а0 этой задачи. Любая точка из допустимого множества Q является планом работы предприятия, для реализации которого хватит имеющихся запасов сырья. Оптимальное решение а0 — это план из допустимого множества Q, при котором будет выпущено наибольшее количество продукции.

226

Очевидно, что ос является точкой пересечения прямых /j и /3, имеющих уравнения lQxj + 20х2 100 и 15xj + 15х2 90 соответственно. Решая систему этих двух уравнений, получаем xt = 2,

*2 = 4Таким образом, для производства наибольшего количества продукции при имеющихся запасах сырья необходимо 2 ч применять первый способ производства и 4 ч — второй способ.

При этом будет изготовлено /(а0) = 20 • 2 + 30 • 4 = 160 единиц продукции. •