Гл. 12. Линейное программирование

Производство •Pink Fin-, ^ л/день 1<00

Специальный ингредиент 0,01р + 0,04т - 16 кг /день

А - точка, в которой достигается максимальный доход

Типичный доход

Время работы оборудования 0,02р + 0,4т - 24 ч /день

&УУУУУУУ&У>,

0,lp+0,3m--100 ф.ст./день

Производство "Mint Pop^-, л/день

Рис. 12.8. Задача линейного программирования для примера 12.1

Эти два ограничения называются связывающими, или лимитирующими огра­ничениями. Они соответствуют тем ресурсам, которые в процессе производства используются полностью и, следовательно, препятствуют дальнейшему увеличению ежедневного дохода. Оптимальное решение задачи — это точка пересечения прямых.

0,02р + 0,04т = 24; (1)

0,01р + 0,04т = 16. (2)

Вычтем уравнение (2) из уравнения (1):

0,01 р = 8.

Следовательно, р = 800 л в день. Подставив найденное значение р в уравнение (2), найдем т:

0,01 х 800 + 0,04 т = 16.

Следовательно, m = 200 л в день.

Таким образом, чтобы получать максимальный ежедневный доход, фирма должна производить 800 л "Pink Fizz" и 200 л "Mint Pop" в день. Это сочетание объемов производства дает максимальное значение дохода: 0,10 х 800 + 0,30 х 200 = = 140 ф. ст. в день.

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

414 Ч. 4. Моделирование в бизнесе

Этот метод определения оптимальной крайней точки зависит от того, насколько правильно была построена линия уровня дохода. Ниже излагается практический прием, который может помочь при нанесении на график линии уровня, которая будет являться основой для определения оптимальной крайней точки. Выберем любую удобную точку, лежащую приблизительно в середине допустимого множества. Предположим, что в примере, изложенном выше, выбрана точка с координатами р = 200, m = 200. Ежедневный доход от выпуска продукции в таком объеме составит:

Р = 0,10 р + 0,30 m = 0,10 х 200 + 0,30 х 200 = 80 ф. ст. в день.

Все остальные сочетания объемов производства, позволяющие получать 80 ф. ст. ежедневного дохода, принадлежат прямой

80 = 0,10 р + 0,30 m (ф. ст. в день).

Одна точка этой прямой уже известна, это — точка с координатами р = 200, m = 200. Для определения другой точки можно положить m = 0, тогда р = 800. Теперь мы можем построить на графике эту линию уровня ежедневного дохода и, используя вышеизложенный алгоритм, определить оптимальное решение (или решения). Очевидно, что в результате применения данного алгоритма оптимальное решение всегда будет представлено либо крайней точкой множества, либо в случае, если целевая функция параллельна одному из ограничений, множеством точек отрезка, соединяющего две крайние точки.

Мы предполагали, что переменные в задаче линейного программирования непрерывны или, если это -условие не выполняется, могут принимать дробные значения. И действительно, часто имеет место ситуация, когда в течение временного промежутка, рассматриваемого в задаче, допустимы дробные значения объемов выпускаемой продукции. Если, например, производятся две модели автомобилей, а цель задачи линейного программирования состоит в максимизации использования оборудования в неделю, может оказаться, что оптимальное решение предполагает наличие к концу недели незавершенного производства. При такой постановке задачи, когда рассматриваемый период времени равен одной неделе, незавершенное производство вполне допустимо.

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

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

Гл. 12. Линейное программирование

переменных используется один из методов целочисленного программирования рассмотрение которых выходит за рамки этой книги.

□ Пример 12.5. Обратимся к примеру 12.2, в котором рассматривалось произ­водство двух типов деталей к автомобилям. Необходимо определить объемы производ­ства, при которых достигается максимальное значение общего дохода за неделю.

Решение.

Допустимые области для каждого из ограничений задачи выглядят следующим образом:

тыс. шт.
	■ Фонд рабочего времени ^ х + 2у - 4000
•г4*
	область ^^^*ш\\

Рис. 12.9. Ограничение на фонд рабочего времени: х + 2 у й 4000 чел.-ч. в неделю

Кч\\\\\\\\\\Х

у.