часто при дополнительных условияхнеравенствах- ~xlx2
Работа добавлена на сайт samzan.net:
СИСТЕМЫ УПРАВЛЕНИЯ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
ЗАДАЧИ ОПТИМИЗАЦИИ
Задачи оптимизации называют экстремальными задачами. Их решение сопряжено с большим количеством вычислений.
Постановка задачи оптимизации
В задачах оптимизации требуется найти значения параметров или функций, реализующих максимум или минимум некоторой зависящей от них величины, например:
z=f(xl,x2,...,xn), (3.1)
часто при дополнительных условиях-неравенствах:
Ψ(xl,x2,...,xn) ≤ 0 (i=1, 2, …, m) (3.2)
В задачах связанных с ресторанным бизнесом желательно найти максимум меры выполнения или минимум стоимости. Другим приложением задач оптимизации является получение приближенных решений выбором неизвестных значений параметров или функций так, чтобы они давали минимум ошибки.
В простейшем случае одной независимой переменной Х локальные максимум и минимум функции определяются следующим образом. Действительная функция f(x), определенная при х= а, имеет в точке а (локальный) минимум или (локальный) максимум f (а), если существует такое положительное число δ, что при всех Δx = x - a, для которых выполняются неравенства 0< 𝗅Δх𝗅< δ и существует значение f (a + Δx), соответственно:
Максимум и минимум функции - это экстремум функции. Определение локальный подчеркивает тот факт, что понятие экстремума связано лишь с достаточно малой окрестностью точки а. При решении оптимизационных задач важно нахождение не локальных экстремумов, а глобального максимума или глобального минимума (наибольшего или наименьшего значений) функции на промежутке X. Для поиска экстремумов существуют различные методы. Часто случается, что при поиске максимумов и минимумов функций многих переменных получают сложную систему уравнений, в этих случаях экстремумы находятся численными методами, то есть при помощи последовательного применения метода проб. При этом применение информационных технологий является практически единственным способом решения задачи.
Линейное программирование
В случае, когда оптимизируемая целевая функция (3.1) и ограничения (3.2) линейны, задача оптимизации решается методами линейного программирования и обычно называется задачей линейного программирования. Задача линейного программирования заключается в нахождении n переменных xl, x2 х1, минимизирующих данную линейную функцию (целевую функцию):
(3.4)
(или максимизирующую — Z) при линейных ограничениях-равенствах:
(3.5)
и линейных ограничениях-неравенствах:
(3.6)
Задачу линейного программирования (3.4-3.6) сводят путем
введения вспомогательных переменных к стандартной форме
(основной задаче линейного программирования). При этом требуется минимизировать целевую функцию:
(3.7)
при т < п линейных ограничениях-равенствах
(3.8)
и n линейных ограничениях-неравенствах
(3.9)
Допустимым решением (планом) задачи линейного программирования является упорядоченное множество чисел (x1 ,x2 , ...,xn), удовлетворяющих ограничениям (3.8) и (3.9). Это точка в n-мерном пространстве. Допустимое решение, минимизирующее целевую функцию (3.7), называется оптимальным решением (оптимальным планом).
Чаще всего оптимальное решение, если оно существует, является и единственным. Однако возможны случаи, когда оптимальных решений бесчисленное множество.
Процесс решения задачи линейного программирования обычно состоит из ряда этапов:
1-й этап: осмысление задачи, выделение наиболее важных
качеств, свойств, величин, параметров. Это можно делать, составляя схемы, таблицы, графики и т.п.;
2-й этап: введение обозначений (неизвестных). Желательно
ограничиваться как можно меньшим количеством неизвестных,
выражая по возможности одни величины через другие;
3-й этап: создание целевой функции. Обычно в качестве
цели могут выступать максимальная стоимость всего объема
продукции, максимальная прибыль, минимальные затраты и т. п.
Целевая функция записывается в виде (3.4) или (3.7).
4-й этап: составление системы ограничений, которым
должны удовлетворять введенные величины (3.5), (3.6) или (3.8), (3.9).
5-й этап: решение задачи на компьютере.
Инструментом для поиска решений задач оптимизации в
Excel служит процедура Поиск решения (Кнопка “Office”>Параметры Ехсеl> Надстройки>Поиск решения>ОК(Процедура «Поиск решения» появится во вкладке данные)). При этом открывается диалоговое окно Поиск решения.
Оно содержит следующие рабочие поля:
Установить целевую ячейку — служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта
ячейка должна содержать формулу;
Равной — служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, необходимо ввести его
в поле;
Изменяя ячейки — служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не
будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую
ячейку;
Предположить — используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле
Установить целевую ячейку. Результат поиска отображается в
поле Изменяя ячейки;
Ограничения — служит для отображения списка граничных
условий поставленной задачи;
Добавить — используется для отображения диалогового
окна Добавить ограничение;
Изменить — применяется для отображения диалогового
окна Изменить ограничение;
Удалить — служит для снятия указанного ограничения;
Выполнить — используется для запуска поиска решения
поставленной задачи;
Закрыть — служит для выхода из окна диалога без запуска
поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить;
Параметры — применяется для отображения диалогового
окна Параметры поиска решения, в котором можно загрузить или
сохранить оптимизируемую модель и указать предусмотренные
варианты поиска решения;
Восстановить — служит для очистки полей окна диалога и
восстановления значений параметров поиска решения, используемых по умолчанию.
Рассмотрим примеры решения задач оптимизации.
Определение максимального значения
Пример. В ресторане готовятся фирменные блюда трех видов
(блюдо А, блюдо В и блюдо С) с использованием при приготовлении ингредиентов трех видов (ингредиент 1, ингредиент 2 и
ингредиент 3). Расход ингредиентов в граммах на блюдо задается
следующей таблицей:
|
Вид ингредиента |
Блюдо А |
Блюдо В |
Блюдо С |
|
Ингредиент 1 |
20 |
50 |
10 |
|
Ингредиент 2 |
20 |
0 |
40 |
|
Ингредиент 3 |
20 |
10 |
10 |
Стоимость приготовления блюд одинакова (100 руб.).
Ежедневно в ресторан поступает 5 кг ингредиента 1 и по 4 кг ингредиентов видов 2 и 3. Каково оптимальное соотношение
дневного производства блюд различного вида, если производственные мощности ресторана позволяют использовать весь запас
поступивших продуктов?
Решение. Для решения задачи введем обозначения: пусть x1- дневной выпуск блюда А; х2 - дневной выпуск блюда В; х3 -дневной выпуск блюда С.
Составим целевую функцию - она заключается в стоимости выпущенных рестораном блюд:
Z=100x1 +100x2 +100x3
Определим имеющиеся ограничения (руководствуясь таблицей):
1. 20х1 + 50х2 +10х3 5000;
2. 20х1 + 0х2 +40х3 4000;
3. 20х1 + 10х2 +10х3 4000.
Кроме того, поскольку нельзя реализовать часть блюда и количество блюд не может быть отрицательным, добавим еще ряд ограничений:
1. Х1 > 0;
2. х2 > 0;
3. Х3 > 0;
4. x1 — целое;
5. х2 — целое;
6. х3 — целое.
Теперь можно приступить к решению задачи на компьютере.
1. Откроем новую книгу Excel.
2. В ячейки E2, E9 и E10 занесем дневной запас продуктов - числа 5000,4000 и 4000 соответственно
3. В ячейки С3, C4 и C5 занесем начальные значения неизвестных х1, х2 и х3(нули) - в дальнейшем значения этих ячеек
будут подобраны автоматически.
4.В ячейку С7 занесем формулу целевой функции =100*(С3
+ С4 + С5)
5. В ячейках диапазона С8:C10 занесем ограничения для расчета расхода
ингредиентов по видам, руководствуясь таблицей:
С8 - 20*C3+50*C4+10*C5;
С9 - 20*C3+0*C4+40*C5;
С10 - 20*C3+10*C4+10*C5.
6. Дадим команду Данные> Анализ>Поиск решения - откроется диалоговое окно Поиск решения.
7. В поле Установить целевую ячейку мышью укажем ячейку, cсодержащую оптимизируемое значение (С7) (рис.1). Установим
переключатель Равной в положение максимальному значению
(требуется максимальный объем производства).
8. В поле Изменяя ячейки мышью зададим диапазон подбираемых параметров (неизвестных хi ) — С3:С5.
9. Чтобы определить набор ограничений, щелкнем на
кнопке Добавить. В диалоговом окне Добавление ограничения в
поле Ссылка на ячейку мышью укажем диапазон С8:С10. В качестве условия зададим <=. В поле Ограничение мышью зададим
диапазон E8:E10. Это условие указывает, что дневной
расход ингредиентов не должен превосходить запасов. Щелкнем
на кнопке ОК.
Рис. 1. Пример заполнения диалогового окна Поиск решения
10. Снова щелкнем на кнопке Добавить. В поле Ссылка на
ячейку укажем диапазон С3:C5. В качестве условия зададим >=.
В поле Ограничение зададим число 0. Это условие указывает, что
число приготавливаемых блюд неотрицательно. Щелкнем на
кнопке ОК.
11. Снова щелкнем на кнопке Добавить. В поле Ссылка на
ячейку укажем диапазон С3:C5. В качестве условия выберем
пункт цел. Это условие не позволяет производить доли блюд.
Щелкнем на кнопке ОК.
12. Нажимаем кнопку параметры и выбираем – Линейная модель, оставляя все остальное без изменений.
13. Щелкнем на кнопке Выполнить. По завершении оптимизации откроется диалоговое окно Результаты поиска решения.
14. Установим переключатель Значения параметров в положение Сохранить найденное решение, после чего щелкнем на
кнопке ОК.
В результате получится оптимальный набор переменных
(оптимальное количество приготавливаемых фирменных блюд)
при данных ограничениях (при данном количестве ингредиентов): блюда А - 184 порции (х1), блюда В - 24 порции (х2) и
блюда С - 8 порций (х3). При этом общая стоимость блюд (Z)
будет максимальной и равной 21 600 руб. При этом останутся
неизрасходованными 40 г первого ингредиента (рис. 2).
Рис. 2. Результат вычислений из примера
Проанализируем полученное решение. Проверить его оптимальность можно, экспериментируя со значениями ячеек С1:Е1.
Например, допустим, что решили приготовить количества блюд,
соответственно 184, 23, 9. Тогда при той же общей стоимости
блюд будет перерасход второго ингредиента на 40 г, что, естественно, недопустимо. Можно рассмотреть и другие варианты.
Чтобы восстановить оптимальные значения, можно в любой момент повторить операцию поиска решения.
Самостоятельные задания
Вариант 1.
Кулинария магазина «О КЕЙ» выпускает два вида холодных закусок: А и В. Продукция обоих видов поступает в продажу. Для производства обоих видов используются полуфабрикаты: I и II. Максимально возможные суточные запасы этих продуктов составляют 7 и 9 центнеров. Расходы полуфабрикатов I и II на одну тонну соответствующих закусок приведены в таблице 1.
Таблица 1. Расход полуфабрикатов
Изучение покупательского спроса показало, что суточный спрос на закуски В никогда не превышает спроса на закуски А, а спрос на закуски А не превышает 3 центнеров. Оптовые цены одного центнера полуфабрикатов равны: 400 у.е. для В и 300 у.е. для А. Какое количество закусок каждого вида должна производить кулинария магазина «О КЕЙ», чтобы доход от реализации был максимален.
Вариант 2..
Для приготовления четырех фирменных блюд F1, F2, F3, F4 в ресторане используют три вида ингредиентов I1, I2, I3. Объемы выделенных ингредиентов (в граммах), нормы расхода ингредиентов (в граммах) и прибыль при приготовлении 1 блюда приведены в табл. 2. Какое количество каждого вида блюд должен производить ресторан, чтобы доход от реализации был максимален.
Таблица 2. Нормы расхода ингредиентов и прибыль от реализации 1 блюда.
|
Вид ингредиента |
Запасы |
Виды блюд |
|||
|
F1 |
F2 |
F3 |
F4 |
||
|
I1, |
350 |
40 |
20 |
20 |
30 |
|
I2 |
300 |
10 |
10 |
20 |
30 |
|
I3 |
400 |
30 |
10 |
20 |
10 |
|
Прибыль в у.е |
14 |
10 |
14 |
11 |
Определение минимального значения.
Пример.
Каждый из сотрудников ресторана (например, бармен, официант, повар и т.д.) может выполнять определенные виды работ. Почасовая оплата Сij i-му сотруднику по j – му виду работ приведена в таблице 3. Составить план выполнения работ, так, чтобы все виды работ были проведены, каждый сотрудник выполнял только работу одного вида, а суммарная стоимость почасовой оплаты была минимальной.
Таблица3. Стоимости выполнения работы
|
Сотрудники |
Почасовая оплата работ |
|||
|
1 |
2 |
3 |
4 |
|
|
1 |
350 |
420 |
610 |
200 |
|
2 |
890 |
130 |
650 |
900 |
|
3 |
430 |
520 |
600 |
720 |
|
4 |
830 |
610 |
780 |
470 |
Решение
1. Проверка задачи на сбалансированность - задача является сбалансированной, т. к. количество сотрудников соответствует числу возможных видов работ. В случае несбалансированности задачи необходимо ввести недостающее число фиктивных сотрудников (строчек) или видов работ (столбцов).
2. Построение математической модели задачи - пусть хij = 1
в случае выполнения i-м сотрудником j-го вида работ, и
хij = 0 - в случае невыполнения вида работ. Тогда математическая модель задачи примет вид:
• найти минимум функционала:
Z=min
• при следующих ограничениях:
=1, j=
=1, i=
(0;1), j= i=
3. Решение задачи с помощью надстройки Поиск решения:
- подготовку рабочего листа осуществляем в соответствии с рис. 3, формулы для расчета приведены в табл. 4;
Таблица 4. Формулы для расчета в задаче о назначениях
|
Описание |
Ячейка |
Формула |
|
Ограничения |
G1I |
=CУMM(Cll:Fll) |
|
G12 |
=CУMM(C12:F12) |
|
|
G13 |
=CУMM(C13:F13) |
|
|
GI4 |
=CУMM(C14:F14) |
|
|
Ограничения |
С15 |
=СУММ(С11:С14) |
|
D15 |
=CУMM(Dll:D14) |
|
|
Е15 |
=СУММ(Е11:Е14) |
|
|
F15 |
=CУMM(Fll:F14) |
|
|
Стоимость всех работ |
G15 |
=СУММПРИЗВ(С5:C8;C11:F14) |
Рис. 3. Подготовка рабочего листа
Рис.4. Установка параметров
• устанавливаем ограничения в окне Поиск решения, как показано на рис. 4. В окне Параметры поиска решения необходимо также установить флажок Линейная модель;
• решение задачи представлено на рис. 5.
Рис. 5. Решение задачи о назначениях
Самостоятельные задания
Задания по теме сформулированы в виде задач о назначениях. Имеется n сотрудников и т видов работ. Стоимость Сij выполнения i-м сотрудником j-го вида работ приведена в таблицах, где сотрудникам соответствуют строки, а видам работ - столбцы. Составить план выполнения видов работ так, чтобы все виды работ были проведены, каждый сотрудник был занят только одним видом деятельности, а суммарная стоимость проведения всех видов работ была минимальной.
Вариант №1
|
Сотрудники |
Стоимость выполнения |
||||
|
Виды работ |
|||||
|
1 |
2 |
3 |
4 |
5 |
|
|
1 |
320 |
360 |
210 |
650 |
1100 |
|
2 |
100 |
200 |
670 |
780 |
340 |
|
3 |
510 |
120 |
110 |
900 |
210 |
|
4 |
270 |
540 |
200 |
950 |
500 |
Вариант №2
|
Сотрудники |
Стоимость выполнения |
|||
|
Виды работ |
||||
|
1 |
2 |
3 |
4 |
|
|
1 |
860 |
620 |
200 |
500 |
|
2 |
510 |
230 |
910 |
860 |
|
3 |
300 |
800 |
120 |
900 |
|
4 |
100 |
410 |
210 |
330 |
|
5 |
300 |
720 |
990 |
500 |
2. Изучение дифракции света на простейших преградах и дифракционной решетке
3. а человек богатый и культурный англоман
4. Материальные и процессуальные особенности рассмотрения судами уголовных дел о нецелевом расходовании бюджетных средств
5. взрослому столу Можно ли давать ребёнку сосиски варёную колбасу творожные сырки обжаренные котлетки бл
6. Реферат- Кровная месть у народов Кавказа и в Осетии
7. тематической статистики
8. 3 1 Проблемы государственной политики в области налогообложения
9. Agriculture in the USA
10. Общество российскогерманской дружбы БашкортостанГермания Ассоциация учителей преподавателей немецко
11. Центробежные насосы
12. Лисанд
13. біологія Г.
14. Этический кодекс организации
15. Невербальные средства жесты, мимика, их функции
16. тема квалифицирующих признаков преступлений против общих правил безопасности по сравнению с УК 1960 годом под
17. История создания Агентства безопасности связи Армии США (1914-1945 гг)
18. тема управления базами данных СУБД
19. Реферат- Лекции - Терапия (острые экзогенные отравления)
20. Тема 15 Оценка помехоустойчивости электронных систем