Линейная оптимизация

Общей задачей линейного программирования (планирования) называется задача нахождения экстремума линейной целевой функции вида:

$f(x)=\sum_{j=1}^n c_jx_j=c_1x_1+c_2x_2+\ldots+c_nx_n$

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

$\sum_{j=1}^n a_{ij}x_j\geqslant b_i\quad (i=1,\;2,\;\ldots,\;m)$ ,

$x_j\geqslant 0\quad (j=1,\;2,\;\ldots,\;n)$ .

Пример

Фирма производит три вида продукции (А, В, С). Для выпуска единицы продукции каждого вида требуется определенное время обработки на всех четырех устройствах I, II, Ш, IV. Известна также прибыль от реализации единицы продукции каждого вида.

Вид продукции	Время обработки, ч				Прибыль, долл.
Вид продукции	I	II	III	IV	Прибыль, долл.
А	1	3	1	2	3
В	6	1	3	3	6
С	3	3	2	4	4

Пусть время работы на устройствах I, II, Ш, IV ограничено соответственно 84, 42, 21 и 42 часами. Определите, какую продукцию и в каких количествах стоит производить для максимизации прибыли. (Рынок сбыта для каждого продукта неограничен).

Решение

Построим математическую модель задачи

Пусть х1 - количество продукции А, х2 - количество продукции В, х3 - количество продукции С.

Целевая функция (прибыль): 3*х1+6*х2+4*х3 → max

Ограничения:

1*х1+6*х2+3*х3 <= 84

3*х1+1*х2+3*х3 <= 42

1*х1+3*х2+2*х3 <= 21

2*х1+3*х2+4*х3 <= 42

х1>=0; x2>=0; x3>=0.

Реализуем задачу в Excel:

Пояснения к таблице.

Добавлен столбец Количество продукции. В этом столбце пока введем единицы. Количество продукции каждого вида нам ещё предстоит рассчитать, чтобы максимизировать прибыль.

В ячейке F6 рассчитана суммарная прибыль = сумме прибылей по каждому виду продукции. Прибыль по виду продукции = Количество единиц продукции*Прибыль за единицу. Использована функция "Сумма произведений" =СУММПРОИЗВ(F3:F5;G3:G5).

Добавлена строка "Итого, ч" с расчетом загрузки каждого устройства при производстве всех видов продукции. Загрузка устройства при производстве определенного вида продукции = Количество продукции этого вида * Время обработки. В ячейке E6 использована функция "Сумма произведений" =СУММПРОИЗВ(E3:E5;G3:G5). Эта формула скопирована в ячейки B6:D6.

Добавлена строка "Ограничение, ч" с указанием максимально возможной загрузки каждого устройства.

Найдите оптимальное решение с помощью Поиска решения.

Ответ. Продукция А 12 единиц, продукция В 3 единицы, продукцию С не выпускать. Прибыль 54 долл.

Информационные технологии

Линейная оптимизация