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

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

• целевая функция

• ограничения

Здесь постоянные величины - должны быть заданы в условиях задачи,n– количество искомых переменных,i=1,n– номер переменной,m– количество линейных уравнений, которые представляют собой ограничения,k=1,m. Требуется определить такие значения переменных, которые обеспечивают в зависимости от постановки задачи максимум, минимум или постоянное значение целевой функции.

В качестве примера рассмотрим задачу о выборе ассортимента товаров. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители. Расходы исходных продуктов на 1кг мороженого и их суточные запасы даны в таблице 3.1.

Отпускная цена 1кг сливочного мороженого 16 р., шоколадного – 14 р. Определить какое количество продукции каждого вида должна производить фирма, чтобы стоимость этой продукции, а следовательно и доход от ее реализации был максимальным.

Таблица 3.1

Математическая модель

Обозначим X1суточный объем выпуска сливочного мороженого,X2– шоколадного. Тогда стоимость произведенной продукции (целевую функцию), которую требуется максимизировать, можно записать:

F=16*X1 + 14*X2 (1)

Учитывая указанные в таблице запасы исходных продуктов, запишем ограничения:

0,8*X1+0,5*X2 ≤ 400 (2)

0,4*X1+0,8*X2 ≤ 365 (3)

X1 ≥ 0 (4)

X2 ≥ 0 (5)

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

Для того, чтобы не только получить конкретное решение, но и исследовать влияние ограничений на доход предприятия, надо создать на листе Excelтаблицу (рис.3.7).

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

Стоимость выпущенного мороженого подсчитывается по формулам: =16*G4 и =14*G5. Формулы записываются в ячейкиH4 иH5. В ячейкеH8 должна быть вычислена суммарная стоимость выпущенного мороженого.

Для того, чтобы записать ограничения (2) и(3)так как это требуется в программе, надо вычислить расход исходных продуктов – расход молока по формуле =E4*G4 и расход наполнителя по формуле =E5*G5. Эти формулы должны быть записаны в ячейкахE7 иF7. В поле «Ограничения» окна «Поиск решения» должны быть записаны ограничения в виде неравенствE7<=E6 иF7<=F6. Ограничения (4) и (5) можно добавить в окно «Ограничения». Но проще отметить (щелкнуть мышкой) флажок «Неотрицательные значения» в окне «Параметры» (рис.3.6).

Рис 3.7 Таблица расчета стоимости продукции

На рисунке 3.8 приведено окно «Поиск решения», в котором введены все исходные данные для рассмотренного здесь примера.

Рис. 3.8 Окно «Поиск решения» для задачи линейного программирования