Фармацевтическая фирма ежедневно производит не менее 800 кг пищевой добавки

Линейное программирование (ЛП) – это метод оптимизации моделей, в которых целевые функции и ограничения строго линейны.

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

Задача, в которой требуется найти экстремум функции

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

называется задачей линейного программирования.

Задача в краткой записи имеет вид

2.1.  Модели линейного программирования с двумя
переменными

Пример 2.1. Компания Mikks производит краску для внутренних и наружных работ из сырья двух типов С1 и С2. Следующая таблица представляет основные данные для задачи.

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

Задача (модель) линейного программирования (ЗЛП), как и любая задача исследования операций, включает три основных элемента.

1.  Переменные, которые следует определить.

2.  Целевая функция, подлежащая оптимизации.

3.  Ограничения, которым должны удовлетворять переменные.

Определение переменных – первый шаг в создании модели. В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели:

ежедневный объем производства краски для наружных работ;

ежедневный объем производства краски для внутренних работ.

Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z (она измеряется в тысячах долларов) и положим, что .

В соответствии с целями компании получаем задачу:

Максимизировать , или

Итак, остался не определенным последний элемент модели — условия (ограничения), которые должны учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом.

Из таблицы с данными имеем следующее.

Используемый объем сырья (т)

Используемый объем сырья (т)

Поскольку ежедневный расход сырья С1 и С2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.

(сырье С1)

(сырье С2)

Существует еще два ограничения по спросу на готовую продукцию:

1)  максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т, т. е.

2)  ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на одну тонну (разность между ежедневными объемами производства красок для внутренних и наружных работ не должна превышать одной тонны), т. е.

Еще одно неявное ограничение состоит в том, что переменные и должны быть неотрицательными.

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

Максимизировать (или )

при выполнении следующих ограничений:

, .

Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение и будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Чтобы удостовериться в этом, подставьте значения и в левые части неравенств системы ограничений и убедитесь, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно (тысяч долларов).

Итак, задача сформулирована.

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

2.2.  Графическое решение ЗЛП

Графический способ решения задачи ЛП состоит из двух этапов.

1.  Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.

2.  Нахождение оптимального решения среди всех точек пространства допустимых решений.

2.2.1.  Нахождение максимума целевой функции

Используем модель, построенную для компании Mikks, чтобы показать два этапа графического решения ЗЛП.

Этап 1. Построение пространства допустимых решений.

Сначала проведем оси: на горизонтальной будут указываться значения переменной , а на вертикальной — (рис. 2.1). Далее рассмотрим условие неотрицательности переменных: , . Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте.

Рис. 2.1. Пространство допустимых решений модели

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получим уравнения прямых, а затем на плоскости провести эти прямые. Например, неравенство заменяется уравнением прямой . Эта прямая обозначена на рис. 2.1 как линия (1).

Этап 2. Нахождение оптимального решения.

Точки пространства допустимых решений, показанного на рис. 2.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках А, В, С, D, Е и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной ABCDEF, является допустимым решением, т. е. удовлетворяет всем ограничениям. Поскольку пространство допустимых решений содержит бесконечное число точек, необходима некая процедура поиска оптимального решения.

Нахождение оптимального решения требует определения направления возрастания целевой функции (напомним, что мы максимизируем функцию z). Мы можем приравнять z к нескольким возрастающим значениям, например 10 и 15.

Эти значения, подставленные вместо z в выражение целевой функции, порождают уравнения прямых. Для значений 10 и 15 получаем уравнения прямых и . На рис. 2.2 эти прямые показаны штриховыми ли­ниями, а направление возрастания целевой функции — толстой стрелкой.

Рис. 2.2. Оптимальное решение модели

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

На рис. 2.2 видно, что оптимальное решение соответствует точке С. Эта точка является местом пересечения прямых (1) и (2), поэтому ее координаты и находятся как решение системы уравнений, задающих эти прямые:

Решением этой системы будет и , при этом значение целевой функции равно.

Полученное решение означает, что для компании Mikks оптимальным выбором будет ежедневное производство 3 т краски для наружных работ и 1.5 т — для внутренних работ с ежедневным доходом в $21 000.

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

2.2.2.  Нахождение минимума целевой функции

Пример 2.2. Задача о диете

Фармацевтическая фирма Ozark ежедневно производит не менее 800 кг некой пищевой добавки – смеси кукурузной и соевой муки, состав которой представлен в следующей таблице.

Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не более 5% клетчатки. Фирма Ozark хочет определить рецептуру смеси минимальной стоимости с учетом требований диетологов.

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

— количество (в кг) кукурузной муки, используемой в дневном производстве пищевой добавки;

— количество (в кг) соевой муки, используемой в дневном производстве пищевой добавки.

Целевая функция равна общей стоимости пищевой добавки, производимой за один день, и должна быть минимальной. В данном случае это можно записать следующим образом:

Минимизировать (или )

Ограничения модели должны отражать производственные требования и рекомендации диетологов. Фирма должна выпускать не менее 800 кг смеси в день; соответствующее ограничение будет записано следующим образом: .

