Рассмотрим линейное программирование в Excel на примере задачи, ранее решенной .
Задача. Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно. Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд. На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц. Необходимо определить количество единиц продуктов А и В, которые Николай доложен производить в следующем месяце для максимизации маржинальной прибыли.
Скачать заметку в формате , пример в формате
1. Воспользуемся математической моделью построенной . Вот эта модель:
Максимизировать: Z = 2500 * х 1 + 3500 *х 2
При условии, что: 3 * х 1 + 10 * х 2 ≤ 330
16 * х 1 + 4 * х 2 ≤ 400
6 * х 1 + 6 * х 2 ≤ 240
2. Создадим экранную форму и введем в нее исходные данные (рис. 1).
Рис. 1. Экранная форма для ввода данных задачи линейного программирования
Обратите внимание на формулу в ячейке С7. Это формула целевой функции. Аналогично, в ячейки С16:С18 введены формулы для расчета левой части ограничений.
3. Проверьте, если у вас установлена надстройка «Поиск решения» (рис. 2), пропустите этот пункт.
Рис. 2. Надстройка Поиск решения установлена; вкладка «Данные», группа «Анализ»
Если надстройки «Поиск решения» вы на ленте Excel не обнаружили, щелкните на кнопку Microsoft Office, а затем Параметры Excel (рис. 3).
Рис. 3. Параметры Excel
Выберите строку Надстройки, а затем в самом низу окна «Управление надстройками Microsoft Excel» выберите «Перейти» (рис. 4).
Рис. 4. Надстройки Excel
В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (рис. 5). (Если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее.)
Рис. 5. Активация надстройки «Поиск решения»
После загрузки надстройки для поиска решения в группе Анализ на вкладке Данные становится доступна команда Поиск решения (рис. 2).
4. Следующим этапом заполняем окно Excel «Поиск решения» (рис. 6)
Рис. 6. Заполнение окна «Поиск решения»
В поле «Установить целевую ячейку» выбираем ячейку со значением целевой функции – $C$7. Выбираем, максимизировать или минимизировать целевую функцию. В поле «Изменяя ячейки» выбираем ячейки со значениями искомых переменных $C$4:$D$4 (пока в них нули или пусто). В области «Ограничения» с помощью кнопки «Добавить» размещаем все ограничения нашей модели. Жмем «Выполнить». В появившемся окне «Результат поиска решения» выбираем все три типа отчета (рис. 7) и жмем Ok. Эти отчеты нужны для анализа полученного решения. Подробнее о данных, представленных в отчетах, можно почитать .
Рис. 7. Выбор типов отчета
На основном листе появились значения максимизированной целевой функции – 130 000 руб. и изменяемых параметров х 1 = 10 и х 2 = 30. Таким образом, для максимизации маржинального дохода Николаю в следующем месяце следует произвести 10 единиц продукта А и 30 единиц продукта В.
Если вместо окна «Результат поиска решения» появилось что-то иное, Excel`ю найти решение не удалось. Проверьте правильность заполнения окна «Поиск решения». И еще одна маленькая хитрость. Попробуйте уменьшить точность поиска решения. Для этого в окне «Поиск решения» щелкните на Параметры (рис. 8.) и увеличьте погрешность вычисления, например, до 0,001. Иногда из-за высокой точности Excel не успевает за 100 итераций найти решение. Подробнее о параметрах поиска решения можно почитать .
Рис. 8. Увеличение погрешности вычислений
Лабораторная работа "Использование средства Поиск решения"
Задание:
Решить в Excel все приведенные ниже задачи (каждую на отдельном листе) и сохранить решения в файле LAB4.xls на своем пользовательском диске.
Задача 1 1
Решение задачи линейного программирования с помощью EXCEL. 2
Задача 2 4
Задача планирования производства красок 4
Задача 3 5
Решение транспортной задачи с помощью средства Поиск решения 5
Задача 1
Задача распределения ресурсов.
Если финансы, оборудование, сырье и даже людей полагать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.
Например:
Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведена ниже.Составим математическую модель, для чего введем следущие обозначения:
x j - количество выпускаемой продукции j-го типа, j=1,4 ;
b i - количество располагаемого ресурса i-го вида, i=1,3 ;
a ij - норма расхода i-го ресурса для выпуска единицы продукции j-го типа;
c j - прибыль, получаемая от реализации единицы продукции j-го типа.
Теперь приступим к составлению модели.
Для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6 х 1 единиц сырья, где х 1 - количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
6х 1 +5х 2 +4х 3
В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющегося ресурса. Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:
F=60x 1 +70x 2 +120x 3 +130x 4 --> max
x 1 +x 2 +x 3 +x 4
6x 1 +5x 2 +4x 3 +3x 4
4x 1 +6x 2 +10x 3 +13x 4
x j >=0; j=1,4
Решение задачи линейного программирования с помощью EXCEL.
1
.
Сделать активной ячейку F6.
2. Мастер функций Математические СУММПРОИЗВ на жмите кнопку Далее. На экране диалоговое окно
3. Введите зависимости для левых частей ограничений.
Работа в диалоговом окне Поиск решения.
1
.
Сервис, Поиск решения...
2 . Курсор в поле Установить целевую ячейку и введите адрес F6.
3 . Введите направление целевой функции: Максимальному значению .
4 . Курсор в поле Изменяя ячейки и введите адреса B3:E3
5. Нажмите кнопку Добавить... и в ведите граничные условия на переменные
6. После ввода ограничений, нажмите кнопку Выполнить . В результате вычислений в ячейках В3:Е3, будут отражены найденные числовые значения х i , а в ячейке F6 – значение целевой функции.
Т.О, видно, что в оптимальном решении Прод1=В3=10, Прод2=С3=0, Прод3=D3=6, Прод4=Е3=0.
При этом максимальная прибыль будет составлять F6=1320 , количество использованных ресурсов равно трудовых=F9=16, сырья=F10=84, финансов=F11=100.
С помощью диалогового окна Результат поиска решения. Решение найдено можно получить отчеты трех типов: результаты, устойчивость, пределы.
Задача 2
Задача планирования производства красок
Для производства красок для наружных и внутренних работ используют два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно.
Суточный спрос на краску для внутренних работ никогда не превышает спроса на краску для наружных работ более чем на 1т.
Спрос на краску для внутренних работ не превышает 2т. в сутки.
Оптовые цены одной тонны красок равны: 3000 руб. для краски для наружных работ и 2000 руб. для краски для внутренних работ .
Какое количество краски каждого вида следует производить, чтобы доход от реализации был максимальным?
Расходы продуктов А и В на 1т. приведены в таблице:
исходный продукт |
расход исходных продуктов на тонну краски |
максимально возможный запас |
|
для внутренних работ |
для наружных работ |
||
х 1 - суточный объем производства краски для внутренних работ
х 2 - суточный объем производства краски для наружных работ
f -суммарная суточная прибыль от производства обоих видов красок (целевая функция)
f = 3000х 1 +2000х 2
Определить при каких допустимых значениях х 1 и х 2 значение f - максимальное
Ограничения:
Решение задачи в Excel
Переменные |
|||
Целевая функция: |
3000*А3+2000*В3 |
||
Ограничения |
|||
Выполните: Cервис, Поиск решения
Целевая ячейка С4
Установить: М аксимальному значению
Изменяемые ячейки: А3:В3
Ограничения:
После ввода данных нажмите кнопку Выполнить
Полученное решение:
Переменные |
|||
Целевая функция: |
|||
Ограничения: |
|||
Вывод: оптимальным является производство 3,3 т. краски для наружных работ и 1,3 т. краски для внутренних работ в сутки. Этот объем принесет прибыль 12,7 тыс. руб.
Задача 3
Решение транспортной задачи с помощью средства Поиск решения
Фирма имеет четыре фабрики: А, В, С, D и пять центров распределения ее товаров: №1, №2, №3, №4, №5.
Производственные возможности фабрик соответственно составляют:
А – 200, В – 150, С – 225, D – 175 единиц продукции ежедневно.
Потребности центров распределения соответственно составляют:
№1 – 100, №2 – 200, №3 – 50, №4 – 250, №5 – 150 единиц продукции ежедневно.
Хранение на фабрике единицы продукции, не поставленной в центр распределения, составляет $0,75 в день.
Штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день.
Стоимость перевозки единицы продукции с фабрик в пункты распределения представлена в таблице:
Спланировать перевозки так, чтобы минимизировать суммарные транспортные расходы.
Модель рассматриваемой задачи сбалансирована (суммарный объем произведенной продукции равен суммарному объему потребностей в ней), значит не нужно учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель следует ввести:
В случае перепроизводства – фиктивный пункт распределения, стоимость перевозок единицы продукции, в который полагается равной стоимости складирования, а объемы перевозок – объемам складирования излишков продукции на фабриках.
В случае дефицита – фиктивную фабрику, стоимость перевозок единицы продукции с которой полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок – объемам недопоставок продукции в пункты распределения.
x ij – объем перевозок с i-й фабрики в j-й центр распределения.
c ij – стоимость перевозки единицы продукции с i-й фабрики в j-й центр распределения.
а i – объем производства на i-й фабрике.
в j – спрос в j-м центре распределения.
Т
ребуется
минимизировать суммарные транспортные
расходы, т.е.
Ограничения:
x
ij
0 , i
, j
Механизм решения задачи в Excel с использованием средства Поиск решения
В ячейки А1:Е4 введите стоимости перевозок.
А6:Е9 – отведите под значения неизвестных (объемы перевозок).
В ячейки G6:G9 введите объемы производства на фабриках.
В А11:Е11 – потребность в продукции в пунктах распределения.
В ячейку F10 – введите целевую функцию
В А10:Е10 –введите формулы, определяющие объем продукции, ввозимой в центры распределения
В F6: F9 – формулы, вычисляющие объем продукции, вывозимой с фабрик.
СУММ(A6:E6) |
|||||||
СУММ(A7:E7) |
|||||||
СУММ(A8:E8) |
|||||||
СУММ(A9:E9) |
|||||||
СУММ(A6:A9) |
СУММ(B6:B9) |
СУММ(C6:C9) |
СУММ(D6:D9) |
СУММ(E6:E9) |
СУММПРОИЗВ(A1:E4;A6:E9) |
||
Сервис Поиск решения
В
окне диалога Поиск решения:
Установить
целевую ячейку $F$10
Равной
мин
имальному
значению
Изменяя
ячейки:
$А$6:$E$9
Ограничения:
$А$10:$E$10=$A$11:$E$11
$А$6:$E$9>=0
$F$6:$F$9=$G$6:$G$9
Щелкните на кнопке Параметры… и установите флажок Линейная модель
Нажмите кнопку Выполнить
Оптимальное решение транспортной задачи будет отражено в диапазоне А6:Е9
Решите транспортную задачу самостоятельно, используя выше описанный механизм.
Excel необходимо: ... Задачи линейного программирования. Графический метод решения задач линейного программированияРешениеMicrosoft Excel . Решение задач выпуклого программирования при помощи линейной аппроксимации. Приближённое решение задач математического программирования методом сепарабельного программирования . Экономические задачи , решаемые с помощью ... Инструкция по использованию microsoft Excel для решения задач лп 5 3 Одноиндексные задачи лп 6 > 3 Ввод исходных данных 6 > 3 Решение задачи 13Инструкция1. ЛАБОРАТОРНАЯ РАБОТА №1 “РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Excel ” 1.1. ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном... Некоторые понятия линейного программированияДокументМы приведем решение этой задачи с помощью программы Tora. рассмотрим реализацию задачи линейного программирования в... задачи с помощью Microsoft Excel . 1. Осуществляем ввод данных в таблицу Excel (рис. 1). Рис. 1. Заполнение листа для решения задачи ... |
Рассмотрим пример задачи линейного программирования.
Требуется определить, в каком количестве надо выпустить продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены на рис. 1.
Ресурс | Прод1 | Прод2 | Прод3 | Прод4 | Знак | Наличие |
Прибыль | ||||||
Трудовые | ||||||
Сырье | ||||||
Финансы |
Рисунок 1.
Математическая модель задачи имеет вид:
где x j – количество выпускаемой продукции j-го типа; F – функция цели; в левых частях выражений ограничений указаны величины потребного ресурса , а правые части показывают количество имеющегося ресурса .
Ввод условий задачи
Для решения задачи с помощью Excel следует создать форму для ввода исходных данных и ввести их. Форма ввода показана на рис. 2.
В ячейку F6 введено выражение целевой функции как суммы произведений значений прибыли от выпуска единицы продукции каждого типа на количество выпускаемой продукции соответствующего типа. Для наглядности на рис. 3 представлена форма ввода исходных данных в режиме вывода формул.
В ячейки F8:F10 введены левые части ограничений для ресурсов каждого вида.
Рисунок 2.
Рисунок 3.
Решение задачи линейного программирования
Для решения задач линейного программирования в Excel используется мощный инструмент, называемый Поиск решения . Обращение к Поиску решения осуществляется из меню Сервис , на экран выводится диалоговое окно Поиска решения (рис. 4).
Рисунок 4.
Ввод условий задачи для поиска ее решения состоит из следующих шагов:
1 Назначить целевую функцию, для чего установить курсор в поле Установить целевую ячейку окна Поиск решения и щелкнуть в ячейке F6 в форме ввода;
2 Включить переключатель значения целевой функции, т.е. указать ее Равной Максимальному значению ;
3 Ввести адреса изменяемых переменных (x j): для этого установить курсор в поле Изменяя ячейки окна Поиск решения, а затем выделить диапазон ячеек B3:E3 в форме ввода;
4 Нажать кнопку Добавить окна Поиск решения для ввода ограничений задачи линейного программирования; на экран выводится окно Добавление ограничения (рис. 5) :
Ввести граничные условия для переменных x j (x j ³0), для этого в поле Ссылка на ячейку указать ячейку В3, соответствующую х 1 , выбрать из списка нужный знак (³), в поле Ограничение указать ячейку формы ввода, в которой хранится соответствующее значение граничного условия, (ячейка В4), нажать кнопку Добавить ; повторить описанные действия для переменных х 2 , х 3 и х 4 ;
Ввести ограничения для каждого вида ресурса, для этого в поле Ссылка на ячейку окна Добавление ограничения указать ячейку F9 формы ввода, в которой содержится выражение левой части ограничения, наложенного на трудовые ресурсы, в полях Ограничение указать знак £ и адрес Н9 правой части ограничения, нажать кнопку Добавить ; аналогично ввести ограничения на остальные виды ресурсов;
После ввода последнего ограничения вместо Добавить нажать ОК и возвратиться в окно Поиск решения.
Рисунок 5.
Решение задачи линейного программирования начинается с установки параметров поиска:
В окне Поиск решения нажать кнопку Параметры , на экран выводится окно Параметры поиска решения (рис. 6);
Установить флажок Линейная модель, что обеспечивает применение симплекс-метода;
Указать предельное число итераций (по умолчанию – 100, что подходит для решения большинства задач);
Установить флажок , если необходимо просмотреть все этапы поиска оптимального решения;
Нажать ОК , возврат в окно Поиск решения .
Рисунок 6.
Для решения задачи нажать кнопку Выполнить в окне Поиск решения , на экране – окно Результаты поиска решения (рис. 7), в котором содержится сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если условия задачи несовместны, то выводится сообщение Поиск не может найти подходящего решения . Если целевая функция не ограничена, то появляется сообщение Значения целевой ячейки не сходятся .
Рисунок 7.
Для рассматриваемого примера решение найдено и результат оптимального решения задачи выводится в форме ввода: значение целевой функции, соответствующее максимальной прибыли и равное 1320, указывается в ячейке F6 формы ввода, оптимальный план выпуска продукции х 1 =10, х 2 =0, х 3 =6, х 4 =0 указывается в ячейках В3:С3 формы ввода (рис. 8).
Количество использованных для выпуска продукции ресурсов выводится в ячейки F9:F11: трудовых – 16, сырья – 84, финансов – 100.
Рисунок 8.
Если при установке параметров в окне Параметры поиска решения (рис. 6) был установлен флажок Показывать результаты итераций , то будут показаны последовательно все шаги поиска. На экран будет выводиться окно (рис. 9). При этом текущие значения переменных и функции цели будут показаны в форме ввода. Так, результаты первой итерации поиска решения исходной задачи представлены в форме ввода на рисунке 10 .
Рисунок 9.
Рисунок 10.
Чтобы продолжить поиск решения, следует нажимать кнопку Продолжить в окне Текущее состояние поиска решения .
Анализ оптимального решения
Прежде чем, перейти к анализу результатов решения, представим исходную задачу в форме
введя дополнительные переменные у i , представляющие собой величины неиспользованных ресурсов.
Составим для исходной задачи двойственную задачу и введем дополнительные двойственные переменные v i .
Анализ результатов поиска решения позволит увязать их с переменными исходной и двойственной задач.
С помощью окна Результаты поиска решения можно вызвать отчеты трех типов, позволяющие анализировать найденное оптимальное решение:
Результаты,
Устойчивость,
Пределы.
Для вызова отчета в поле Тип отчета выделить название нужного типа и нажать ОК .
1 Отчет по результатам (рис. 11) состоит из трех таблиц:
Таблица 1 содержит сведения о целевой функции; в столбце Исходно указывается значение целевой функции до начала вычислений;
Таблица 2 содержит значения искомых переменных x j , полученных в результате решения задачи (оптимальный план выпуска продукции);
Таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.
Для Ограничений в графе Формула приведены зависимости, которые были введены при задании ограничений в окне Поиск решения ; в графе Значение указаны величины использованного ресурса; в графе Разница показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние выводится сообщение связанное ; при неполном использовании ресурса в этой графе указывается не связан. Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо неиспользованного ресурса показана разность между значением переменной x j в найденном оптимальном решении и заданным для нее граничным условием (x j ³0).
Именно в графе Разница можно увидеть значения дополнительных переменных y i исходной задачи в формулировке (2). Здесь у 1 =у 3 =0, т.е. величины неиспользованных трудовых и финансовых ресурсов равны нулю. Эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у 2 =26, значит, имеются излишки сырья.
Рисунок 11.
2 Отчет по устойчивости (рис. 12)состоит из двух таблиц.
В таблице 1 приводятся следующие значения:
Результат решения задачи (оптимальный план выпуска);
- Нормир. стоимость , т.е. величины, показывающие, насколько изменится целевая функция при принудительном включении единицы продукции соответствующего типа в оптимальный план;
Коэффициенты целевой функции;
Предельные значения приращения коэффициентов целевой функции, при которых сохраняется оптимальный план выпуска.
В таблице 2 содержатся аналогичные данные для ограничений:
Величины использованных ресурсов;
- Теневая цена , показывающая, как изменится целевая функция при изменении величины соответствующего ресурса на единицу;
Допустимые значения приращений ресурсов, при которых сохраняется оптимальный план выпуска продукции.
Рисунок 12.
Отчет по устойчивости позволяет позволяет получить двойственные оценки.
Как известно, двойственные переменные z i показывают, как изменится целевая функция при изменении ресурса i-го типа на единицу. В отчете Excel двойственная оценка называется Теневой ценой .
В нашем примере сырье не используется полностью и его ресурс у 2 =26. Очевидно, что увеличение количества сырья, например, до 111 не повлечет за собой увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z 2 =0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.
В рассматриваемом примере трудовые ресурсы и финансы использовались полностью, поэтому их дополнительные переменные равны нулю (у 1 =у 3 =0). Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции, и следовательно, на величину целевой функции. Двойственные оценки ограничений на трудовые и финансовые ресурсы отличны от нуля, т.е. z 1 =20, z 3 =10.
Значения двойственных оценок находим в Отчете по устойчивости , в таблице 2, в графе Теневая цена .
При увеличении (уменьшении) трудовых ресурсов на единицу целевая функция увеличится (уменьшится) на 20 единиц и будет равна
F=1320+20×1=1340 (при увеличении).
Аналогично, при увеличении объема финансов на единицу целевая функция будет
F=1320+10×1=1330.
Здесь же, в графах Допустимое увеличение и Допустимое уменьшение таблицы 2, показаны допустимые пределы изменения количества ресурсов j-го вида. Например, для при изменении приращения величины трудовых ресурсов в пределах от –6 до 3,55, как показано в таблице, структура оптимального решения сохраняется, т.е наибольшую прибыль обеспечивает выпуск Прод1 и Прод3, но в других количествах.
Дополнительные двойственные переменные также отражены в Отчете по устойчивости в графе Нормир. стоимость таблицы 1.
Если основные переменные не вошли в оптимальное решение, т.е. равны нулю (в примере х 2 =х 4 =0), то соответствующие им дополнительные переменные имеют положительные значения (v 2 =10, v 4 =20). Если же основные переменные вошли в оптимальное решение (х 1 =10, х 3 =6), то их дополнительные двойственные переменные равны нулю (v 1 =0, v 3 =0).
Эти величины показывают, насколько уменьшится (поэтому знак минус в значениях переменных v 2 и v 4) целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции вида Прод3, то целевая функция уменьшится на 10 единиц и будет равна 1320 -10×1 =1310.
Обозначим через Dс j изменение коэффициентов целевой функции в исходной модели (1). Эти коэффициенты определяют прибыль, получаемую при реализации единицы продукции j-го вида.
В графах Допустимое увеличение и Допустимое Уменьшение таблицы 1 Отчета по устойчивости показаны пределы изменения Dс j , при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукцию вида Продj. Например, при изменении Dс 1 в пределах -12£ Dс 1 £ 40, как показано в отчете, по-прежнему будет выгодно выпускать продукцию вида Прод1. При этом значение целевой функции будет F=1320+x 1 ×Dс j =1320+10×Dс j .
3 Отчет по пределам приведен на рис. 13. В нем показывается, в каких пределах могут изменяться значения x j , вошедшие в оптимальное решение, при сохранении структуры оптимального решения. Кроме этого, для каждого типа продукции приводятся значения целевой функции, получаемые при подстановке в оптимальное решение значения нижнего предела выпуска изделий соответствующего типа при неизменных значениях выпуска остальных типов. Например, если при оптимальном решении х 1 =10, х 2 =0, х 3 =6, х 4 =0 положить х 1 =0 (нижний предел) при неизменных х 2 , х 3 и х 4 , то значение целевой функции будет равно 60×0+70×0+120×6+130×0=720.
Ввод условий задачи состоит из следующих основных шагов:
Создание формы для ввода условий задачи.
Ввод исходных данных.
Ввод зависимостей из математической модели.
Назначение целевой функции.
ввод ограничений и граничных условий.
Ход решения задачи:
Форма для ввода условий задачи:
Переменные |
||||||
Значение |
||||||
Коэффициент в целевой функции |
(формула) |
|||||
Ограничения |
||||||
Коэффициенты в ограничениях |
Правая часть ограничения |
|||||
Поочередно в представленную форму заносятся коэффициенты целевой функции, ограничений, их знаки, формулы описания целевой функции и ограничений, представленные в математической модели задачи.
Для описания формулы целевой функции и ограничений используется диалоговое окно Мастер функций; категория функций – математические; функция СУММПРОИЗВ. (в диалоговом окне в массиве 1 указывается интервал ячеек значения переменной В3:С3, в массиве 2 – коэффициенты при этих переменных. В функции это интервал ячеек В4:С4, в ограничениях – В8:C8, В9:C9 и т.д.)
Решение задачи осуществляется с использованием команд Сервис, Поиск решения…
В диалоговом окне Поиск решения заполняем строки, указывая адреса ячеек:
Целевая функция: Е4
Равная: max (min)
Изменяя ячейки: указывается месторасположения переменных (В3:C3)
Ограничения: с использованием клавиши Добавить записываются адреса ячеек с указанием условий ограничений (например: D8>= F8 и т.д.). Обязательным является ввод ограничения целочисленного решения.
Если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это осуществляется с помощью команд Изменить.., Удалить.
Для получения оптимального решения задачи линейного программирования в Поиске решения задействуется клавиша Параметры…:
Максимальное время: 100 сек
Предельное число итераций: 100
Относительная погрешность 0,000001
Допустимое отклонение: 5%
Устанавливаем флажок Линейная модель, что обеспечивает применение симплекс-метода.
В появившемся окне Поиск решения выполняем команду Выполнить.
Решение найдено, результат оптимального решения приведен в исходной таблице.
Решение задач линейного программирования в Excel
Используя данные прямой двойственной задачи, решите ее в системе Excel, с помощью следующих таблиц
Переменные
Ограничения
Вид ресурса |
Коэффициенты в ограничениях |
Левая часть ограничения (формула) |
Правая часть ограничения |
||
Требуется определить, в каком количестве надо выпустить продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены на рис. 1.
Ресурс | Прод1 | Прод2 | Прод3 | Прод4 | Знак | Наличие |
Прибыль | ||||||
Трудовые | ||||||
Сырье | ||||||
Финансы |
Рисунок 1.
Математическая модель задачи имеет вид:
где x j – количество выпускаемой продукции j-го типа; F – функция цели; в левых частях выражений ограничений указаны величины потребного ресурса , а правые части показывают количество имеющегося ресурса .
Ввод условий задачи
Для решения задачи с помощью Excel следует создать форму для ввода исходных данных и ввести их. Форма ввода показана на рис. 2.
В ячейку F6 введено выражение целевой функции как суммы произведений значений прибыли от выпуска единицы продукции каждого типа на количество выпускаемой продукции соответствующего типа. Для наглядности на рис. 3 представлена форма ввода исходных данных в режиме вывода формул.
В ячейки F8:F10 введены левые части ограничений для ресурсов каждого вида.
Рисунок 2.
Рисунок 3.
Решение задачи линейного программирования
Для решения задач линейного программирования в Excel используется мощный инструмент, называемый Поиск решения . Обращение к Поиску решения осуществляется из меню Сервис , на экран выводится диалоговое окно Поиска решения (рис. 4).
Рисунок 4.
Ввод условий задачи для поиска ее решения состоит из следующих шагов:
1 Назначить целевую функцию, для чего установить курсор в поле Установить целевую ячейку окна Поиск решения и щелкнуть в ячейке F6 в форме ввода;
2 Включить переключатель значения целевой функции, т.е. указать ее Равной Максимальному значению ;
3 Ввести адреса изменяемых переменных (x j): для этого установить курсор в поле Изменяя ячейки окна Поиск решения, а затем выделить диапазон ячеек B3:E3 в форме ввода;
4 Нажать кнопку Добавить окна Поиск решения для ввода ограничений задачи линейного программирования; на экран выводится окно Добавление ограничения (рис. 5) :
Ввести граничные условия для переменных x j (x j ³0), для этого в поле Ссылка на ячейку указать ячейку В3, соответствующую х 1 , выбрать из списка нужный знак (³), в поле Ограничение указать ячейку формы ввода, в которой хранится соответствующее значение граничного условия, (ячейка В4), нажать кнопку Добавить ; повторить описанные действия для переменных х 2 , х 3 и х 4 ;
Ввести ограничения для каждого вида ресурса, для этого в поле Ссылка на ячейку окна Добавление ограничения указать ячейку F9 формы ввода, в которой содержится выражение левой части ограничения, наложенного на трудовые ресурсы, в полях Ограничение указать знак £ и адрес Н9 правой части ограничения, нажать кнопку Добавить ; аналогично ввести ограничения на остальные виды ресурсов;
После ввода последнего ограничения вместо Добавить нажать ОК и возвратиться в окно Поиск решения.
Рисунок 5.
Решение задачи линейного программирования начинается с установки параметров поиска:
В окне Поиск решения нажать кнопку Параметры , на экран выводится окно Параметры поиска решения (рис. 6);
Установить флажок Линейная модель, что обеспечивает применение симплекс-метода;
Указать предельное число итераций (по умолчанию – 100, что подходит для решения большинства задач);
Установить флажок , если необходимо просмотреть все этапы поиска оптимального решения;
Нажать ОК , возврат в окно Поиск решения .
Рисунок 6.
Для решения задачи нажать кнопку Выполнить в окне Поиск решения , на экране – окно Результаты поиска решения (рис. 7), в котором содержится сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если условия задачи несовместны, то выводится сообщение Поиск не может найти подходящего решения . Если целевая функция не ограничена, то появляется сообщение Значения целевой ячейки не сходятся .
Рисунок 7.
Для рассматриваемого примера решение найдено и результат оптимального решения задачи выводится в форме ввода: значение целевой функции, соответствующее максимальной прибыли и равное 1320, указывается в ячейке F6 формы ввода, оптимальный план выпуска продукции х 1 =10, х 2 =0, х 3 =6, х 4 =0 указывается в ячейках В3:С3 формы ввода (рис. 8).
Количество использованных для выпуска продукции ресурсов выводится в ячейки F9:F11: трудовых – 16, сырья – 84, финансов – 100.
Рисунок 8.
Если при установке параметров в окне Параметры поиска решения (рис. 6) был установлен флажок Показывать результаты итераций , то будут показаны последовательно все шаги поиска. На экран будет выводиться окно (рис. 9). При этом текущие значения переменных и функции цели будут показаны в форме ввода. Так, результаты первой итерации поиска решения исходной задачи представлены в форме ввода на рисунке 10 .
Рисунок 9.
Рисунок 10.
Чтобы продолжить поиск решения, следует нажимать кнопку Продолжить в окне Текущее состояние поиска решения .
Анализ оптимального решения
Прежде чем, перейти к анализу результатов решения, представим исходную задачу в форме
введя дополнительные переменные у i , представляющие собой величины неиспользованных ресурсов.
Составим для исходной задачи двойственную задачу и введем дополнительные двойственные переменные v i .
Анализ результатов поиска решения позволит увязать их с переменными исходной и двойственной задач.
С помощью окна Результаты поиска решения можно вызвать отчеты трех типов, позволяющие анализировать найденное оптимальное решение:
Результаты,
Устойчивость,
Пределы.
Для вызова отчета в поле Тип отчета выделить название нужного типа и нажать ОК .
1 Отчет по результатам (рис. 11) состоит из трех таблиц:
Таблица 1 содержит сведения о целевой функции; в столбце Исходно указывается значение целевой функции до начала вычислений;
Таблица 2 содержит значения искомых переменных x j , полученных в результате решения задачи (оптимальный план выпуска продукции);
Таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.
Для Ограничений в графе Формула приведены зависимости, которые были введены при задании ограничений в окне Поиск решения ; в графе Значение указаны величины использованного ресурса; в графе Разница показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние выводится сообщение связанное ; при неполном использовании ресурса в этой графе указывается не связан. Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо неиспользованного ресурса показана разность между значением переменной x j в найденном оптимальном решении и заданным для нее граничным условием (x j ³0).
Именно в графе Разница можно увидеть значения дополнительных переменных y i исходной задачи в формулировке (2). Здесь у 1 =у 3 =0, т.е. величины неиспользованных трудовых и финансовых ресурсов равны нулю. Эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у 2 =26, значит, имеются излишки сырья.
Рисунок 11.
2 Отчет по устойчивости (рис. 12)состоит из двух таблиц.
В таблице 1 приводятся следующие значения:
Результат решения задачи (оптимальный план выпуска);
- Нормир. стоимость , т.е. величины, показывающие, насколько изменится целевая функция при принудительном включении единицы продукции соответствующего типа в оптимальный план;
Коэффициенты целевой функции;
Предельные значения приращения коэффициентов целевой функции, при которых сохраняется оптимальный план выпуска.
В таблице 2 содержатся аналогичные данные для ограничений:
Величины использованных ресурсов;
- Теневая цена , показывающая, как изменится целевая функция при изменении величины соответствующего ресурса на единицу;
Допустимые значения приращений ресурсов, при которых сохраняется оптимальный план выпуска продукции.
Рисунок 12.
Отчет по устойчивости позволяет позволяет получить двойственные оценки.
Как известно, двойственные переменные z i показывают, как изменится целевая функция при изменении ресурса i-го типа на единицу. В отчете Excel двойственная оценка называется Теневой ценой .
В нашем примере сырье не используется полностью и его ресурс у 2 =26. Очевидно, что увеличение количества сырья, например, до 111 не повлечет за собой увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z 2 =0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.
В рассматриваемом примере трудовые ресурсы и финансы использовались полностью, поэтому их дополнительные переменные равны нулю (у 1 =у 3 =0). Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции, и следовательно, на величину целевой функции. Двойственные оценки ограничений на трудовые и финансовые ресурсы отличны от нуля, т.е. z 1 =20, z 3 =10.
Значения двойственных оценок находим в Отчете по устойчивости , в таблице 2, в графе Теневая цена .
При увеличении (уменьшении) трудовых ресурсов на единицу целевая функция увеличится (уменьшится) на 20 единиц и будет равна
F=1320+20×1=1340 (при увеличении).
Аналогично, при увеличении объема финансов на единицу целевая функция будет
F=1320+10×1=1330.
Здесь же, в графах Допустимое увеличение и Допустимое уменьшение таблицы 2, показаны допустимые пределы изменения количества ресурсов j-го вида. Например, для при изменении приращения величины трудовых ресурсов в пределах от –6 до 3,55, как показано в таблице, структура оптимального решения сохраняется, т.е наибольшую прибыль обеспечивает выпуск Прод1 и Прод3, но в других количествах.
Дополнительные двойственные переменные также отражены в Отчете по устойчивости в графе Нормир. стоимость таблицы 1.
Если основные переменные не вошли в оптимальное решение, т.е. равны нулю (в примере х 2 =х 4 =0), то соответствующие им дополнительные переменные имеют положительные значения (v 2 =10, v 4 =20). Если же основные переменные вошли в оптимальное решение (х 1 =10, х 3 =6), то их дополнительные двойственные переменные равны нулю (v 1 =0, v 3 =0).
Эти величины показывают, насколько уменьшится (поэтому знак минус в значениях переменных v 2 и v 4) целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции вида Прод3, то целевая функция уменьшится на 10 единиц и будет равна 1320 -10×1 =1310.
Обозначим через Dс j изменение коэффициентов целевой функции в исходной модели (1). Эти коэффициенты определяют прибыль, получаемую при реализации единицы продукции j-го вида.
В графах Допустимое увеличение и Допустимое Уменьшение таблицы 1 Отчета по устойчивости показаны пределы изменения Dс j , при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукцию вида Продj. Например, при изменении Dс 1 в пределах -12£ Dс 1 £ 40, как показано в отчете, по-прежнему будет выгодно выпускать продукцию вида Прод1. При этом значение целевой функции будет F=1320+x 1 ×Dс j =1320+10×Dс j .
3 Отчет по пределам приведен на рис. 13. В нем показывается, в каких пределах могут изменяться значения x j , вошедшие в оптимальное решение, при сохранении структуры оптимального решения. Кроме этого, для каждого типа продукции приводятся значения целевой функции, получаемые при подстановке в оптимальное решение значения нижнего предела выпуска изделий соответствующего типа при неизменных значениях выпуска остальных типов. Например, если при оптимальном решении х 1 =10, х 2 =0, х 3 =6, х 4 =0 положить х 1 =0 (нижний предел) при неизменных х 2 , х 3 и х 4 , то значение целевой функции будет равно 60×0+70×0+120×6+130×0=720.