Решение двойственной задачи в excel поиск решения
Цель работы: изучение возможности проведения анализа решения оптимизационных задач в Excel и решения задач целочисленного программирования в Excel.
1.Используя задание предшествующей работы, решить задачу оптимизации.
Ресурс | Прод 1 | Прод 2 | Прод 3 | Прод 4 | Наличие |
Прибыль | |||||
Труд | |||||
Оборуд. | |||||
Сырье |
Математическая модель задачи:
F = 15 Х1 + 24 Х2 + 19 Х3 + 27 Х4 → MAX
Xj>=0 j=1-4
где Xj - количество выпускаемой продукции j-го типа;
bj - количество располагаемого ресурса i-го вида;
aij - норма расхода i-го ресурса для выпуска единицы продукции j-го типа;
сij - прибыль, получаемая от реализации единицы продукции j-го типа.
После успешного решения задачи на экране появляется диалоговое окно Результат поиска решения. (Решение найдено). С помощью этого окна можно вызвать отчеты трех типов: результаты; устойчивость; пределы.
Отчет по результатам.
Показывает в графе Разница количество неиспользованного ресурса.
Отчет по устойчивости.
Нормированная стоимость - дополнительные переменные в двойственной задаче, показывающие насколько изменится целевая функция при принудительном включении единицы этой продукции в оптимальное решение. Допустимые переменные значения изменения коэффициентов целевой функции и ресурсов, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение (при выходе за эти границы будет выгоден выпуск другой продукции в иных пропорциях).
Теневая цена - двойственные оценки переменных прямой исходной задачи, которые показывают, как изменится целевая функция при изменении ресурсов на единицу.
Отчет по пределам.Показывает значение целевой функции при выпуске каждого из типов продукции на нижнем пределе (по умолчанию - это ноль, т.е. при невыпуске данной продукции).
Провести серию экспериментов на модели для значений ресурса "Сырье"- 50; 100; 150; 200; 250; 300; 350; 400.
Удалить результат решения - выделить область таблицы, содержащую значения переменных (В3:Е3); нажать клавишу " ← Delete"; убрать выделение (клавиша "Esc" или щелкнуть левой кнопкой мыши по свободному полю).
Ввести в ячейку правой части ограничения по сырью (ячейка Н11) значение 50.
Верхнее меню\ Сервис\Поиск решения\Выполнить.
Результаты поиска решения. Сохранить сценарий.
Ввести имя сценария (сырье=50). ОК. ОК.
Выпонить решение для всех значений ресурса "Сырье".
Представление результатов решения.
Верхнее меню\ Сервис\Сценарии.
Диспетчер сценариев. Отчет. Структура. ОК.
3.Решить задачу при назначении граничных условий на все виды выпускаемой продукции 1 ≤ Xj ≤ 5. Ввести эти условия в ячейки для нижней и верхней границ значений переменных (В4:Е4 и В5:Е5).
4.Решить задачу с иной целевой функцией: минимизация используемых ресурсов при заданном результате.
Ввести новую целевую функцию в свободную ячейку, например (I4).
5.Решение задач целочисленного программирования
Верхнее меню\ Сервис\Поиск решения\Добавить
Для каждого значения переменных добавить ограничения на челочисленность получаемых результатов:
В 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 |
а) Сформулировать модель линейного программирования, максимизирующую общий доход фабрики за месяц.
б) Решить ее 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) представлено на рис. 5.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис. 5).
Решение задачи
Установка параметров решения задачи
Задача запускается на решение в окне "Поиск решения" . Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).
Рис. 7 - Параметры поиска решения, подходящие для большинства задач ЛП
Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Подтвердите установленные параметры нажатием кнопки "OK" .
Запуск задачи на решение
Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить" .
Пример. Бумажная фабрика использует для производства продукции два вида учитываемых ресурсов: целлюлозу и электроэнергию. Фабрика производит бумагу для ксероксов, упаковочную бумагу, цветную бумагу для художественного творчества и бумагу для писем.
Затраты ресурсов на производство одной тонны продукции каждого вида указан в следующей таблице:
Целлюлоза Электроэнергия
Бумага для ксероксов. 0,7 т. 15% 1.2 кВт
Упаковочная бумага. 0,4 т. 20% 1.0 кВт
Бумага для художественного творчества. 0,5 т. 1.8 кВт
Писчая бумага. 0,7 т. 0,0 кВт
В течение рабочего дня фабрика может использовать до 30 т. целлюлозы и до 100 кВт электроэнергии. Планом предусматривается, что производство бумаги для ксероксов составляет 15% от общего выпуска продукции, а производство упаковочной бумаги - 30% от общего выпуска. Стоимость одной тонны производимой продукции соответственно равна 20,12,24 и 15 тыс. руб.
Правление бумажной фабрики в таком производственном плане, который: а) максимизирует стоимость произведенной продукции б) максимизирует суммарный объем произведенной продукции.
Задание: Построить экономико-математическую модель линейного программирования, соответствующую задаче (а). Построить модель линейного программирования, соответствующую задаче (б).
Алгоритм решения двойственного симплекс-метода в Excel
- Подготовить форму для решения. Сделать это можно при помощи сервиса.
- Выполнить команду Сервис/Поиск решения
- В окне Параметры указать Линейная модель, Неотрицательные значения.
- Выбрать целевую ячейку, добавить ограничения-условия.
Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.
В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:
Далее в открывшемся списке нужно выбрать Надстройки, затем установить курсор на пункт Поиск решения, нажать кнопку Перейти и в следующем окне включить пакет анализа.
- Загрузите файл шаблон для проверки в Excel
- Откройте его в MS Excel
- Мышкой или с помощью клавиатуры перейдите к ячейке G4
- Выполните команду Сервис / Поиск решения
Иногда задание звучит следующим образом: расчеты осуществить на ЭВМ, привести распечатку полученных результатов.
- Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях.
- Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
- Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.
Пример. В библиотеке работают 6 пожилых уборщиц. Каждая из них по своим физическим возможностям и состоянию здоровья может выполнять только определенные виды работ, причем с определенной производительностью. Площадь каждой из работ известна. Нужно добиться минимума времени на уборку помещений.
ПРОИЗВОДИТЕЛЬНОСТЬ БАБУШЕК м 2 . /мин | |||||||
Баба Аня | Белла Петровна | Баба Варя | Баба Галя | Домна Ивановна | Евгения Карловна | Площадь работ | |
Мытье окон | 2 | 0 | 0 | 1 | 0 | 0 | 46 |
Мытье полов | 0 | 1 | 0 | 0 | 0 | 0 | 300 |
Протирка столов | 0 | 0 | 2 | 0 | 0.2 | 1 | 50 |
Чистка дорожек | 0 | 0 | 0 | 2 | 0 | 4 | 100 |
Пример.На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
Найти оптимальное соотношение количества кормов и численности поголовья лис и песцов.
Алгоритм получения решения задачи симплекс-методом с использованием офисного приложения Microsoft Excel рассмотрим на примере 2.2.1. Математическая модель задачи имеет следующий вид:
Для получения решения исходной задачи будем использовать надстройку «Поиск решения».
Ввод исходных данных задачи
При решении задачи линейного программирования симплекс-методом с использованием офисного приложения Microsoft Excel необходимо сначала ввести данные задачи. Для этого создается новая рабочая книга Microsoft Excel, в свободные ячейки которой вносятся коэффициенты целевой функции, левой части ограничений, значения правой части ограничений.
Экранная форма для ввода условий задачи имеет следующий вид
(рис. 2.2.2):
В ячейках В4:С4 находятся значения коэффициентов целевой функции; в массиве В6:С8 –коэффициенты левой части ограничений; в столбце Е6:Е8значения правой части ограничений. Ячейки В2:С2соответствуют переменным задачи, а в ячейке Е2будет отображаться значение целевой функции. Сюда необходимо ввести формулу, по которой это значение рассчитывается, то есть . Для этого курсор ставится в ячейку и далее набирается следующее выражение: .
Имена ячеек можно набирать непосредственно с клавиатуры, либо делая на них ссылку мышью.
Значение целевой функции также можно рассчитать, используя надстройку «Мастер функций», а именно, функцию «СУММПРОИЗВ». Для этого необходимо выполнить следующие действия:
поставить курсор в поле Е2;
выбрать на панели инструментов кнопку ;
в окне «Категория» выбрать «Математические». В окне «Выберите функцию» «СУММПРОИЗВ» (рис. 2.2.3) и нажать «ОК»;
Ввести аргументы функции: в строку «Массив 1» выражение В2:С2, а в строку «Массив 2» выражение В4:С4 (можно, выделять соответствующие массивы с помощью мыши) (рис. 2.2.4) и нажать «ОК»;
После этого в ячейке Е2 появится текущее значение целевой функции, вычисленное по введенной формуле. Оно равно нулю, так как переменные в данный момент равны нулю.
Аналогично в ячейки D6:D8вводятся формулы для расчета левых частей ограничений (рис. 2.2.5):
Для ячейкиD6формула имеет вид ,а ее реализация в ячейке: или =СУММПРОИЗВ(В2:C2; В6:C6).
Для ячейкиD7формула имеет вид ,а ее реализация в ячейке: или = СУММПРОИЗВ(В2:C2; В7:C7).
Для ячейкиD8формула имеет вид ,а ее реализация в ячейке: или = СУММПРОИЗВ(В2:C2; В8:C8).
Как видно, формулы для расчета левой части ограничений отличаются друг от друга только именем второго массива (строчки коэффициентов ограничения), первый же массив (массив значений переменных) один и тот же. Поэтому можно ввести формулу один раз, а затем скопировать ее, сделав абсолютную ссылку на массив переменных В2:C2.
Для того, чтобы сделать абсолютную ссылку на определенный столбец, необходимо поставить символ $, перед буквой, обозначающей имя столбца. Например $В2:$C2.Чтобы зафиксировать строку, символ $, ставится перед номером строки: В$2:C$2.Если необходимо сделать абсолютную ссылку на конкретную ячейку (ячейки), символ $ ставится и перед именем столбца и перед номером строки: $В$2:$C$2.
Абсолютную ссылку на ячейку (ячейки) можно сделать, нажав клавишу F4, когда курсор находится в поле имени ячейки. При однократном нажатии клавиши будет сделана абсолютная ссылка на массив или ячейку ($В$2: $C$2). Если клавишу нажать дважды, будет сделана абсолютная ссылка на номер строки (В$2: C$2). При следующем нажатии клавиши ссылка будет сделана на имя столбца ($В2: $C2).
При данном способе реализации симплекс-метода достаточно сделать ссылку лишь на соответствующую строку: В$2: C$2. В то же время допустима и абсолютная ссылка на конкретный массив ячеек: $В$2: $C$2.
Таким образом, для ячейки D6формула будет иметь вид или = СУММПРОИЗВ(В$2: C$2;В6:C6) (в случае абсолютной ссылки на массив = СУММПРОИЗВ($В$2: $C$2;В6:C6)).
Затем эту формулу необходимо скопировать в ячейки D7иD8.Копировать формулу можно с помощью клавиш «Ctrl-Insert» копировать и клавиш «Shift-Insert» вставить. Другой способ копирования формул поставить курсор в ячейку, содержащую формулу и протянуть ее за правый нижний угол на все ячейки, в которые ее необходимо скопировать.
После этого экранная форма условий задачи будет иметь вид (рис. 2.2.6).
Для получения решения задачи используется надстройка «Поиск решения», которая находится в меню «Сервис».
В диалоговом окне «Поиск решения» (рис. 2.2.7) необходимо выполнить следующие действия:
Поставить курсор в поле «Установить целевую ячейку» и ввести адрес ячейки, в которой находится формула для расчета значения целевой функции (можно сделать ссылку на ячейку мышью). В примере это ячейка E2.
Выбрать критерий оптимизации целевой функции (максимизация, минимизация или точное значение). В примере это максимум.
Поставить курсор в поле «Изменяя ячейки» и ввести адрес массива, в котором находятся значения переменных. В примере это В2:C2.Адрес можно внести также с помощью выделения мышью соответствующих ячеек.
В окне «Ограничения» выбрать кнопку «Добавить», после чего появится окно «Добавление ограничения» (рис. 2.6.8).
В поле «Ссылка на ячейку» ввести адрес ячейки, в которой содержится левая часть ограничения. (Это можно сделать путем выделения мышью соответствующей ячейки на экране). В поле знака открыть список предлагаемых знаков и выбрать нужный. В поле «Ограничения» ввести адрес ячейки, содержащей правую часть ограничений. В примере первое ограничение: D6в диалоговом окне представлено следующим образом (рис. 2.2.9)
Нажать кнопку «Добавить»и аналогично ввести остальные ограничения. Если при вводе ограничений задачи возникает необходимость изменить или удалить ограничения, то для этого используются кнопки «Изменить» и «Удалить» соответственно.
Диалоговое окно надстройки «Поиск решения» после ввода данных имеет следующий вид (рис. 2.2.10)
Для обеспечения выполнения условия неотрицательности переменных, а также установления конкретных параметров решения задачи оптимизации используется кнопка «Параметры» (рис. 2.2.11)
Установка флажка «Линейная модель» обеспечивает ускорение процесса решения линейной задачи, а установление флажка «Неотрицательные значения» неотрицательность переменных.
Подтверждаются установленные параметры нажатием кнопки «ОК».
В окне «Результат поиска решения» приведены типы отчета: «Результаты», «Устойчивость», «Пределы», которые используются для анализа чувствительности. Чтобы получить отчет, необходимо выбрать соответствующий тип и нажать кнопку «ОК». Результаты каждого отчета будут выведены на отдельных листах рабочей книги с названиями: «Отчет по результатам 1», «Отчет по устойчивости 1», «Отчет по пределам 1» (рис. 2.2.13)
Если необходимо получить только решение задачи, достаточно нажать кнопку «ОК» в диалоговом окне «Результат поиска решения» (рис. 2.2.12), после чего на экране в соответствующих ячейках появятся значения переменных и целевой функции. В нашем примере значения переменных находятся в ячейках В2:C2,а значение целевой функции – в ячейке E2(рис. 2.2.14).
Итак, решение задачи найдено: .
Заметим, что надстройка «Поиск решения» позволяет получать решение и в том случае, если в условии задачи все или некоторые переменные могут принимать только целые значения. Для получения целочисленного решения приведенной выше задачи в описанный процесс необходимо внести некоторые дополнения.
Дополнения вносятся на этапе ввода ограничений. К имеющимся в задаче ограничениям необходимо добавить условие целочисленности переменных. Для этого в диалоговом окне «Поиска решения» надо выбрать кнопку «Добавить», в поле «Ссылка на ячейку» ввести адрес ячеек, содержащих значения переменных (в примере это ячейки В2:С2),а в поле ввода знака ограничения выбрать целое(цел). (рис.2.2.15)
Подтверждается ввод условия целочисленности нажатием кнопки «ОК». Если задача имеет альтернативное решение, то с помощью компьютера получаем только одно решение.
Чтобы провести анализ чувствительности, необходимо в диалоговом окне «Результаты поиска решения» выделить с помощью мыши требуемый тип отчета: «Результаты», «Устойчивость», «Пределы» (рис. 2.2.16) и нажать кнопку «ОК».
Результаты каждого отчета будут выданы на отдельных листах рабочей книги (рис. 2.2.17; 2.2.18; 2.2.19).
В таблице «Отчет по результатам» приведена информация о значениях переменных, целевой функции, а также статусе ограничений (рис. 2.2.17).
Рис. 2.2.17. Отчёт по результатам (первая таблица)
В первой таблице указано оптимальное значение целевой функции. Результат: 52 000.
Вторая таблица позволяет найти значения переменных принятия решения (результат: ).
В третьей таблице отчета указаны значения левой части ограничений при данных значениях переменных, статус ограничений (связующее или не связующее), а также разность между правой и левой частью. Для связующих ограничений разность равна нулю, для не связующих – больше нуля
«Отчет по устойчивости» состоит из двух таблиц (рис. 2.2.18).
В первой таблице приведена информация о переменных.
1. Результат решения, то есть значения переменных.
2. Нормированная стоимость, или альтернативная цена, которая для небазисных переменных показывает, как изменится значение целевой функции, если соответствующую переменную ввести в базис со значением, равным единице. Для базисных переменных нормированная стоимость равна нулю. В данной задаче обе переменные являются базисными, поэтому их альтернативная цена равна нулю.
3. Коэффициенты целевой функции при соответствующих переменных.
4. Предельные приращения коэффициентов целевой функции, при которых текущее базисное решение не изменится. Так, для переменной границы устойчивости коэффициента целевой функции составляют , поскольку максимальное увеличение коэффициента возможно на 200, а уменьшение на 50. Другими словами, текущее оптимальное решение не изменится, пока цена за единицу первого вида продукции будет находиться в пределах от 250 до 500 грн.
Рис. 2.2.18. Отчёт по устойчивости (вторая таблица)
Вторая таблица содержит данные об ограничениях.
1. В столбце «Результ. значение» указано значение левой части ограничений.
2. В столбце «Теневая цена» находится решение двойственной задачи. Теневая цена показывает, на сколько изменится значение целевой функции, если правая часть ограничения увеличится на одну единицу. В приведенном примере третье ограничение не является связующим, то есть, третий вид сырья используется не полностью. Таким образом, можно закупать его меньше на соответствующую величину, то есть на 100 единиц. Это уменьшит затраты как на закупку сырья, так и на его хранение. Теневая цена первого ограничения, равная 400, свидетельствует о том, что каждая дополнительная единица третьего вида сырья увеличит прибыль на 400 грн. Можно также утверждать, что это максимальная цена, которую можно заплатить за 1 единицу сырья первого вида.
3. В столбцах «Допустимое увеличение (уменьшение)» находятся предельные приращения правых частей ограничений, при которых текущий опорный план не изменится. В примере для первого вида сырья границы устойчивости , так как допустимое уменьшение возможно на 25 ед., а увеличение на 20 Для второго вида сырья границы устойчивости составляют (100; 140), а для третьего – (200; ) (здесь 1Е+30 равносильна ). Это означает, что, до тех пор, пока количество сырья будет находиться в данных пределах, оптимальное решение задачи не изменится.
«Отчет по пределам»для рассматриваемой задачи имеет следующий вид (рис. 2.2.19):
Рис. 2.2.19. Отчёт по пределам (третья таблица)
Необходимо отметить, что для задач целочисленного программирования отчеты по устойчивости и пределам не применимы.
Необходимо отметить, что при решении задачи с использованием надстройки «Поиск решения» не важно, в какой форме записана задача линейного программирования и содержит ли система ограничений полный единичный базис. Решение осуществляется так, как было описано выше.
Для составления и анализа двойственной задачи рассмотрим вначале дополнительно основные понятия двойственности.
При составлении двойственных задач будем пользоваться определением. Если задача задана на max то ограничение вида «£» будем называть согласованным или правильным, а «³» – неправильным, несогласованным. Если задача задана на min, то ограничение « ³ » – правильное, а « £ » – неправильное.
Для написания двойственной задачи сформулируем соотношение между отдельными элементами прямой и двойственной задач:
1. Количество двойственных переменных равно количеству ограничений исходной задачи (каждому ограничению ставится в соответствие двойственная переменная).
2. Целевая функция двойственной задачи имеет вид F = b1y1+ b2y2+…+ bmym.
3. Если Z ® max, то F ® min; если Z ® min, то F ® max (направление цели F противоположно направлению цели Z).
4. Количество ограничений двойственной задачи равно количеству переменных исходной задачи. Каждой переменной исходной задачи ставится в соответствие ограничение двойственной задачи.
5. Левая часть j-го ограничения двойственной задачи равна , а правая сj. Если , то j-е ограничение в двойственной задаче правильное. Если , то j-е ограничение – неправильное, если имеет любой знак, то j-е ограничение является равенством.
6. Если i-е ограничение исходной задачи правильное, то , если i-е ограничение исходной задачи неправильное, то , если i-е ограничение исходной задачи « = », то может иметь любой знак.
7. Матрицы исходной и двойственной задач взаимно транспонированные.
Для задачи оптимального выпуска продукции прямая и двойственная записываются в виде:
Прямая задача. Двойственная задача.
Рассмотрим составление двойственной задачи к исходной в общем случае на примере. Написать двойственную задачу к заданной задаче.
Прямая задача Двойственная задача
Решение двойственной задачи можно получить, исследуя решение исходной на основании первой и второй теорем двойственности.
Первая теорема двойственности.Если одна из пары двойственных задач имеет оптимальное решение, то вторая также имеет оптимальное решение, причем
Если одна из пары двойственных задач не ограничена, то у второй несовместна система ограничений.
Если одна из пары двойственных задач несовместна, то вторая несовместна или неограниченная.
Оптимальные значения переменных двойственной задачи можно определять из индексной строки последней симплексной таблицы по следующему правилу.
Чтобы найти надо:
1) в первой строке первой симплексной таблицы выбрать столбец, в котором находится базисная переменная. Пусть это будет столбец, соответствующий вектору ;
2) в этом столбце взять число, которое находится в индексной строке последней симплексной таблицы, т.е. ;
3) к этому числу прибавить коэффициент целевой функции из этого столбца. Это будет , т.е. .
Аналогично по второй, третьей строке и т. д. первой симплексной таблицы и элементам индексной строки последней таблицы находятся , и т. д.
При нахождении решения двойственной ЗЛП надо пользоваться правилом:
при умножении целевой функции на -1 двойственные переменные меняют знак.
при дописывании балансовых и искусственных переменных значения двойственных переменных не изменяются.
при умножении i-го ограничения на -1 i-я двойственная переменная меняет знак.
Значения двойственных переменных можно выписать из значения теневых цен.
4. Напишем двойственную задачу в примере 2.2.1.
5. Находим значения двойственных переменных из табл. 2.2.5.
Их можно выписать из теневых цен или из индексной строки последней симплекс-таблицы.
Читайте также: