Решение задачи ЛП средствами MS Excel

Рассмотрим технологию решения на примере задачи оптимального использования ресурсов.

Пример 2.5. Исходные данные для иллюстрации метода возьмем из примера 2.1. Экономико-математическая модель задачи имеет вид:

найти

при ограничениях на ресурсы

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

Рис. 2.1. Шаблон решения примера 2.1 с исходными данными.

Блок ячеек B3:E3 зарезервирован под искомые значения переменных Х. Переменным присвоены единичные значения, что можно рассматривать как начальную точку для поисковой процедуры. Кроме того, легко проверить безошибочность введенных формул: числа в столбце G равняются сумме чисел по строкам;

Блок ячеек B5:E5 содержит коэффициенты целевой функции (цены продаж);

Блок ячеек B8:E10 содержит коэффициенты матрицы ограничений (нормативы затрат ресурса на единицу изделия);

Блок ячеек I8:I10 содержит значения правых частей ограничений (лимит имеющихся в наличии ресурсов);

Формулы для расчета значения целевой функции (ЦФ) и значений левых частей ограничений приведены в нижеследующей таблице:

Адрес ячейки	Формула
G5	=СУММПРОИЗВ(B3:E3;B5:E5)
G8	=СУММПРОИЗВ(B3:E3;B8:E8)
G9	=СУММПРОИЗВ(B3:E3;B9:E9)
G10	=СУММПРОИЗВ(B3:E3;B10:E10)

В главном меню выбираем пункт Данные и нажимаем кнопку Поиск решения и заполняем открывшееся диалоговое окно (рис. 3.2.) и нажимаем кнопку Выполнить:

Рис. 2.2. Исходные данные для запуска процедуры численного решения задачи.

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

В ячейках B3:E3 мы видим оптимальные значения переменных:

В ячейке I5 число 181 означает максимальный объем выручки, соответствующий найденной оптимальной структуре выпуска продукции.

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

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

Рассмотрим модели исходной(прямой) и двойственной задач в общем виде.

Прямая задача (ПЗ):

Двойственная задача (ДЗ):

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

1) Вводятся переменные y_i, число которых соответствует числу ограничений ПЗ;

2) Характер экстремума в ДЗ меняется на противоположный;

3) Знак неравенств в ДЗ меняется на противоположный;

4) Коэффициенты целевой функции c_j ПЗ становятся правыми частями ограничений ДЗ;

5) Правые части ограничений b_i ПЗ становятся коэффициентами целевой функции Д З;

6) Матрица А, составленная из коэффициентов a_ij при переменных ПЗ транспонируется в ДЗ;

7) Число ограничений в ДЗ равняется числу переменных в ПЗ.

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

Теоремы двойственности

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

1) Если X₀ и Y₀ допустимые решения прямой и двойственной задач, то

то есть значения целевой функции ПЗ никогда не превышают значения целевой функции ДЗ;

2) Если X₀ и Y₀ допустимые решения прямой и двойственной задач и если

то X₀ и Y₀ оптимальные решения прямой и двойственной задач, то есть X₀ = X^* и Y₀ = Y*;

3) Для того, чтобы допустимые решения прямой и двойственной задач стали оптимальными, необходимо и достаточно, необходимо и достаточно, чтобы выполнялись следующие условия:

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

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

Рассмотрим построение двойственной задачи и её решение с использованием теорем двойственности на предыдущем примере.

Пример 2.6. Исходная задача о распределении ресурсов (прямая задача), рассмотренная в примере2.1. имеет вид:

найти

при ограничениях на ресурсы

Оптимальное решение прямой задачи:

В соответствии с правилами 1) – 7) двойственная задача имеет вид:

найти

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

Подставим оптимальные значения переменных x_j^* в систему ограничений прямой задачи:

Так как первое неравенство выполняется как строгое, из условия (2.4) следует, что y₁^* = 0.

Так как х₁^* ≠ 0 и х₂^* ≠ 0, то из условия (2.5) следует, что первое и второе ограничения двойственной задачи должны быть равенствами. С учетом, что y₁^* = 0 имеем систему уравнений:

решая которую, находим y₂^* = 1/28 и y₃^* = 4/7. Таким образом, оптимальное решение двойственной задачи равно:

y₁^* = 0; y₂^* = 1/28 = 0,036; y₃^* = 4/7 = 0,571.

Подставим эти значения в целевую функцию двойственной задачи.

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

Переменные y₂^* и y₃^* соответствуют ограничениям на сырьё и оборудование. Их оптимальные решения показывают, что каждая дополнительный кг сырья даст прирост прибыли на 1/28 тыс. руб., а каждый дополнительный станко/час обеспечит прирост прибыли на 4/7 тыс. руб.

Решение двойственной задачи в среде MS Excel

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

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

Постоптимизационный анализ

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

Для этого необходимо повторно запустить программу Поиск решения для прямой задачи ЛП. После её выполнения появится следующее диалоговое окно Результат поиска решения (рис.2.3). Далее необходимо выбрать тип отчета Устойчивость. В низу таблицы появится новый рабочий лист Excel с именем Отчет по устойчивости (рис. 2.4).

В первых трех строках указаны реквизиты отчета.

Рис. 2.3. Диалоговое окно Результаты поиска решения

В таблице отчета Изменяемые ячейки содержатся следующая информация:

• Адреса ячеек, выделенные под переменные Х и наименование переменных (столбцы В и С);

• Оптимальные значения переменных (столбец D);

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

• Разность значений правых и левых частей ограничений двойственной задачи (столбец «Нормируемая стоимость»). По сути они характеризую «уровень технологичности» производства того или иного изделия. В нашем примере нетехнологичными оказались переменные Х3 и Х4 (гобелены «Меланхолия» и «орнамент») поэтому их объемы производства равны нулю;

• Коэффициенты целевой функции (столбец F);

• Нижний и верхний пределы изменения коэффициентов целевой функции, внутри которых сохраняется найденное решение (столбцы G и H). По сути, это допустимы диапазон цен на изделия Х, внутри которого структура оптимального решения не изменится. Например, независимо от того, увеличим мы цену изделия Х₁ на 0.3 (300 руб.) или уменьшим её на 0.1 (100 руб.), наиболее выгодные объемы выпуска продукции останутся прежними: Х₁^* = 56, Х₂^* = 7, Х₃^* = 0, Х₄^* = 0.

В таблице отчета Ограничения содержатся следующая информация:

• В ячейках В17:С19 располагаются адреса и имена ограничений задачи по ресурсам;

• В столбце D: «Результативное значение», приведены объемы фактически израсходованных ресурсов;

• В столбце «Теневая цена» расположены оптимальные значения переменных двойственной задачи. Мы видим, что ресурс «труд» используется не полностью, поэтому его теневая цена равна нулю;

• В столбце F размещаются значения правых частей ограничений прямой задачи, то есть предельные значения объемов ресурсов, которыми располагает предприятие;

• В ячейках В17:С19 располагаются допустимые пределы изменения Нижний и верхний пределы изменения запасов ресурсов. Эта информация важна с точки зрения принятия решения о дополнительном вовлечении ресурсов в производство с целью увеличения объемов выпуска продукции: привлечение дополнительных ресурсов или их сокращение приведет к изменению объемов производства и, соответственно, к увеличению или снижении прибыли. Поскольку целью задачи является увеличение прибыли, то вариант уменьшения лимита ресурса рассматривать нецелесообразно. Рассмотрим дополнительное привлечение ресурсов:

Ресурс «Труд». Его допустимое увеличение неограниченно. Однако делать это нецелесообразно, так как его теневая цена равна 0, поэтому дополнительное привлечение рабочей силы не приведет к росту прибыли.

Ресурс «Оборудование». Его допустимое увеличение равно 520 станко/часам. Каждый дополнительный станко/час даст прирост прибыли на 0,036 тыс. руб. (теневая цена). Увеличим лимит этого ресурса на 500 ед., тогда прирост прибыли составит ∆f = 0,036∙500 = 18 тыс. руб.

Ресурс «Сырьё». Его допустимое увеличение равно 50 кг. Каждый дополнительный кг даст прирост прибыли на 0,571 тыс. руб. (теневая цена). Увеличим лимит этого ресурса на 45 ед., тогда прирост прибыли составит ∆f = 0,571∙45 = 25,7 тыс. руб. ≈ 26 тыс. руб.

