В 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.
Формальная постановка данной задачи имеет вид:
(1)
Ввод исходных данных
Создание экранной формы и ввод исходных данных
Экранная форма для решения в MS Excel представлена на рисунке 1. 
Рисунок 1.
В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4
(), C4
(), коэффициентам ЦФ соответствуют ячейки B6
(150), C6
(75), правым частям ограничений соответствуют ячейки
D
18
(1000), D
19
(360), D
20
(600) и т.д.
Ввод зависимостей из формальной постановки задачи в экранную форму
Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ , которая вычисляет сумму попарных произведений двух или более массивов.
Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций",
который можно вызвать из меню "Вставка"
или при нажатии кнопки "
Рисунок 2
Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:
· курсор в поле D 6;
· нажав кнопку "
· в окне "Функция"
выберитефункцию СУММПРОИЗВ
(рис. 3);
Рисунок 3
· в появившемся окне "СУММПРОИЗВ"
в строку "Массив 1"
введите выражение B
$4:
C
$4
, а в строку "Массив 2"
- выражение B
6:
C
6
(рис. 4);
Рисунок 4
Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B 3, C 3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B 13, C 13 - 1-е ограничение; B 14, С14 - 2-е ограничение и B 15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Таблица 1.
Формулы, описывающие ограничения модели (1)
|
Левая часть ограничения |
Формула Excel |
|
|
=СУММПРОИЗВ(B 4: C 4; B 13: C 13)) |
|
|
=СУММПРОИЗВ(B 4: C 4; B 14: C 14)) |
|
|
=СУММПРОИЗВ(B 4: C 4; B 15: C 15) |
Дальнейшие действия производятся в окне "Поиск решения" , которое вызывается из меню "Сервис" (рис.5):
· поставьте курсор в поле "Установить целевую ячейку" ;
· введите адрес целевой ячейки $ D $6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;
· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".
Рисунок 5
Ввод ограничений и граничных условий
Задание ячеек переменных
В окно "Поиск решения"
в поле "Изменяя ячейки"
впишите адреса $
B
$4:$С$4
. Необходимые адреса можно вносить в поле "Изменяя ячейки"
и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных
В нашем случае на значения переменных накладывается только граничное условие неотрицательности, то есть их нижняя граница должна быть равна нулю (см. рис. 1).
· Нажмите кнопку "Добавить" , после чего появится окно "Добавление ограничения" (рис.6).
· В поле "Ссылка на ячейку" введите адреса ячеек переменных $ B $4:$С$4 . Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.
· В поле знака откройте список предлагаемых знаков и выберите .
· В поле "Ограничение"
введите 0.
Рис.6 - Добавление условия неотрицательности переменных задачи (1)
Задание знаков ограничений
,
, =
· Нажмите кнопку "Добавить" в окне "Добавление ограничения" .
· В поле "Ссылка на ячейку" введите адрес ячейки левой части конкретного ограничения, например $ B $18 . Это можно сделать как с клавиатуры, так и путем выделения мышью нужной ячейки непосредственно в экранной форме.
· В соответствии с условием задачи (1) выбрать в поле знака необходимый знак, например, .
· В поле "Ограничение" введите адрес ячейки правой части рассматриваемого ограничения, например $ D $18 .
· Аналогично введите ограничения: $ B $19<=$ D $19 , $ B $20<=$ D $20 .
· Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK .
Окно "Поиск решения" после ввода всех необходимых данных задачи (1) представлено на рис. 5.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить"
или "Удалить"
(см. рис. 5).
Решение задачи
Установка параметров решения задачи
Задача запускается на решение в окне "Поиск решения".
Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры"
и заполнить некоторые поля окна "Параметры поиска решения"
(рис. 7).
Рис. 7 - Параметры поиска решения, подходящие для большинства задач ЛП
Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Подтвердите установленные параметры нажатием кнопки "
OK
"
.
Запуск задачи на решение
Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".
После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения"
с сообщением об успешном решении задачи, представленном на рис. 8.
Рис. 8 -. Сообщение об успешном решении задачи
Появление иного сообщения свидетельствует не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки , не позволяющие Excel найти оптимальное решение, которое в действительности существует.
Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.
В окне "Результаты поиска решения"
представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы"
. Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку "
OK
".
После этого в экранной форме появляется оптимальное решение задачи (рис. 9).
Рис.9 - Экранная форма задачи (1) после получения решения
Изучив алгоритмы "ручного" решения задач линейного программирования, полезно познакомиться и со способом упростить этот процесс. Ясно, что чем сложнее задача, чем больше в ней переменных и условий, тем утомительнее и дольше ее решать. В таких случаях удобно использовать специальные математические пакеты, или доступную многим программу MS Excel.
Решить задачи линейного программирования в Excel достаточно просто: 1) внести исходные данные задачи и ограничения, 2) запустить надстройку Поиск решения, 3) установить нужные параметры решения и запустить выполнение. Программа подберет оптимальное решение, выдаст отчеты для анализа решения задачи.
Подробнее все эти этапы с пояснениями и скриншотами разобраны ниже в примерах на разных задачах линейного программирования - изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий, перейдите в раздел: Контрольные работы по линейному программированию .
Задача 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.
Инструментом для решений задач оптимизации в MS Excel служит надстройка Поиск решения . Процедура поиска решения позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках.
Если данная надстройка установлена, то Поиск решения
запускается из меню Сервис
. Если такого пункта нет, следует выполнить команду Сервис
→ Надстройки...
и выставить флажок против надстройки
Поиск решения
(рис.2.1).
В окне Поиск решения имеются следующие поля:
Установить целевую ячейку – служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу .
Равной – служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или Подбор заданного числа). Чтобы установить число, введите его в поле.
Изменяя ячейки – служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку.
Предположить – используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.
Ограничения – служит для отображения списка граничных условий поставленной задачи.
Добавить - служит для отображения диалогового окна Добавить ограничение.
Изменить - Служит для отображения диалоговое окна Изменить ограничение.
Удалить - Служит для снятия указанного ограничения.
Выполнить – Служит для запуска поиска решения поставленной задачи.
Закрыть – Служит для выхода из окна диалога без запуска поиска решения поставленной задачи.
Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Восстановить – Служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.
Для решения задачи оптимизации выполните следующие действия.
1. В меню Сервис выберите команду Поиск решения.
2. В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.
3. Чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению.
Чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите, переключатель в положение
минимальному значению.
Чтобы установить значение в целевой ячейке равным некоторому числу путем изменения значений влияющих ячеек, установите переключатель в положение значению и введите в соответствующее поле требуемое число.
4. В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.
5. В поле Ограничения введите все ограничения, накладываемые на поиск решения.
6. Нажмите кнопку Выполнить.
Чтобы восстановить исходные данные, установите переключатель в положение
Этап С. Анализ найденного решения задачи оптимизации.
Для вывода итогового сообщения о результате решения используется диалоговое окно Результаты поиска решения.
 |
