Задачи оптимизации

2 x1 x2 x3 min; 2 x2 x3 x4 5;

x1 x2 x3 x5 1; 2 x1 x2 x6 3;

x1 0, xi 0, i 2, 3, 4, 5, 6.

Заметим, что знак, с которым вводится новая переменная в уравнение ограничения, зависит от смысла неравенства. Если знак неравенства , то дополнительная переменная вводится со знаком «плюс», а, если , то со знаком «минус». Именно по этой причине перед переменной x6 поставлен знак минус.

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

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

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

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

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

Для иллюстрации сказанного выше обратимся к простому примеру.

Пример 3.3

Планируется выпустить два вида продукции. Для производства единицы продукции первого вида требуется 2 кг сырья первого вида, 1 кг сырья второго вида. Для производства единицы продукции второго вида требуется 1 кг сырья первого вида, 1 кг сырья второго вида. Наличие сырья первого вида –10 кг; второго – 7 кг. Прибыль от реализации единицы продукции первого вида – 6 рублей; второго вида – 4 рубля.

Разработать оптимальный план выпуска продукции, оптимизирующий прибыль.

11

Рис. 11. Графическое построение области допустимых планов и оптимального плана

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

12

Условие оптимизации прибыли x1 6 x2 4 max также запишем в виде

уравнения прямой, придав целевой функции некоторое значение C : x2 C4 1,5 x1 . В действительности это уравнение задает целое семейство па-

раллельных линий, различающихся различным значением прибыли C . Из всего множества этих линий следует выбрать ту, которая имеет хотя бы одну общую точку с областью допустимых решений и соответствует при этом максимально возможному значению прибыли, задаваемому параметром C . На рис. 11 это линия, касающаяся области допустимых планов в угловой точке g.

Таким образом, прибыль будет максимальной, если x1 3, x2 4 . При этих

значениях параметров производства достигается максимально возможная прибыль, равная 34.

Подведем некоторые итоги геометрического анализа задачи линейной оптимизации в примере 3.3. Хотя мы рассмотрели всего лишь один частный пример, он позволяет сделать выводы, справедливые для любой задачи линейного программирования.

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

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

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

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

Например, если в условие примера 3.3 внести коррективы, считая, что прибыль от реализации единицы продукции первого вида – 4 рубля; второго вида – 2 рубля, то семейство линий постоянной прибыли будет иметь вид x2 C2 2 x1 (семейство линий, параллельных линии ограничения ab).

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

Другая проблема таких решений – их неустойчивость. Действительно, если в уравнении, определяющем семейство планов с равной прибылью, x2 C2 2 x1 ,

коэффициент перед переменной x1 будет чуть-чуть меньше двух, то оптимальным

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

13

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

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

Рассмотрим еще один важный в практическом отношении вопрос. Всегда ли допустимая область должна быть ограниченной? Легко себе представить ситуацию, когда допустимая область является неограниченной, как на рис. 12, а оптимальное решение существует.

Рис. 12. Оптимизация в модели с неограниченной допустимой областью (вправо область предполагается неограниченной)

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

Таким образом, каждая задача линейного программирования принадлежит к одной из трех взаимоисключающих категорий.

1.Задача имеет оптимальное решение.

2.Оптимального решения нет, поскольку нет допустимых решений.

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

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

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

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

14

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

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

1.Сформулированная в словесной форме задача линейного программирования должна быть формализована и записана в виде математической модели, например в виде (3.14).

2.Следует уделить должное внимание оформлению табличной модели на листе электронных таблиц Excel. Правильное оформление табличной модели позволяет легко контролировать ввод данных в программу Поиск решения и обеспечивает информативный отчет по чувствительности модели. Рекомендации по такому оформлению приведены ниже в примере 3.4.

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

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

5.При задании левых и правых частей ограничений модели в диалоговом окне Добавление ограничений2, нужно ссылаться на ячейки рабочего листа, а не вводить формулы в левое окно или константы в правое окно непосредственно на этой форме. Рекомендуется подготовить необходимые формулы и константы предварительно на листе рабочей книги, а в диалоговом окне Добавление ограничений лишь указать на нужные ячейки (см. пример 3.4).

После того как сформулированы некоторые общие принципы, рассмотрим

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

Пример 3.4

При создании сплава для новой продукции компания Eastern Steel использует железную руду, получаемую с четырех различных шахт. Как показал анализ, чтобы получить сталь с заданными технологическими свойствами, нужно обеспечить содержание основных химических элементов А, В, С в исходном сырье

2 Это окно открывается после нажатия кнопки Добавить на основной форме процедуры Поиск решения.

15

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

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

Решение

Обозначим x1, x2, x3, x4 – долю руды с первой, второй, третьей и четвертой шахт в одной тонне смеси. Целевая функция, очевидно, представляет собой стоимость одной тонны смеси, которая должна быть минимальной. В наших обозначениях это условие может быть записано в виде: x1 800 x2 400 x3 600 x4 500 min . Для построения математической модели этой задачи следует к условию минимальности добавить ограничения по содержанию химических элементов А, В, С в одной тонне смеси, условие по-

x1 x2 x3 x4 1;

x1 0, x2 0, x3 0, x4 0.

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

16

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

Как уже указывалось, правильная запись математической модели на рабочем листе Excel является совершенно необходимым элементом решения задач с помощью программы Поиск решения. Ниже на рис. 13 показан пример такого размещения исходных данных. Целевой является ячейка с адресом F4, для размещения переменных отведены ячейки B3:E3. На рисунке показан фрагмент листа Excel после успешного завершения работы программы Поиск решения, поэтому в этих ячейках находятся значения искомых параметров оптимальной смеси.

Ячейки B4:E4 содержат экзогенные параметры – стоимость тонны руды различных месторождений. В ячейках F6:F9 записаны левые части ограничений системы (3.19), а соответствующие константы содержатся в ячейках H5:H9.

Рис. 13. Построение табличной модели решения задачи в примере 3.4

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

Рис. 14. Формулы, записанные в целевую ячейку и ячейки, содержащие левые части ограничений

Ячейки B6:E8 содержат заданные значения содержания химических элементов А, В, С в руде, добытой в различных шахтах. Эти данные используются для записи левых частей ограничений. Ячейки G6:G9 содержат знаки (равенств и неравенств), соединяющие левые и правые части ограничений системы (3.19), что позволяет контролировать правильность ввода данных в диалоговом окне Добавле-

ние ограничений.

Наконец, в ячейках I6:I9 записана разность левых и правых частей ограничений. После выполнения оптимизационных расчетов результат в этих ячейках может не оказаться равным нулю. Это не является ошибкой, поскольку левые и правые части ограничений соединены знаком неравенств. Наличие ненулевых результатов в этих ячейках следует рассматривать как некоторый резерв, который при возмож-

17

ном изменении технологии производства позволит снизить производственные издержки.

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

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

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

1.Оптимальное решение любой задачи линейного программирования не может находиться во внутренней точке допустимой области.

2.Лимитирующее ограничение – это ограничение, на линии которого расположено оптимальное решение.

3.Нелимитирующее ограничение – это ограничение, на линии которого нет оптимального решения.

4.Из общих соображения ясно, что добавление ограничений приведет либо к ухудшению оптимального решения, либо оставит его неизменным. Удаление ограничений приведет к улучшению оптимального значения либо оставит его неизменным.

5.Введение удаление дополнительных переменных улучшит ухудшит оптимальное значение, или оставит его неизменным.

Анализ чувствительности моделей линейного программирования

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

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

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

18

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

Сразу следует отметить, что анализ чувствительности по каждому из параметров производится в предположении, что все остальные параметры модели остаются постоянными. В экономике такой анализ называется анализом по предельным показателям .

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

Пример 3.5

Мебельная фирма производит два вида стульев «Мечта» и «Лада». Компании требуется оптимизировать план недельного производства стульев, исходя из того, что прибыль от продажи одного стула «Мечта» составляет 56 рублей, а от продажи одного стула «Лада» – 40 рублей.

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

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

Перед менеджерами компании стоит задача определить оптимальный план недельного производства стульев каждого типа.

Решение

Составим математическую модель задачи. Обозначим количество производимых стульев марки «Мечта» и «Лада» переменными x1 и x2 . Тогда математическая модель поставленной задачи будет выглядеть следующим образом:

19

56 x1 40 x2 max;

8 x1 4 x2 1350 (ограничение на число длинных штифтов); 4 x1 12 x2 1600 (ограничение на число коротких щтифтов);

4 x1 4 x2 760 (ограничение на число ножек);

(3.20)

x1 140 (ограничение на число прочных сидений);

x2 120 (ограничение на число облегченных сидений); x1 x2 100 (минимальный объем производства);

x1 0, x2 0 (условие неотрицательности).

Табличная модель решения задачи (после завершения работы программы Поиск решения) представлена на рис. 15.

Рис. 15. Фрагмент листа рабочей книги Excel с табличной моделью решения задачи по оптимизации производства стульев

Используя данные примера 3.5. рассмотрим, какую информацию можно получить об устойчивости модели в программе Поиск решения. Предположим, что доход от реализации стульев в течение недели может изменяться, а все ограничения остаются неизменными. В каких пределах может изменяться прибыльность производства стульев различных марок, которая не повлечет за собой замены плана производства?

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

На рис. 16 показана область допустимых планов для рассматриваемой задачи (закрашена серым цветом)

20