Как решить двойственную задачу линейного программирования в excel

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

Изучив алгоритмы "ручного" решения задач линейного программирования, полезно познакомиться и со способом упростить этот процесс. Ясно, что чем сложнее задача, чем больше в ней переменных и условий, тем утомительнее и дольше ее решать. В таких случаях удобно использовать специальные математические пакеты, или доступную многим программу MS Excel (версии 2003, 2007, 2010, 2013 и др.).

Решить задачи линейного программирования в Excel достаточно просто:

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

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

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

Линейное программирование: примеры в Excel

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

Задача 2. Цех производит 8 различных видов деталей для двигателей A, B, C1, C2, C3, D, E6, F имея в своем распоряжении перечисленный ниже парк из 7 видов универсальных станков: 2 шт. -ADF, 3 шт. -SHG, 3 шт. -BSD, 1 шт. -AVP, 1 шт. -BFG, 3 шт. -ABM, 2 шт. -RL.
Время, требуемое для обработки единицы каждого продукта на каждом станке, вклад в прибыль от производства единицы каждого продукта и рыночный спрос на каждый продукт за месяц даны в таблице.
Цех работает 12 часов в день. Каждый месяц содержит 26 рабочих дней. Для упрощения задачи считаем, что возможен произвольный порядок обработки деталей на различных станках.
Составьте оптимальный план производства.
Определите, производство каких продуктов лимитировано рынком, и каких – техническими возможностями цеха. Какие машинные ресурсы должны быть увеличены в первую очередь, чтобы добиться максимального увеличения прибыли (при заданных потребностях рынка)?
Есть ли продукт, который невыгодно производить? Почему? Что нужно изменить, чтобы все продукты стало выгодно производить?

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

Задача 4. Фирма "Компьютер-сервис" поставляет компьютеры под ключ четырех базовых комплектаций: «домашний», «игровой», «офисный» и «экстрим». Известны средние затраты времени на сборку, проверку и подключение компьютеров. Каждый компьютер приносит определенный уровень прибыли, но спрос ограничен. Кроме того, в плановом периоде ограничен ресурс человеко-часов, отведенных на выполнение каждой производственной операции. Определить, сколько компьютеров каждого типа необходимо произвести в плановом периоде, имея целью максимизировать прибыль.

Задача 5. На лесопилку поступают доски длиной 10 м. По контракту лесопилка должна поставить клиенту не менее 100 досок длиной 5 м, не менее 200 досок длиной 4 м и не менее 300 досок длиной 3 м. Как работникам лесопилки выполнить условия контракта, разрезав наименьшее количество досок?

Задача 6. Компания "Евростройтур" организует экскурсионные автобусные туры по странам Европы. Компания получила 4 новых автобуса и предполагает направить их на маршруты во Францию, Италию, Чехию и Испанию. Каждый автобус обслуживают 2 водителя. Компанией приглашены 8 водителей, в различной степени знакомых с дорогами европейских стран (в % от экскурсионного маршрута).
Необходимо распределить водителей так, чтобы общий показатель освоения маршрутов был максимальным.

Задача 7. Решить задачу методом ветвей и границ, решая отдельные задачи линейного нецелочисленного программирования с помощью функции "Поиск решения" в Microsoft Excel (в случае, если первая же задача ЛП выдает целочисленное решение, не позволяя ветвить задачу, немного изменить начальные условия).
Состав еды рядовых регламентируется верховной ставкой главнокомандующего, которая устанавливает нижние нормы питания в сутки по основным компонентам: 1500 килокалорий, 100 г белков, 280 г углеводов, 90 г жиров, 1 кг воды. На складах есть 4 вида продуктов, которые выдают защитникам Родины сухим пайком: лимонад, тушенка в маленьких банках, унифицированные наборы горбушек и пирожки с ежевикой. Стоимость этих четырех продуктов соответственно 12 руб., 34 руб., 3 руб. и 20 руб. Какова минимальная сумма, которую должен затратить прапорщик на питание одного солдата?

Задача 8. Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить a11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа.
На изготовление единицы Изделия 2 требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа.
Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно.
Рыночная цена единицы Изделия 1 составляет c1 тыс. руб., а единицы Изделия 2 — c2 тыс.руб.
Требуется:
1) построить экономико – математическую модель задачи;
2) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.
3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования.
4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL.

Линейное программирование в Excel

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:

Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel , необходимо выполнить следующие действия:
1. Ввести условие задачи:
a) создать экранную форму для ввода условия задачи:
· переменных,
· целевой функции (ЦФ),
· ограничений,
· граничных условий;
b) ввести исходные данные в экранную форму:
· коэффициенты ЦФ,
· коэффициенты при переменных в ограничениях,
· правые части ограничений;
c) ввести зависимости из математической модели в экранную форму:
· формулу для расчета ЦФ,
· формулы для расчета значений левых частей ограничений;
d) задать ЦФ (в окне "Поиск решения" ):
· целевую ячейку,
· направление оптимизации ЦФ;
e) ввести ограничения и граничные условия (в окне "Поиск решения" ):
· ячейки со значениями переменных,
· граничные условия для допустимых значений переменных,
· соотношения между правыми и левыми частями ограничений.
2. Решить задачу:
a) установить параметры решения задачи (в окне "Поиск решения" );
b) запустить задачу на решение (в окне "Поиск решения" );
c) выбрать формат вывода решения (в окне "Результаты поиска решения" ).

Рассмотрим подробно использование MS Excel на примере решения следующей задачи.

Фабрика "GRM pic" выпускает два вида каш для завтрака — "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основ­ном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.

Управляющему производством Джою Дисону необходимо разработать план производства на месяц. В приведенной ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т продукта.

Цех Необходимый фонд рабочего времени
чел.-ч/т
Общий фонд рабочего времени
чел.-ч. в месяц
"Crunchy" "Chewy"
А. Производство 10 4 1000
В. Добавка приправ 3 2 360
С. Упаковка 2 5 600

Доход от производства 1 т "Crunchy" составляет 150 ф. ст., а от производства "Chewy" — 75 ф, ст. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.

а) Сформулировать модель линейного программирования, максимизи­рующую общий доход фабрики за месяц.

б) Решить ее c помощью MS Excel.

Ввод исходных данных
Создание экранной формы и ввод исходных данных

Экранная форма для решения в MS Excel представлена на рисунке 1.

В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (x1), C4 (x2), коэффициентам ЦФ соответствуют ячейки B6 (c1=150), C6 (c2=75), правым частям ограничений соответствуют ячейки D18 (b1=1000), D19 (b2=360), D20 (b3=600) и т.д.

Ввод зависимостей из формальной постановки задачи в экранную форму

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

Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций" , который можно вызвать из меню "Вставка" или при нажатии кнопки fx (рисунок 2) на стандартной панели инструментов.

Рисунок 2

Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:
· курсор в поле D6;
· нажав кнопку fx , вызовите окно "Мастер функций — шаг 1 из 2";
· выберите в окне "Категория" категорию "Математические";
· в окне "Функция" выберите функцию СУММПРОИЗВ (рис. 3);

Рисунок 3
· в появившемся окне "СУММПРОИЗВ" в строку "Массив 1" введите выражение B$4:C$4 , а в строку "Массив 2" — выражение B6:C6 (рис. 4);

Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи ( B3, C3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения ( B13, C13 — 1-е ограничение; B14, С14 — 2-е ограничение и B15, С15 — 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Таблица 1.

Формулы, описывающие ограничения модели (1)

Левая часть ограничения Формула Excel
10x1+4x2 или B3×B13+C3×C13 =СУММПРОИЗВ(B4:C4;B13:C13))
3x1+2x2 или B3×B14+C3×C14 =СУММПРОИЗВ(B4:C4;B14:C14))
2x1+5x2 или B3×B15+C3×C15 =СУММПРОИЗВ(B4:C4;B15:C15)

Дальнейшие действия производятся в окне "Поиск решения" , которое вызывается из меню "Сервис" (рис.5):

· поставьте курсор в поле "Установить целевую ячейку" ;

· введите адрес целевой ячейки $D$6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;

· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".

Ввод ограничений и граничных условий
Задание ячеек переменных

В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $B$4:$С$4 . Необходимые адреса можно вносить в поле "Изменяя ячейки" и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных

В нашем случае на значения переменных накладывается только граничное условие неотрицательности, то есть их нижняя граница должна быть равна нулю (см. рис. 1).
· Нажмите кнопку "Добавить" , после чего появится окно "Добавление ограничения" (рис.6).
· В поле "Ссылка на ячейку" введите адреса ячеек переменных $B$4:$С$4 . Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.
· В поле знака откройте список предлагаемых знаков и выберите ≥ .
· В поле "Ограничение" введите 0.

Рис.6 — Добавление условия неотрицательности переменных задачи (1)

Задание знаков ограничений ≤ , ≥ , = .
· Нажмите кнопку "Добавить" в окне "Добавление ограничения" .
· В поле "Ссылка на ячейку" введите адрес ячейки левой части конкретного ограничения, например $B$18 . Это можно сделать как с клавиатуры, так и путем выделения мышью нужной ячейки непосредственно в экранной форме.
· В соответствии с условием задачи (1) выбрать в поле знака необходимый знак, например, ≤ .
· В поле "Ограничение" введите адрес ячейки правой части рассматриваемого ограничения, например $D$18 .
· Аналогично введите ограничения: $B$19 , $B$20 .
· Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK .

Окно "Поиск решения" после ввода всех необходимых данных задачи (1) представлено на рис. 5.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис. 5).

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

Задача запускается на решение в окне "Поиск решения" . Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).

Рис. 7 — Параметры поиска решения, подходящие для большинства задач ЛП

Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Подтвердите установленные параметры нажатием кнопки "OK" .

Запуск задачи на решение
Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить" .

После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения" с сообщением об успешном решении задачи, представленном на рис. 8.

Рис. 8 -. Сообщение об успешном решении задачи

Появление иного сообщения свидетельствует не о характере оптимального решения задачи, а о том, что при вводе условий задачи в MS Excel были допущены ошибки, не позволяющие MS Excel найти оптимальное решение, которое в действительности существует.
Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие MS Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.
В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы" . Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку "OK" . После этого в экранной форме появляется оптимальное решение задачи (рис. 9).

Ссылка на основную публикацию