Диалоговое окно Результаты поиска решения содержит следующие поля:
Восстановить исходные значения – служит для восстановления исходных значений влияющих ячеек модели.
Отчеты – служит для указания типа отчета, размещаемого на отдельном листе книги.
Результаты. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.
Устойчивость. Используется для создания отчета, содержащего сведения о чувствительности решения к малым изменениям в формуле (поле Установить целевую ячейку, диалоговое окно Поиск решения) или в формулах ограничений.
Ограничения. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно, верхним пределом называется наибольшее значение.
Сохранить сценарий – служит для отображения диалогового окна Сохранение сценария, в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев MS Excel. В следующих разделах рассмотрим несколько конкретных моделей линейной оптимизации и примеры их решения с помощью MS Excel.
2.4 Задача о планировании производства
Постановка задачи. Предприятие должно производить изделия n видов: и 1 ,и 2 ,...и п , причем количество каждого выпускаемого изделия не должно превысить спрос β 1 , β 2 ,..., β n и одновременно не должно быть меньше запланированных величин b 1 ,b 2 ,...,b n соответственно. На изготовление изделий идет m видов сырья s l ,s 2 ,...,s m , запасы которых ограничены соответственно величинами γ 1 , γ 2 ,..., γ m . Известно, что на изготовление i -го изделия идет а ij единиц j -го сырья. Прибыль, получаемая от реализации изделий u 1 , ,и 2 ,...и п равна соответственно с 1 ,с 2 ,...,с п. Требуется так спланировать производство изделий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.
Математическая модель. Обозначим за х 1 ,х 2 ,...х n количества единиц изделий u 1 , ,и 2 ,...и п, выпускаемых предприятием. Прибыль, приносимая планом (целевая функция), будет равна:
z = z(x 1 ,x 2 ,...,x n) = с 1 x 1 + c 2 x 2 + ...+c n x n → max. Ограничения на выполнение плана запишется в виде: х i ≥β i для i = 1,2,...,n Чтобы не превысить спрос, надо ограничить выпуск изделий: x i ≤β i для i = 1,2,...n. И, наконец, ограничения на сырье запишутся в виде системы неравенств:
α 11 x 1 + α 12 x 2 +...+ α 1n x n ≤b 1
α 21 x 1 + α 22 x 2 +...+ α 2n x n ≤b 2
................................................
α m1 x 1 + α m2 x 2 +...+ α mn x n ≤b m
при условии, что х 1 ,х 2 ,...х п неотрицательны.
Пример 2.1:
Рассмотрим конкретный пример задачи о планировании производства и приведем последовательность действий, необходимых для ее решения с помощью MS Excel.
Условие задачи. Предприятие выпускает два вида железобетонных изделий: лестничные марши и балконные плиты. Для производства одного лестничного марша требуется израсходовать 3,5 куб.м. бетона и 1 упаковку арматуры, а для производства плиты - 1 куб.м. бетона и 2 упаковки арматуры. На каждую единицу продукции приходится 1 человеко-день трудозатрат. Прибыль от продажи 1 лестничного марша составляет 200 руб., а одной плиты - 100 руб. На предприятии работает 150 человек, причем известно, что в день предприятие производит не более 350 куб.м. бетона и завозится не более 240 упаковок арматуры. Требуется составить такой производственный план, чтобы прибыль от производимой продукции была максимальной.
Решение.
1. На листе рабочей книги MS Excel заполните таблицу параметров задачи (рис. 2.2).
2.
Создайте модель задачи и заполните ячейки для значений переменных (первоначально ячейки х { и х г
заполняются произвольными числовыми значениями, например, значением 10), целевой функции (ячейка содержит формулу) и ограничений (ячейки содержат формулы)
(рис. 2.2)
3. Выполните команду Сервис Поиск решения и установите необходимые значения в полях диалогового окна Поиск решения, добавляя ограничения в окне Добавление ограничений.
Замечание. В окне Добавление ограничений при необходимости есть возможность установить ограничения на целочисленность переменных модели.
4. Нажмите на кнопку Выполнить и установите параметры в окне Результаты поиска решения (переключатель Сохранить найденное решение или Восстановить исходные значения и Тип отчета).
Замечание: В случае ошибок в формулах, ограничениях или неверных параметрах модели в данном окне могут появиться следующие сообщения: «Значения целевой ячейки не сходятся», «Поиск не может найти решения» или «Условия линейной модели не выполняются». При этом переключатель следует установить в положение Восстановить исходные значения, проверить данные на листе и процедуру поиска решения проделать заново.
5. В результате в ячейках с переменными задачи появятся значения, соответствующие оптимальному плану (80 лестничных маршей и 70 плит перекрытия в день), а в ячейке для целевой функции - значение прибыли (23 000 руб.), соответствующее данному плану (рис. 2.3)
6. Вслучае если полученное решение является удовлетворительным, можно сохранить оптимальный план и ознакомиться с результатами поиска, которые выводятся на отдельный лист.
Упражнение:
Упр. 2.1. Предприятие выпускает телевизоры, стереосистемы и акустические системы, используя общий склад комплектующих. Запасы шасси на складе составляют 450 шт., кинескопов – 250 шт., динамиков – 800 шт., блоков питания – 450 шт., плат – 600 шт. На каждое изделие расходуется количество комплектующих, указанное в таблице:
Прибыль от производства одного телевизора составляет 90 у.е, одной стереосистемы – 50 и аудиосистемы – 45. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.
Нижегородский Государственный Технический Университет
Павловский филиал
Курсовая работа
по информатике на тему:
“Технология решения задач линейного программирования с помощью Поиска решений приложения Excel” .
Выполнила : Бородулина Д.А.
Группа 05-АМ.
Проверила : Ловыгина М.Б.
Павлово 2006 г.
Введение……………………………………………………………………………стр. 3
Решение задач с помощью надстройки Поиск решения
Вычисления и результаты решения задачи………………………………..стр. 10
Просмотр промежуточных результатов поиска решения…………...стр.11
Возникающие проблемы и сообщения процедуры поиска решения…...стр.12
Итоговые сообщения процедуры поиска решения……………………....стр.13
Примеры выполнения задач
Вывод……………………………………………………………………………....стр.24
Список литературы…………………………………………………………....стр.25
Введение
Линейная оптимизация – это раздел математического программирования, посвящённый нахождению экстремума линейных функций нескольких переменных при дополнительных линейных ограничениях, которые налагаются на переменные. Методы, с помощью которых решаются задачи, подразделяются на универсальные (например, симплексный метод) и специальные. С помощью универсальных методов решаются любые задачи линейного программирования. Особенностью задач линейного программирования является то, что экстремум целевой функции достигается на границе области допустимых решений.
Использование электронных таблиц широко распространено для решения многочисленных и разнообразных задач, связанных с учётом и контролем результатов управленческой деятельности: торгово-закупочных операций, производственных планов, бухучёта и т. п. Вместе с тем форма электронной таблицы оказывается очень удобной при решении многих аналитических задач управления деятельностью, и в частности задач исследования операций и поиска оптимальных решений.
В экономике оптимизационные задачи возникают в связи с многочисленностью возможных вариантов функционирования конкретного экономического объекта, когда возникает ситуация выбора варианта, наилучшего по некоторому правилу, критерию, характеризуемому соответствующей целевой функцией (например, иметь минимум затрат, максимум продукции).
Такие задачи в Excel решают с помощью Поиска решения .
Процедура Поиск решения представляет собой мощный инструмент для выполнения сложных вычислений. Она позволяет находить значения переменных, удовлетворяющих указанным критериям оптимальности, при условии выполнения заданных ограничений.
Решение задач с помощью надстройки Поиск решения
1. Установка программы Поиск решения
В меню Сервис выберите команду Надстройки.
В диалоговом окне Надстройки установите флажок Поиск решения. Если диалоговое окно Надстройки не содержит команды Поиск решения , нажмите кнопку Обзор и укажите диск и папку, в которой содержится файл надстройки Solver. xla (как правило, это папка Library\ Solver folder) или запустите программу Setup , если найти файл не удаётся.
Надстройка, указанная в диалоговом окне Надстройки , остаётся активной до тех пор, пока она не будет удалена.
2. Диалоговое окно Поиск решения
Окно Поиск решения (рис. 1) вызывается командой меню Сервис>Поиск решения.
Поле Установить целевую ячейку служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.
Рис.1.Диалоговое окно Поиск решения.
Кнопка Равной служит для выбора варианта с заданным значением целевой ячейки. Чтобы установить заданное число, введите его в поле.
Поле Изменяя ячейки служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку.
В поле Изменяя ячейки вводятся имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
Поле Предположить используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.
Поля Ограничения служат для отображения списка граничных условий, налагаемые на переменные задачи. Допускаются ограничения в виде равенств, неравенств, а также – требование целочисленности переменных. Ограничения добавляются по одному с помощью кнопки Добавить.
Команда Изменить Изменение ограничения.
Команда Удалить служит для снятия указанного курсором ограничения.
Команда Выполнить служит для запуска поиска решения поставленной задачи.
Команда Закрыть служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить.
Кнопка Параметры служит для отображения диалогового окна Параметры поиска решения , в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Кнопка Восстановить служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.
3.Ввод и редактирование ограничений
Диалоговые окна изменения и добавления ограничений одинаковы, рис.2.
Выберите из раскрывающегося списка условный оператор, который необходимо разместить между ссылкой и её ограничением. Это знаки операторов: не более, не менее, равно и т. д.
В поле Ограничения введите число, формулу или имя ячейки или диапазона содержащих или вычисляющих ограничивающие значения.
Чтобы приступить к набору нового условия, нажмите кнопку Добавить.
Чтобы вернуться в диалоговое окно Поиск решения, нажмите кнопку ОК.
Условные операторы целого и двоичного типа можно применять только при наложении ограничений на изменяемые ячейки.
Рис.2.Диалоговое окно Изменение ограничения.
4. Настройка параметров алгоритма и программы
Настройка параметров алгоритма и программы производится в диалоговом окне Параметры поиска решения , рис. 3.
В окне устанавливаются ограничения на время решения задач, выбираются алгоритмы, задаётся точность решения, предоставляется возможность для сохранения вариантов модели и их последующей загрузки. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач.
Рис. 3. Диалоговое окно Параметры поиска решения.
Поле Максимальное время служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства лабораторных работ.
Поле Предельное число итераций служит для управления временем решения задачи, путём ограничения числа промежуточных вычислений. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.
При достижении отведённого временного интервала или при выполнении отведённого числа итераций, на экране появляется диалоговое окно
Поле Относительная погрешность служит для задания точности (допустимой погрешности), с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до1. Низкая точность соответствует введённому числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию, например, 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошёлся процесс оптимизации. Чем меньше введённое число, тем выше точность результатов.
Поле Допустимое отклонение служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. При указании большого допуска поиск решения заканчивается быстрее.
Поле Сходимость результатов поиска решения применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость , поиск прекращается. Условием сходимости служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков, например, 0,0001 – это меньшее относительное изменение, чем 0,01. Чем меньше его значение, тем выше точность результатов. Лучшая сходимость требует больше времени на поиск оптимального решения.
Флажок Линейная модель служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.
Флажок Неотрицательные значения позволяет установить нулевую нижнею границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение .
Флажок служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.
Флажок служит для приостановки поиска решения для просмотра результатов отдельных итераций.
Кнопки Оценки служат для указания метода экстраполяции (линейная или квадратичная), используемого для получения исходных оценок значений переменных в каждом одномерном поиске.
Линейная служит для использования линейной экстраполяции вдоль касательного вектора.
Квадратичная служит для использования квадратичной экстраполяции, которая даёт лучшие результаты при решении нелинейных задач.
Кнопки Разности (производные) служат для указания метода численного дифференцирования (прямые или центральные производные), который используется для вычисления частных производных целевых и ограничивающихся функций.
Прямые используется для гладких непрерывных функций.
Центральные используется для функций, имеющих разрывную производную. Не смотря на то, что данный способ требует больше вычислений, он может помочь при получении итогового сообщения о том, что процедура поиска решения не может улучшить текущий набор влияющих ячеек.
Кнопки Метод поиска служат для выбора алгоритма оптимизации (метод Ньютона или сопряжённых градиентов).
Кнопка Ньютона служит для реализации квазиньютоновского метода, в котором запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряжённых градиентов. Здесь вычисляются частные производные второго порядка.
Кнопка Сопряжённых градиентов служит для реализации метода сопряжённых градиентов, в котором запрашивается меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях.
Для решения линейных задач используются алгоритмы симплексного метода. Для решения целочисленных задач используется метод ветвей и границ.
Команда Сохранить модель служит для отображения на экране диалогового окна Сохранить модель, в котором можно задать ссылку на область ячеек, предназначенную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации. Первая модель сохраняется автоматически.
Команда Загрузить модель служит для отображения на экране диалогового окна Загрузить модель, в котором можно задать ссылку на область ячеек, содержащих загружаемую модель.
1. Сохранение модели оптимизации
Рис. 4. Диалоговое окно Сохранить модель.
Значения элементов управления диалоговых окон Поиск решения и Параметры поиска решения записываются на лист. Чтобы использовать на листе несколько моделей оптимизации, нужно сохранить их в разных диапазонах (столбцах).
Предлагаемый диапазон содержит ячейку для каждого ограничения, а также ещё три ячейки. Можно также ввести ссылку только на верхнюю ячейку столбца, в котором следует сохранить модель.
Диалоговое окно Загрузить модель используется для задания ссылки на область загружаемой модели оптимизации. Ссылка должна адресовать область модели целиком, недостаточно указать только первую ячейку.
Перед тем как использовать данную процедуру, необходимо сохранить хотя бы одну модель.
1 В меню Сервис выберите команду Поиск решения.
2. Нажмите кнопку Параметры.
3. Нажмите кнопку Загрузить модель. Появляется окно, аналогичное окну Сохранить модель.
Диалоговое окно Загрузить модель используется для задания ссылки на область загружаемой (ранее сохранённой) модели оптимизации. Ссылка должна адресовать область модели целиком не достаточно указать только первую ячейку.
Вычисления и результаты решения задачи
Для запуска оптимизатора нажмите кнопку Выполнить в окне Поиск решения.
Программа начинает работать, в строке сообщений (слева внизу листа) появляется сообщение Постановка задачи… Ваша таблица с моделью и параметрами алгоритма автоматически приводится к стандартам постановки задач математического программирования. Это преимущество Excel. В других пакетах Вам пришлось бы оторваться от экономической сути задачи и заниматься формальной математической постановкой задачи. После этапа постановки решается задача.
Чтобы прервать поиск решения, нажмите клавишу ESC. Microsoft Excel пересчитает лист с учётом найденных значений влияющих ячеек.
По окончании счёта появляется диалоговое окно Результаты поиска решения, рис. 5.
Рис. 5. Диалоговое окно Результаты поиска решения.
Поле Тип отчёта служит для указания типа отчёта, размещаемого на отдельном листе книги.
Отчёт Результаты используется для создания отчёта, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.
Отчёт Устойчивость используется для создания отчёта, содержащего сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчёт не создаётся для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчёт содержит данные для градиентов и множителей Лагранжа. В отчёт по нелинейным моделям включаются ограниченные затраты, фиктивные цены, а также диапазоны ограничений.
Отчёт Пределы используется для создания отчёта, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчёт не создаётся для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно верхним пределом называется наибольшее значение.
К сожалению, эти отчёты очень неудобны. Они перегружены плохо читаемыми абсолютными ссылками со знаками доллара. Желает лучшего и перевод с английского на русский.
Кнопка Сохранить сценарий служит для отображения диалогового окна Сохранение сценария , в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев Microsoft Excel. В поле Название сценария введите имя сценария. Чтобы создать сценарий, не сохраняя найденное решение и не отображая результатов на листе, сохраните сценарий в диалоговом окне Результаты поиска решения , а затем выберите Восстановить исходные значения.
Просмотр промежуточных результатов поиска решения
Режим пошагового решения задач используется при отладке моделей.
В диалоговом окне Поиск решения нажмите кнопку Параметры.
Чтобы получить возможность просмотра текущих значений влияющих ячеек каждой итерации, установите флажок Показывать результаты итераций, нажмите кнопку ОК, а затем кнопку Выполнить.
На экране появится диалоговое окно , рис. 6, а влияющие ячейки листа изменят свои значения.
Чтобы остановить поиск решения и вывести на экран диалоговое окно Результаты поиска решения, нажмите кнопку Стоп.
Рис.6. Диалоговое окно Текущее состояние поиска решения.
Чтобы выполнить следующую итерацию и просмотреть её результаты, нажмите кнопку Продолжить.
Возникающие проблемы и сообщения процедуры поиска решения
Оптимальное решение не найдено
Поиск решения может остановиться до достижения оптимального решения по следующим причинам.
Пользователь прервал процесс поиска.
Команда Показывать результаты итераций в диалоговом окне Параметры поиска решения выбрана перед Выполнить.
Пользователь нажал кнопку Стоп в режиме пошагового выполнения итераций, по истечении времени, отведённого на работу процедуры, или после выполнения заданного числа итераций.
Установлен флажок Линейная модель в диалоговом окне Параметры поиска решения, в то время как решаемая задача не линейна.
Значение, заданное в поле Установить целевую диалогового окна Поиск решения , неограниченно увеличивается или уменьшается. Необходимо уменьшить значения полей Максимальное время или Итерации в диалоговом окне Параметры поиска решения.
В случае задач, значения в которых ограничены множеством целых чисел, необходимо уменьшить значение в поле Допустимое отклонение диалогового окна Параметры поиска решения , что позволит найти лучшее решение.
В случае нелинейных задач необходимо уменьшить значение в поле Сходимость диалогового окна Параметры поиска решения , что позволит продолжать поиск решения, когда значение в целевой ячейке изменяется медленно.
Если значения влияющих ячеек или значения влияющей и целевой ячеек различаются на несколько порядков, необходимо установить флажок Автоматическое масштабирование в диалоговом окне Параметры поиска решения. Внесите нужные изменения и запустите процедуру поиска решения снова.
Если найденное решение нелинейной задачи существенно отличается от ожидаемого результата, запустите процедуру поиска решения с другими начальными значениями влияющих ячеек. Если задать такие значения влияющих ячеек, которые близко расположены от экстремальной точки целевой функции, можно значительно сократить время поиска решения.
Итоговые сообщения процедуры поиска решения
1. Если поиск решения успешно завершён, в диалоговом окне Результаты поиска решения
Решение найдено. Все ограничения и условия оптимальности выполнены.
Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.
Поиск свёлся к текущему решению. Все ограничения выполнены.
Относительное изменение значения в целевой ячейке за последние пять итераций стало меньше установленного значения параметра Сходимость в диалоговом окне Параметры поиска решения . Чтобы найти более точное решение, установите меньшее значение параметра Сходимость , но это займёт больше времени.
2. Если поиск не может найти оптимальное решение, в диалоговом окне Результаты поиска решения выводится одно из следующих сообщений.
Поиск не может улучшить текущее решение. Все ограничения выполнены.
В процессе поиска решения нельзя найти такой набор значений влияющих ячеек, который был бы лучше текущего решения. Приблизительное решение найдено, но либо дальнейшее уточнение невозможно, либо заданная погрешность слишком высока. Измените погрешность на меньшее число и запустите процедуру поиска решения снова.
3. Поиск остановлен (истекло заданное на поиск время).
Время, отпущенное на решение задачи, исчерпано, но достичь удовлетворительного решения не удалось. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить найденное решение или Сохранить сценарий .
4. Поиск остановлен (достигнуто максимальное число итераций).
Произведено разрешённое число итераций, но достичь удовлетворительного решения не удалось. Увеличение числа итераций может помочь, однако следует рассмотреть результаты, чтобы понять причины остановки. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления установите переключатель Сохранить найденное решение или Сохранить сценарий .
5. Значения целевой ячейки не сходятся.
Значение целевой ячейки неограниченно увеличивается (или уменьшается), даже если все ограничения соблюдены.Возможно, следует в задаче снять одно ограничение или сразу несколько, или наложить дополнительные ограничения. Изучите процесс расхождения решения, проверьте ограничения и запустите задачу снова. Например, в задаче об оптимальных портфелях банков, если не наложить ограничение на портфель привлечения ресурсов, то банк как аферист будет занимать деньги до бесконечности.
6. Поиск не может найти подходящее решение.
В процессе поиска решения нельзя сделать итерацию, которая удовлетворяла бы всем ограничениям при заданной точности. Вероятно, ограничения противоречивы. Исследуйте лист на предмет возможных ошибок в формулах ограничений или в выборе ограничений.
7. Поиск остановлен по требованию пользователя.
Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.
8. Условия для линейной модели не удовлетворяются.
Установлен флажок Линейная модель , однако итоговый пересчёт порождает такие значения, которые не согласуются с линейной моделью. Это означает, что решение недействительно для данных формул листа. Чтобы проверить линейность задачи, установите флажок Автоматическое масштабирование и повторно запустите задачу. Если это сообщение опять появится на экране, снимите флажок Линейная модель и снова запустите задачу.
9. При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.
При пересчёте значений ячеек обнаружена ошибка в одной формуле или в нескольких сразу. Найдите целевую ячейку или ячейку ограничения, порождающие ошибку, и измените их формулы так, чтобы они возвращали подходящее числовое значение.
Набрано неверное имя или формула в окне Добавить ограничение или окне Изменить ограничение или в поле Ограничения были заданы целое или двоичное ограничение. Чтобы ограничить значения ячейки множеством целых чисел, выберите оператор целого ограничения в списке условных операторов. Чтобы установить двоичное ограничение, выберите оператор для двоичного ограничения.
10. Мало памяти для решения задачи.
Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения, и попытайтесь снова выполнить процедуру поиска решения.
Примеры выполнения задач
ПРИМЕР № 1
Для изготовления четырёх видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице.
Какое количество продукции каждого вида должно изготовляться, чтобы доход от реализации был максимальным?
1. Формулировка математической модели задачи :
· переменные для решения задачи: x 1 – суточный объём изготовления продукции А, x 2 – суточный объём изготовления продукции Б, x 3 – суточный объём изготовления продукции В, x 4 – суточный объём изготовления продукции Г;
· определение функции цели (критерия оптимизации). Суммарная суточная прибыль от изготовления всех видов продукции равна:
F=12* x 1 +7* x 2 +18* x 3 +10* x 4,
поэтому цель состоит в том, чтобы среди всех допустимых значений x 1, x 2, x 3, x 4 найти такие, которые максимизируют суммарную прибыль от изготовления продуктов F:
· ограничения на переменные:
1. объём производства продукции не может быть отрицательным, т. е.
2. расход исходного продукта для изготовления всех видов продукции не может превосходить максимально возможного запаса данного исходного продукта, т. е.
Таким образом, получаем следующую математическую модель задачи:
· Найти максимум следующей функции:
F=12* x 1 +7* x 2 +18* x 3 +10* x 4 max;
· При ограничениях вида:
1* x 1 +2* x 2 +1* x 3 +0* x 4 ≤ 18,
1* x 1 +1* x 2 +2* x 3 +1* x 4 ≤ 30,
1* x 1 +3* x 2 +3* x 3 +2* x 4 ≤ 40,
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0;
2. Подготовка листа рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7. Переменные задачи x 1, x 2, x 3, x 4 находятся соответственно в C3, С4, С5, С6 . Целевая функция находится в ячейке С8 и содержит формулу:
12*C3+7*C4+18*C5+10*C6
Ограничения на задачу учтены в ячейках С10:С12.
3. Работа с надстройкой Поиск решения – воспользовавшись командой Сервис | Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рис. 8). Результат работы по поиску решения помещён на рис. 9 – 14.
Рис. 7. Рабочий лист MS Excel для решения задачи .
Рис. 8. Установка необходимых параметров задачи в окне Поиск решения .
Рис.9. Результаты расчёта надстройки Поиск решения.
Рис. 10. Отчёт по результатам поиска решения.
Рис. 11. Отчёт по устойчивости поиска решения.
Рис. 12. Отчёт по пределам поиска решения.
ВЫВОД : из решения видно, что оптимальный план выпуска предусматривает изготовление продукции видов "А" и "Г". А продукцию видов "Б" и "В" производить не стоит. Полученная Вами прибыль составит 326 усл. ед.
ПРИМЕР № 2
Задача распределения ресурсов
Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется два исходных продукта A и B. Расходы продуктов A и B на 1 т. соответствующих красок и запасы этих продуктов на складе приведены в таблице:
Продажная цена за 1 тонну краски для внутренних работ составляет 2 000 рублей, краска для наружных работ продается по 1 000 рублей за 1 тонну. Требуется определить какое количество краски каждого вида следует производить предприятию, чтобы получить максимальный доход.
Рассмотрим поэтапное решение этой задачи графическим способом с использованием процедуры « Поиск решения » Excel.
I. Составление математической модели задачи.
1) Переменные задачи.
Обозначим: x 1 - количество производимой краски для
внутренних работ;
x 2 - соответствующее количество краски
для наружных работ.
2) Ограничения, которым должны удовлетворять переменные задачи:
по расходу продукта A: x 1 + 2x 2 3;
по расходу продукта B: 3x 1 + x 2 3;
В левых частях последних двух неравенств определены расходы продуктов A и B, а в правых частях неравенств записаны запасы этих продуктов.
3) Целевая функция задачи.
Обозначим Z доход от продажи краски (в тысячах рублей), тогда целевая функция задачи записывается так:
Z = 2x 1 + x 2 ,
таким образом, задача состоит в том, чтобы найти max Z=2x 1 +x 2 , при ограничениях:
x 1 + 2x 2 3 (A)
3x 1 + x 2 3 (B)
x 1 , x 2 0 .
Так как переменные задачи x 1 и x 2 входят в целевую функцию и ограничения задачи линейно , то соответствующая задача оптимизации называется задачей линейного программирования (ЛП)
В рассматриваемом примере содержатся только две переменные x 1 и x 2 , поэтому задачу можно решить графически.
1) На плоскости x 1 , x 2 строим область допустимых значений переменных, определяемую ограничениями задачи:
x 1 + 2x 2 3 (A)
3x 1 + 1x 2 3 (B)
x 1 , x 2 0 .
Последнее ограничение определяет первый квадрант плоскости. Чтобы построить множество точек удовлетворяющих неравенству (А) нанесем на плоскость график прямой, определяющий границу этого множества: x 1 +2x 2 =3 (A).
Линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:
Z = 2x 1 + x 2 = К,
где К - задаваемая постоянная.
При К = 1 уравнение линии уровня будет:
2x 1 + x 2 = 1
или (в отрезках) :
При К = 2, аналогично:
2x 1 + x 2 = 2 , или .
Нанеся линии уровня на область допустимых решений (рис.13), получим, что при увеличении значения Z соответствующая линия уровня перемещается параллельно предыдущей вправо и вверх. Таким образом, точкой из многоугольника ABCD в которой целевая функция Z имеет максимальное значение будет вершина С. Эта точка и определяет решение задачи.
| |
Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.
Изучение литературы показало, что:
1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