Посмотрим, как отразятся эти изменения на оптимальной структуре выпуска. Для этого скорректируем правые части ограничений в таблице (рис.2.1) и запустим программу поиск решения:

Из таблицы видно, что прибыль увеличилась на рассчитанные 44 тыс.руб. Изменились и объемы производства, однако структура выпуска сохранилась – изделия третьего и четвертого видов выпускать нецелесообразно.

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

1) Записать формальную задачу ЛП;

2) Решить задачу с помощью средств MS Excel (надстройка Поиск решения);

3) Составить двойственную задачу ЛП;

4) Решить двойственную задачу с использованием теорем двойственности;

5) Осуществить проверку правильности решения двойственной задачи с помощью средств MS Excel (надстройки Поиск решения).

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

С графическим методом решения ЗЛП и примерами решения подобных задач можно ознакомиться в литературе /1, стр. 53-60/, технологией оптимизации в среде MS Excel – в/2, стр. 28-48/. Кроме того, полезно дополнительно привлечь литературу /3,4,11/.

Контрольные задания по теме 2

Вариант 1. Инвестор, располагающий суммой в 300 тыс. ден. ед., может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс. ден. ед. Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?

Вариант 2. Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:

Корма   Питательные вещества	Количество питательных веществ в 1 кг корма
А В
Цена 1 кг корма, т.руб.	0,2	0,3

Вариант 3. Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Вариант 4. На имеющихся у фермера 400 гектарах земли он планирует посеять кукурузу и сою. Сев и уборка кукурузы требует на каждый гектар 200 ден. ед. затрат, а сои – 100 ден. ед. На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. ден. ед.. Каждый гектар, засеянный кукурузой, принесет 30 центнеров, а каждый гектар, засеянный соей – 60 центнеров. Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему 3 ден. ед., а каждый центнер сои – 6 ден. ед. Однако, согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. центнеров.

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

Вариант 5. Продукция двух видов (краска для внутренних (I) и наружных (Е) работ) поступает в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно. Расходы продуктов А и В на 1 т соответствующих красок приведены в таблице.

Исходный продукт	Расход исходных продуктов на тонну краски, т	Максимально возможный запас, т
Краска Е	Краска I
А В

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3000 ден. ед. для краски Е и 2000 ден. ед. для краски I.

Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Вариант 6. Финансовый консультант фирмы «АВС» консультирует клиента по оптимальному инвестиционному портфелю. Клиент хочет вложить средства (не более 25000$) в два наименования акций крупных предприятий в составе холдинга «Дикси». Анализируются акции «Дикси –Е» и «Дикси –В». Цены на акции: «Дикси –Е» - 5$ за акцию; «Дикси –В» - 3$ за акцию. Клиент уточнил, что он хочет приобрести максимум 6000 акций обоих наименований, при этом акций одного из наименований должно быть не более 5000 штук.

По оценкам «АВС» прибыль от инвестиций в эти две акции в следующем году составит: «Дикси –Е» - 1,1$; «Дикси –В» - 0,9$.

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

Вариант 7. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей Х и Y. Фонд рабочего времени равен 4000 чел.-ч в неделю. Для производства одной детали типа Х требуется 1 чел./ч, а для производства одной детали типа Y – 2 чел./ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей Х и 1750 деталей Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику. По профсоюзному соглашению общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ден. ед., а от производства одной детали типа Y – 40 ден. ед.?

Вариант 8. Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁ S₂ и S₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице:

Питательное вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
I	II
S1 S2 S3

Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.

Необходимо составить дневной рацион, имеющий минимальную стоимость.

Вариант 9. При производстве двух видов продукции используется 4 типа ресурсов. Норма расхода ресурсов на производство единицы продукции, общий объем каждого ресурса заданы в таблице:

Ресурсы	Норма затрат ресурсов на товары	Общее количество ресурсов
1-го вида	2-го вида

Прибыль от реализации одной единицы продукции первого вида составляет 2 ден. ед., второго вида – 3 ден. ед.

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

Вариант 10. Фирма производит вида два безалкогольных напитков – «Лимонад» и «Тоник». Однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л «Лимонада» требуется 0,02 ч работы оборудования, а для производства 1 л «Тоника» – 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Прибыль фирмы составляет 0,10 ден. ед. за 1 л «Лимонада» и 0,30 ден. ед. за 1 л «Тоника».

Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли?