ГЛАВА 2

ВВЕДЕНИЕ В ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Эта глава начинается с изучения моделей с двумя переменными и их графическими решениями. Обобщение графического метода решения приводит к алгебраическому симплекс-методу (см. главу 3). Графическое решение также показывает конкретные механизмы разработки и реализации анализа чувствительности задач ЛП. Глава заканчивается большим количеством примеров формализации и решения практических задач.

2.1. МОДЕЛИ ЛП С ДВУМЯ ПЕРЕМЕННЫМИ

В этом разделе на простом примере с двумя переменными показаны основные элементы модели ЛП. Далее этот пример будет обобщен в общую задачу линейного программирования.

Пример 2.1.1. Компания Reddy Mikks1

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

1 Автор часто использует в примерах шуточные названия компаний, которые адекватно трудно перевести на русский язык. Например, в данном случае Reddy Mikks дословно не переводится, но по-русски это звучало бы как Охряные смеси (намек на производимые краски) или как Краснощекие бездельники . Эти названия, как правило, не несут смысловой нагрузки. Поэтому в большинстве случаев мы будем оставлять их без перевода. - Прим. перев.

Расход сырья (в тоннах) на тонну краски

для наружных работ

для внутренних работ

Максимально возможный ежедневный расход сырья

Сырье М1 Сырье М2

Доход (в тыс. долл.) на тонну краски

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

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

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

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

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

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

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

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

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

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

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

максимизировать z = 5хх + 4х2.

Используемый объем сырья для производства < обоих видов краски ,

ежедневный расход сырья

Максимально возможный

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

Используемый объем сырья Ml = 6jc, + 4х2 (т) Используемый объем сырья М2 = 1дг, + 2х2 (т)

2.1. Модели ЛП с двумя переменными

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

6х, + 4х2 < 24 (сырье Ml)

1х, + 2х2 < 6 (сырье М2)

Существует еще два ограничения по спросу на готовую продукцию. Первое ограничение указывает, что ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на одну тонну, т.е. х2 - х, < 1. Второе ограничение простое - максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т - и записывается как х2 < 2.

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

Окончательно задача будет записана следующим образом:

максимизировать z = 5х, + 4дг2 при выполнении ограничений

6х, + 4х2 < 24, xt + 2x2<6,

- Xj +х2 < 1,

х2<2,

х,>0,х2>0.

Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение х, = 3 и х2 = 1 будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Чтобы удостовериться в этом, подставьте значения х, = 3 и х2 = 1 в левые части неравенств системы ограничений и убедитесь, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно z = 5x3 4- 4x1 = 19 (тыс. долл.).

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

В предыдущем примере целевая функция и все ограничения были линейными. Свойство линейности функций предполагает следующее.

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

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