Рассмотрим ограничение, связанное с количеством белка в пищевой добавке. Общее количество белка в смеси, состоящей из кг кукурузной муки и кг соевой муки, равно (кг).

Это количество должно составлять не менее 30% от общего объема смеси . Отсюда получаем следующее неравенство:

Аналогично строится ограничение для клетчатки:

В последних двух неравенствах переменные и надо перенести из правых частей в левые. Окончательно модель примет следующий вид.

Минимизировать (или )

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

, .

На рис. 2.3 показано графическое решение этой задачи.

Поскольку в данной модели следует минимизировать целевую функцию, поэтому нужно идти в направлении уменьшения ее значений (это направление на рис. 2.3 показано стрелкой). Оптимальное решение находится на пересечении прямых и , откуда получаем (кг) и (кг).

При этих значениях переменных минимальная стоимость производимой ежедневно пищевой добавки составляет

Рис. 2.3. Графическое решение задачи о диете

2.3.  Компьютерное решение задач ЛП (при помощи Excel)

Проиллюстрируем на примере Mikks.

Составим в Excel следующую таблицу:

Здесь содержится 4 типа данных:

1)  входные данные (ячейки B5:C9 и F6:F9),

2)  значения переменных и целевой функции (ячейки в прямоугольнике B13:D13),

3)  формулы, по которым вычисляются значения целевой функции и левых частей ограничений (ячейки D5:D9) и

4)  поясняющие заголовки и надписи.

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

Покажем соответствие между математической моделью и табличной.

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

Откроется одноименное диалоговое окно:

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

—  в поле ввода УСТАНОВИТЬ ЦЕЛЕВУЮ ЯЧЕЙКУ вводится D5;

—  устанавливается переключатель РАВНОЙ МАКСИМАЛЬНОМУ ЗНАЧЕНИЮ;

—  в поле ввода ИЗМЕНЯЯ ЯЧЕЙКИ вводится $B$13:$C$13.

Эта информация указывает средству ПОИСК РЕШЕНИЯ, что переменные находятся в ячейках В13 и С13, и надо найти максимум целевой функции, значение которой вычисляется в ячейке D5.

Далее надо задать ограничения модели, щелкнув на кнопке ДОБАВИТЬ в диалоговом окне ПОИСК РЕШЕНИЯ. Открывшееся диалоговое окно ДОБАВЛЕНИЕ ОГРАНИЧЕНИЯ предоставляет средства для ввода всех частей ограничений (левой части, знака неравенства и значения правой части). Используя это окно, вводим ограничения модели в таком виде: $D$6:$D$9<=$F$6:$F$9 (напомним, что в ячейках F6:F9 записаны значения правых частей ограничений).

Теперь осталось ввести ограничения неотрицательности для переменных. С помощью диалогового окна ДОБАВЛЕНИЕ ОГРАНИЧЕНИЯ вводим $B$13:$C$13>=0.

Когда ПОИСК РЕШЕНИЯ найдет решение этой задачи, оптимальное значение целевой функции появится в ячейке D5, а значения переменных и – в ячейках B13 и С13 соответственно.

Теперь все готово для решения нашей задачи, достаточно щелкнуть на кнопке ВЫПОЛНИТЬ в диалоговом окне ПОИСК РЕШЕНИЯ, для чего надо открыть диалоговое окно ПАРАМЕТРЫ ПОИСКА РЕШЕНИЯ, щелкнув на кнопке ПАРАМЕТРЫ.

Самое важное – установить опцию ЛИНЕЙНАЯ МОДЕЛЬ. В этом же окне можно указать, что все переменные должны быть неотрицательными (опция Неотрицательные значения).

Результат работы:

2.4.  Двойственная задача и ее решение

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

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

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

1)  в одной задаче ищут максимум целевой функции, в другой — минимум;

2)  обе задачи являются стандартными задачами линейного программирования, причем в задаче о максимуме все неравенства вида «≤», а в задаче о минимуме — вида «≥» ;

3)  матрица системы ограничений одной задачи является транспонированной к матрице системы ограничений другой;

4)  коэффициенты при переменных целевой функции одной задачи являются свободными членами ограничений другой;

5)  число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче;

6)  условия неотрицательности имеются в обеих задачах.

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

2.5.  Целочисленное программирование

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

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

Пример 2.3. На мебельной фабрике изготавливают столы, стулья и табуреты. На производство одного изделия требуется 1,5, 1 и 0,62 м3 древесины. При этом затраты рабочего времени при изготовлении стола составляют 5 машино-часов, стула − 1,5 машино-часа и табурета − 0,7 машино-часа. Всего для производства мебели фабрика может ежедневно использовать 12 м3 древесины. Оборудование может быть занято в течение 26 машино-часов. Прибыль от реализации стола, ст и 15 руб. соответственно. Фабрика должна ежедневно производить не менее двух столов. На производство другой продукции ограничений нет. Требуется определить, какую продукцию и в каком количестве следует ежедневно изготавливать фабрике, чтобы прибыль от ее реализации была максимальной.

Решение.

Составим вспомогательную таблицу:

Определим переменные модели: