Лабораторная работа № 5 Модели линейной оптимизации в ms excel

Цель: приобрести навыки в использовании настройки Поиск решения с условием максимизации или минимизации целевой функции.

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

     сформулировать проблему;

     сформулировать цели, которые должны быть достигнуты в результате реализации найденного решения;

     указать, что считать решением проблемы (решение должно гарантировать достижение целей);

     выявить и описать возможности достижения целей;

     выявить и описать факторы, от которых может зависеть решение проблемы;

     выявить и описать ограничения, препятствующие достижению целей;

     описать возможные альтернативные способы решения проблемы.

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

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

Пусть имеет место некоторая целевая функция z, которая зависит от параметров х = (х₁, х₂, …, х_n), удовлетворяющих некоторым ограничениям α:

z = z(x,α).

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

Среди задач математического программирования самы­ми простыми являются задачи линейного программирова­ния (ЗЛП).

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

Инструментом для решений задач оптимизации в MS Ехсеl служит надстройка Поиск решения. Процедура поиска решения позволяет найти оптимальное значение фор­мулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках.

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

Решение поставленной задачи состоит из выполнения следующих действий:

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

2)  построения математической модели (перевод формальной модели на четкий язык математических отношений);

3)  анализа математической модели и получения математического решения проблемы (анализ построенной математической модели, построение компьютерной модели задачи);

4)  анализа математического решения проблемы и формирование управленческого решения (на основе математического решения принимается управленческое решение).

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

Задание. Предприятие «Олимп» имеет месячный цикл производства. Необходимо определить, сколько в месяц необходимо производить краски типа А и типа Б. Производственная мощность позволяет выпускать в месяц суммарно 500 т краски всех типов. Тонна краски типа А приносит в среднем 2000 руб. прибыли, а одна тонна краски типа Б – 2500 руб. Заказ на краску типа А – не менее 200 т в месяц (по договорам на поставку), краски типа Б нельзя производить более 150 т, так как большее количество трудно реализовать. По рецептуре  на изготовление краски типов А и Б тратится три вида сырья (табл. 5.1).

Таблица 5.1

Затраты сырья для производства красок

Сырье	Краска типа А, кг	Краска типа А, кг	Месячный запас, т
1	50	100	50
2	70	80	30
3	40	70	25

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

Методика выполнения. Безусловно, чем больше будет произведено продукции, тем лучше. Поэтому первая цель – произвести как можно больше краски типов А и Б. Однако имеется ограничение по производственным мощностям – 500 т.

Вторая цель заключается в получении максимальной прибыли от производства и реализации продукции. Факторами, влияющими на достижение данной цели, будут величины удельной прибыли по каждому виду продукции – 2000 руб. и 2500 руб. Прибыль предприятия в реальной экономике зависит от множества факторов и не является величиной постоянной даже на протяжении короткого промежутка времени. Поэтому ее трудно оценить на длительный период и можно оценить только будущую удельную прибыль с некоторой степенью точности. Для достижения второй цели выгодно производить только краску типа Б и совсем не производить краску типа А. Но есть два ограничения, определенные договорами поставки и трудностью реализации большого количества краски типа Б. при таких ограничениях понятно, что нужно производить 350 т краски типа А и 150 т краски Б. Таким образом будут учтены ограничения по производственным мощностям и маркетинговые ограничения.

С учетом данных табл. 5.1, становится очевидным, что общее количество сырья, используемого для производства краски, не должно превышать их месячные запасы. Таким образом, получаем еще три ограничения  –  по одному для каждого типа сырья.

После анализа проблемы получаем следующую информацию:

Постановка проблемы	Разработать производственный план, который бы максимизировал прибыль с учетом всех видов ограничений.
Цель	Максимизировать прибыль.
Решение	Количество тонн краски типов А и Б, производимых в месяц.
Факторы, от которых зависит решение	Значения удельной прибыли каждого типа краски, предельное число производимой краски, предельные числа производимых красок типов А и Б (маркетинговые ограничения), количества сырья (необходимого для производства одной тонны краски), значения запасов сырья (всего 14 факторов).
Факторы, влияющие на прибыль	Все перечисленные, кроме значений количества сырья, необходимого для производства одной тонны краски.
Ограничения	На предельное общее количество производимой краски, на предельные количества производимых красок типов А и Б в отдельности, на предельные количества используемого сырья (всего 6 ограничений).

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

Математическая модель должна содержать три основных компонента.

Переменные – необходимо вычислить (переменные решения из формальной модели).

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

Ограничения – записанные математически ограничения из формальной модели.

Обозначим через х₁ и х₂ переменные, которые определяют месячные объемы производства краски (в тоннах) типов А и Б соответственно. Зная прибыль от продажи одной тонны краски, получаем суммарную прибыль Z  при  производстве х₁  тонн краски типа А и х₂   тонн краски типа Б, руб.:

Z = 2000 х₁ + 2500 х₂.

Это целевая функция, которую необходимо максимизировать.

Далее рассмотрим ограничения. Суммарный объем производства не должен превышать 500 т: х₁ + х₂ ≤ 500. Маркетинговые ограничения записываем как х₁  ≥ 200;  х₂ ≤ 150.

Ограничения на сырье  записываются по каждому виду сырья с учетом расхода по каждому виду продукции. Для производства х₁ тонн краски типа А и х₂  тонн краски типа Б расходуется 0,05 х₁ + 0,1 х₂ тонн сырья 1. Поскольку эта величина не должна превышать величины запаса – 50 т, получаем ограничение 0,05 х₁ + 0,1 х₂ ≤ 50. Подобным образом получаем два других ограничения по сырью 2 и сырью 3: 0,07 х₁ + 0,08 х₂ ≤ 30; 0,04 х₁ + 0,07 х₂ ≤ 25. Еще одно неявное ограничение состоит в том, что переменные х₁ и х₂  должны быть неотрицательными (объем производства не может быть отрицательным числом). Это ограничение называется условием неотрицательности переменных и записывается так: х₁ ≥ 0; х₂ ≥ 0. Однако уже есть условие х₁ ≥ 200, поэтому ограничение х₁ ≥ 0 исключаем из списка ограничений.

Окончательно математическая модель будет выглядеть следующим образом.

Максимизировать Z = 2000 х₁ + 2500 х₂.

При выполнении ограничений:

х₁  +  х₂ ≤ 500;      х₁ ≥ 200;      х₂ ≤ 150;

0,05 х₁ + 0,1 х₂ ≤ 50;     0,07 х₁ + 0,08 х₂ ≤ 30;     0,04 х₁ + 0,07 х₂ ≤ 25;

х₂ ≥ 0.

Строим табличную модель на листе Excel (рис. 5.1).

Диапазон D10:D16 представляет собой вычисляемые ячейки. Формулы, по которым выполняются все вычисления на данном рабочем листе, показаны на рис. 5.2.

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

Значения переменных вносят изначально произвольные. Целевая функция вычисляется в ячейке D7. В диапазоне В10:С16 записаны коэффициенты функций ограничений, в диапазоне F10:F16 – значения правых частей ограничений, в диапазоне D10:D16 вычисляются значения левых частей ограничений.

Рис. 5.1. Табличная модель

Рис. 5.2. Формулы табличной модели

Для вычислений используем функцию СУММПРОИЗВ. Абсолютные ссылки делаем на ячейки, содержащие значения переменных. Такое расположение данных позволяет скопировать формулу, введенную в строку 10. Кроме того, соблюдение такого принципа  построения табличных моделей позволяет легко изменять ограничения путем изменения значений соответствующих коэффициентов.

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

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

Рис. 5.3. Параметры для решения

В поле Установить целевую ячейку вводится адрес ячейки, содержащей значение целевой функции. Для данной модели это D7. Параметры области Равной необходимо установить максимальному значению, поскольку необходимо максимизировать значение. Поле Изменяя ячейки позволяет указать ячейки, в которых содержатся переменные модели: В4:С4.

Далее необходимо указать ограничения. Нажать кнопку Добавить  и сделать ссылку на диапазон D10:D14. Знак неравенства был установлен <=, переносим его в ограничения. В поле Ограничение вводим диапазон F10:F14.

Далее необходимо ввести второю группу ограничений: в поле Ссылка на ячейку вводим D15:D16, знак >=, в поле ограничение F15:F16. Возвращаемся в диалоговое окно Поиск решения.

Далее настраиваем параметры (кнопка Параметры, рис. 5.4).

Рис. 5.4. Диалоговое окно Параметры поиска решения

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

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

Рис. 5.5. Успешное завершение решения задачи оптимизации

При этом можно выбрать отчет о решении (рис. 5.6, 5.7).

В нашем примере получено следующее решение: надо производить 257,14 т краски типа А и 150 т краски типа Б, при этом будет получена прибыль в размере 889 285,71 руб.

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

Более существен для анализа чувствительности отчет по устой­чивости.

Рис. 5.6. Отчет по результатам

Рис. 5.7. Отчет по устойчивости

Первая табли­ца Изменяемые ячейки этого отчета дает информацию о значениях изменяемых ячеек:

адреса изменяемых ячеек;

их имена; если имен нет, то это поле остается пустым;

значения переменных в этих ячейках, найденные средством Поиск решения;

нормированная стоимость – это значение, равное нулю, если значение соответствующей переменной находится в границах своего возможного изменения, но не достигает этих границ (учитываются границы, которые задаются явно в виде неравенств типа х ≥ 0 и/или х ≤ 100). Если переменная равна значению одной из своих явно заданных границ (например, равна нулю при заданном усло­вии неотрицательности), то значение нормированной стоимости показывает, насколько изменится значение целевой функции, если значение этой переменной увеличится на единицу;

  целевой коэффициент – коэффициент, стоящий при данной изменяе­мой переменной в формуле целевой функции;

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

В таблице Ограничения приведена информация об ограничениях:

  адреса ячеек, на значения которых наложены ограничения;

  их имена (созданные заранее или составленные из заголовков строк и столбцов, на пересечении которых находятся изменяе­мые ячейки); если имен нет, то это поле остается пустым;

  значения в этих ячейках, найденные средством Поиск решения;

  теневая цена показывает, насколько изменится значение целе­вой функции, если на единицу изменится значение правой ча­сти данного ограничения; теневая цена отлична от нуля только тогда, когда данное ограничение в оптимальном решении явля­ется связанным (и решение не вырождено);

  значения правых частей ограничений;

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

Проведем анализ чувствительности. Во-первых, переменные решения нулевых значений не принимают. Рассмотрим ограничения. Первое ограничение, задающее предельный объем производства, лимитирующим (связанным) не является (на это прямо указывает отчет по результатам и нулевое значение теневой цены для этого ограничения в отчете по устойчивости). Отсюда следует вывод, что такой производственный план задействует мощности завода не в полной мере. Это большой «минус» данного плана.

Проанализируем, что сдерживает объемы производства. Лимитиру­ющими являются второе маркетинговое ограничение и ограничение по сырью 2 (на это указывает отчет по результатам и ненулевые зна­чения теневых цен для этих ограничений в отчете по устойчивости). Влиять на маркетинговое ограничение трудно, поскольку отдел маркетинга ставит свои условия, для изменений нужны веские обоснования, а их, конечно, нет. Чтобы полностью загрузить мощности производства, надо запланиро­вать еще почти 93 т краски, а такое увеличение производства краски типа Б нецелесообразно, так как даже объем в 150 т трудно продать.

Другое лимитирующее ограничение определяется наличием на складе запаса сырья 2. Разберемся с этим параметром. Взглянем на теневую цену этого ограничения, она равна 28 571,43. Это означает, что изменение на одну единицу величины правой части данного огра­ничения (т. е. изменение величины запаса сырья 2 на 1 т) при­ведет к изменению на 28 571,43 руб. величины прибыли (значения целевой функции). Очевидно, что в данном случае при увеличении значения правой части ограничения значения целевой функции будет возрастать, а при уменьшении – убывать. Насколько нужно уве­личить запас сырья 2, чтобы полностью загрузить все производствен­ные мощности, отчет по устойчивости ответа не дает.

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

Чтобы узнать, что же получится при изменении правой части пятого ограничения до величины 36,5, надо опять запускать Поиск решения. Итак, вносим в ячейку F13 значение 36,5 и выбираем коман­ду Сервис → Поиск решения. В диалоговом окне Поиск решения ничего менять не надо (средство Поиск решения сохраняет все установки сво­его предыдущего использования), можно сразу щелкнуть на кнопке Выполнить.

В этом решении х₁ = 350, x₂ = 150 и z = 1 075 000. Новым лимитирующим ограничением стало первое ограничение, задающее предельный объем производства. Нам повезло, что изменение только одного параметра модели (значения правой части ограничения по сырью 2) уже привело к решению (про­изводственному плану), где производственные мощности завода за­действованы полностью. В общем случае, если действительно есть не­обходимость задействовать все мощности производства, скорее всего, пришлось бы проверять другие лимитирующие ограничения и про­бовать изменять их правые части.

Оптимальным про­изводственным планом будет производство 350 т краски типа А и 150 т краски типа Б. Однако чтобы выполнить такой план, надо увеличить месячные запасы сырья 2 на 6,5 т, а месячные за­пасы сырья 1 и сырья 3 можно уменьшить на 17,5 и 0,5 т соответ­ственно. Это уже не совсем очевидный результат. Но и этот резуль­тат можно было получить другим способом, поскольку нетрудно подсчитать необходимые запасы сырья для производства 350 т краски типа А и 150 т краски типа Б. Затем надо подсчитать, на сколько увеличится (и уве­личится ли) себестоимость краски, если докупить дополнительные объемы сырья 2, так как возрастут расходы на хра­нение сырья. Это может повлиять на удельную прибыль краски, т. е. могут измениться значения коэффициентов при переменных в фор­муле целевой функции. А если это произойдет, то все вычисления надо начинать сначала. Кроме того, надо вспомнить, что значения этих коэффициентов известны нам только приближенно.

 Рекомендуемая литература: [7, 14, 16, 18, 20, 21, 22].