Оптимизация. Содержание Целочисленная оптимизация Нелинейное программирование Примеры оптимизационных задач Постановка задачи линейного программирования. - презентация

1 Оптимизация

2 Содержание Целочисленная оптимизация Нелинейное программирование Примеры оптимизационных задач Постановка задачи линейного программирования

3 Постановка задачи оптимизации Что такое оптимизационная задача? Можно ли из нескольких решений задачи выбрать наиболее оптимальное? Все оптимизационные задачи объединяет наличие цели (целевой функции) и ограничений. В процессе решения требуется найти минимальное или максимальное значение (оптимум) целевой функции. Оптимизационная задача называется линейной, если целевая функция и ограничения линейно зависят от искомых параметров. Задачи линейной оптимизации и методы их решения изучаются в разделе линейного программирования.

4 Постановка задачи линейного программирования Классическая проблема линейного программирования, называемая задачей о коммивояжере, была сформулирована в 1934 г. Постановка задачи следующая: коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, … n и вернуться в первый город. 1 2 В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим?

5 Пример задачи: Имеется предприятие, которое производит n видов сдобы: булки, слойки и т.д. При этом расходуется сырье: мука, молоко, сахар. Рецептура изготовления определяет, сколько продуктов расходуется на изготовление единицы массы каждой сдобы. Эти соотношения можно представить в виде матрицы d ij. Дана также стоимость каждого вида сдобы: c 1, c 2,... c n. Задача об оптимальном ассортименте: Формулировка проблемы: какое количество сдобы каждого вида x 1, x 2,... x n следует выпекать, чтобы сумма продаж была максимальной? количество сырья ограниченно и равно s 1, s 2,... s n для каждого вида.

6 Задача об оптимальном ассортименте: x i 0, i [1, n]. Математическая формулировка: целевая функция - максимальна ограничения

7 Постановка задачи: Необходимо разработать диету, которая бы состояла из n продуктов. Пусть x1, x2,... xn неизвестные количества продуктов питания (ПП), которые надо купить. Стоят они c1, c2,... cn рублей за килограмм. Содержание j-го питательного вещества ( j=1, 2,..., m) в i-том продукте питания задается матрицей dij. Даны также биологические нормы b1, b2,... bm по каждому питательному веществу (ПВ) на месяц. Задача о диете. Постановка Формулировка проблемы: требуется приобрести набор продуктов питания в таком количестве x1, x2,... xn, чтобы удовлетворялись биологические нормы потребления ПВ, а цена набора была бы минимальной.

8 Задача о диете Математическая формулировка: x i 0, i [1, n]. целевая функция - минимальна ограничения

9 Общий для перечисленных задач метод решения называется симплекс-методом. При n = 2 данный метод имеет наглядную графическую интерпретацию. Метод решения. Диета состоит из двух продуктов: хлеба и сала по цене c1 = 5 и c2 = 30. Диета должна удовлетворять ограничениям по белкам, жирам и углеводам, которые содержатся в сале и хлебе в следующих (произвольных) пропорциях: Рассмотрим пример на основе задачи о диете: Хлеб Сало Нормы потребления Белки 0,1 0,25 Жиры 0 0,52,5 Углеводы 0,50,215 Биологические нормы потребления питательных веществ

10 Требуется составить оптимальную диету минимальной стоимости. или в преобразованном виде: (А) x+2y 50, (B) y 5, (C) 5x+2y 150. Задача о диете. Графическая интерпретация (т.е. найти, сколько следует купить хлеба и сала, чтобы соблюдалась биологическая норма) Искомые неотрицательные значения x и y должны удовлетворять следующим условиям:

11 Графики прямых x+2y=50, y = 5 и 5x+2y=150. Искомое решение лежит в правом верхнем квадранте (условие неотрицательности) и выше-правее проведенных прямых. Минимизируемая целевая функция f(x,y)=5x+30y образует семейство параллельных прямых. Метод решения. Графическая интерпретация Искомое решение - точка пересечения прямых x+2y=50 и y =5, т.е. x=40, y=5.

12 Создать и заполнить таблицу в Excel Решение задачи Поиском решений(Excel) Задать целевую функцию Задать ограничения Воспользоваться поиском решений Задать ограничения Проверить параметры Выполнить >> Оk

13 Не всегда Excel с первого раза находит решение. Если вы убеждены в отсутствии собственных ошибок (правильно рассчитываете целевую функцию, верно накладываете ограничения и т.п.), проверьте установки решателя, которые доступны в диалоговом окне Параметры поиска решения. Уменьшите Относительную погрешность и Допустимое отклонение (например, в 2 раза). Решение задачи Поиском решений(Excel)

14 Вопросы и упражнения 1. Дайте определение целевой функции. 2. Как сформулировать общую задачу линейного программирования? Постарайтесь записать математическое определение задачи. 3. Составьте рацион минимальной стоимости, обеспечивающий месячную биологическую норму. Данные представлены в таблице. Хлеб СалоМаргарин КартофельЯйца Норма Белки 0,10,2000,66 Жиры 00,50,8004 Углеводы 0,50,200,5020 Цена Учтите, что количество закупаемых продуктов не должно быть отрицательным или нулевым.

15 Вопросы и упражнения 4. Решите задачу об укладке рюкзака. Каждый предмет можно взять только один раз, объем рюкзака ограничен 100 литрами. Необходимо взять как можно больше нужных вещей. Предмет МассаОбъём, л Палатка 2060 Спальник 555 Одеяло 832 Радиоприёмник 220 Мяч 0,510 Топор 32 Пакет с едой 108

16 Оптимизационные задачи. Транспортная задача Фирма имеет 4 фабрики: Также фирма имеет 5 центров распределения товаров: Город Возможности (ед./день) Денвер 200 Бостон 150 Новый Орлеан 225 Даллас 175 Город Возможности (ед./день) Лос-Анджелес 100 Даллас 200 Вашингтон 50 Атланта 150

17 Транспортная задача Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в таблице: Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы. Лос- Анджелес Далла с Сент- Луис Вашингто н Атланта Денвер 1,521,752,25 Бостон 2,521,7511,5 Новый Орлеан 21,5 1,75 Даллас 20,51,75

18 Транспортная задача называется сбалансированной, если объем произведенной продукции равен объему потребностей в ней. Требование сбалансированности не является слишком обременительным, так как в противном случае в модель нужно было бы ввести: В случае перепроизводства фиктивный склад, стоимость перевозок продукции в который полагается равной стоимости складирования, а объемы перевозок объемам излишков продукции на фабриках. В случае дефицита фиктивную фабрику, стоимость перевозок продукции с которой полагается равной стоимости штрафов за недопоставку, а объемы перевозок объемам недопоставок на оптовые склады. Транспортная задача

19 Транспортная задача. Решение Поскольку решаемая модель сбалансирована, в данном случае не надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции. Для решения данной задачи необходимо построить её математическую модель. Неизвестными в данной задаче являются объемы перевозок. Пусть x ij объем перевозок, а с ij стоимость перевозки единицы продукции с i-й фабрики на j-й склад соответственно. Функция цели это суммарные транспортные расходы, которые следует минимизировать.

20 Транспортная задача. Решение с помощью Excel Неизвестные x ij должны удовлетворять ограничениям. Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик а потребности всех центров распределения должны быть полностью удовлетворены Объемы перевозок не должны быть отрицательными: xij 0, i [1, 4], j [1, 5] Здесь аi объем производства на i-й фабрике, bj спрос в j-м центре распределения.

21 Для решения этой задачи с помощью средства поиска решений необходимо ввести данные следующим образом: Транспортная задача. Решение с помощью Excel

22 В ячейки А10:Е10 введены формулы: =СУММ(А6:А9) =СУММ(В6:В9) =СУММ(С6:С9) =CУMM(D6:D9) =СУММ(Е6:Е9) В ячейки F6:F9 введены формулы: =СУММ(А6:Е6) =СУММ(А7:Е7) =СУММ(А8:Е8) =СУММ(А9:Е9) Транспортная задача. Решение с помощью Excel объем продукции, ввозимой в центры распределения объем продукции, вывозимой с фабрик

23 Теперь, выбрав команду Сервис Поиск решения, необходимо заполнить открывшееся диалоговое окно «Поиск решения» Транспортная задача. Решение с помощью Excel

24 В диалоговом окне Параметры поиска решения устанавливается флажок Линейная модель. После нажатия кнопки Выполнить средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы: Транспортная задача. Решение с помощью Excel

25 Постановка задачи: крупная компания торгует следующими группами товаров: автомобили, компьютеры, мебель, парфюмерия, ткани. Руководитель отдела маркетинга должен разработать стратегию проведения рекламной компании, то есть определить какую сумму следует вложить на рекламирование каждой группы товаров на радио, телевидении, печати и т.д. Задача о рекламной компании

26 Очевидно, что эффективность рекламы неодинакова: на рубль, вложенный в рекламу товара на телевидении можно получить большую прибыль, чем от рекламы в газете. Предположим, что в результате маркетинговых исследований были получены данные, характеризующие величину прибыли от видов рекламы (в рублях) на рубль вложенных средств: Реклама МебельКомпьютеры Парфюмери я Ткани Авто Газета Радио Телевиден ие Щитовая Задача о рекламной компании

27 Пусть xij - средства, которые следует выделить для рекламы j-го товара на i - ом носителе рекламы; матрица cij показывает, какую прибыль приносит каждый рубль, вложенный в рекламу j-го товара на i-ом носителе. Наша цель - получить максимальную прибыль, т.е.: при этом мы ограничены в средствах: не забудем условие неотрицательности: xij 0. Задача о рекламной компании. Математическая формулировка

28 Открыть новый лист Excel, заполнить ячейки листа, как указано на рисунке: Задача о рекламной компании. Решение в Excel

29 Ячейки С13:G16 отводятся под искомые значения xij; формула, по которой рассчитывается получаемая от рекламы прибыль, заносится в ячейку С18, а сумма расходуемых средств в F18: Задача о рекламной компании. Решение в Excel

30 С помощью «Поиска решения» найдем ответ, который приведен в виде таблицы ниже: Газета Радио Телевидени е Щитовая Прибыль 30800Всего 2200 Как видно, после довольно длительных манипуляций получилось тривиальное решение, которое можно прокомментировать так: "Все деньги следует вложить в самую эффективную рекламу (телевидение) самого прибыльного товара (автомобили)". Задача о рекламной компании. Решение в Excel

31 Для каждого товара имеется некоторое предельное значение объема продаж Nпр, обусловленное ограниченностью потребительского спроса. На рисунке схематически изображен график зависимости объема продаж (N) от расходуемых средств на его рекламу (S), который асимптотически приближается к величине Nпр, но не превосходит её. Нелинейное программирование

32 Точный вид зависимости c ij от x ij определить довольно сложно. Будем приближенно считать, что прибыль от продажи товара при увеличении расходов на рекламу вначале линейно растет, а потом не меняется. То есть, Здесь N ij - значения предельной прибыли для i-го товара, рекламируемого на j-том носителе. Нелинейное программирование

33 Нелинейное программирование. Задача о рекламной компании В таблице приведены значения предельной прибыли для каждого товара (способ получения конкретных значений является самостоятельной, весьма сложной задачей): Реклама МебельКомпьютеры Парфюмери я Ткан и Авто Газета Радио Телевидени е Щитовая

34 Теперь нужно внести необходимые изменения в рабочий лист Excel: В ячейки C27:G30 записать значения предельной прибыли для каждого товара В ячейку С34 внести соответствующую формулу, рассчитывающую прибыль от рекламы мебели в газете: =ЕСЛИ(C6*C13<=C27;C6*C13;C27). "Продлить" формулу на остальные ячейки диапазона С34:G37. Прибыль теперь рассчитывается как сумма: =СУММ(C34:G37). Нелинейное программирование. Решение задачи о рекламной компании

35 Вызвать Поиск решения и учесть нелинейность построенной модели. Для этого в Параметрах нужно «убрать» пометку против строки Линейная модель: Нелинейное программирование. Решение задачи о рекламной компании

36 После поиска решения получим результат, отражающий один из возможных вариантов вложения средств: Распределение денег на рекламу: Газета Радио Телевидение Щитовая Прибыль 22828Всего 2200 Повторите вычисления с уменьшенной погрешностью. Если суммы не изменились, или изменились очень незначительно, то решение найдено. Нелинейное программирование. Решение задачи о рекламной компании

37 Решение системы нелинейных уравнений Кроме оптимизационных задач, средство поиска решений позволяет находить решения систем нелинейных уравнений. Рассмотрим, как это делается, на примере решения следующей системы: (Д.1) Пара (х, у) является решением системы (Д.1) тогда и только тогда, когда она является решением следующего уравнения с двумя неизвестными: (x2 + y2 - 3)2+( 2x+ 3y-1)2 = 0 (Д.2)

38 Вопросы и упражнения 1. В каком случае транспортная задача является несбалансированной? 2. Как преобразовать несбалансированную транспортную задачу к сбалансированной? 3. Найдите решение транспортной задачи, данные для которой приведены в таблице: ABCDПроизводств о Потребление

39 Целочисленная оптимизация Нужно совершить авиа тур из Москвы по столицам Европы минимальной стоимости. Цена билетов приведена в таблице. Москва БерлинРим Лондон Москва Берлин Рим Лондон Необходимо заметить, что стоимость перелета «туда» и «обратно» может различаться.

40 Математическая формулировка задачи об авиа туре Математическая формулировка задачи будет выглядеть так: Здесь n – города, которые составляют замкнутый тур, c ij – стоимость поездки из i –го в j-й город. В качестве искомых величин x ij выступает факт посещения того или иного города, поэтому естественно считать x ij равным 1, если коммивояжер отправился из i в j город, и 0 в противном случае. Посещения каждого города должны быть строго однократными, следовательно, обязательно выполнение условий: которые являются ограничителями.

41 Сформулированную таким образом задачу можно решить с помощью «Поиска решения». Для этого нужно ввести данные в лист Excel: Задача об авиа туре. Решение в Excel

42 Решение в виде массива нулей и единиц будет размещено в ячейках B10:E13. Необходимо обратить внимание на диагональные ячейки, которые соответствуют маршруту Москва-Москва, Рим-Рим и т.д. Нужно указать Поиску решения исключить их из возможных направлений маршрута. Для этого в диагональные ячейки занесены значения, в несколько раз превышающие максимально возможную стоимость перелета. В ячейку G15 поместить формулу расчета целевой функции =СУММПРОИЗВ(B3:E6;B10:E13). В ячейки F10:F13 и B14:E14 - функцию вычисления суммы по горизонтальным и вертикальным ячейкам (на рис. показано для строки B13:E13). Задача об авиа туре. Решение в Excel

43 Диалоговое окно «Поиск решения» заполняется, как показано на рисунке: Задача об авиа туре. Решение в Excel Необходимо обратить внимание на новое условие в ограничениях: ячейки B10:E13 указаны как двоичные, т.е. либо 0, либо 1!

44 Единица в ячейке означает отлет – прилет из города в город, указанные в соответствующих столбце и строке. Например, наш тур начинается отлетом из Москвы в Лондон, из Лондона в Рим и т.д. Общая цена оптимально подобранного тура составила 610. Москва БерлинРим Лондонприбытие Москва Берлин Рим Лондон отлёт 1111 Задача об авиа туре. Решение в Excel

45 Целочисленная оптимизация. Задача о назначениях К задачам целочисленной оптимизация относится и известная задача о назначениях. Суть проблемы: надо распределить m рабочих для выполнения ими n работ таким образом, чтобы общая себестоимость выполненных работ была минимальна.

46 Математическая формулировка задачи о назначениях Здесь x ij равное 1 означает назначение, а 0 – не назначение на выполняемую работу. При этом одному рабочему должна соответствовать только одна выполняемая работа, т.е.: Стоимость выполнения i – ой работы j – ым рабочим равна c ij :

47 Количество работ и число рабочих может не совпадать! В этом случае используем прием, описанный в транспортной задаче: вводится фиктивная работа (работы), если m >n, или фиктивный рабочий (рабочие) (m

48 Суть проблемы: Научный институт поставил лакокрасочному заводу компьютерную программу, но у завода не оказалось достаточно денег. Как выход, завод предложил в качестве платы свою продукцию – банки с краской емкостью 15 и 55 л. Подходящая краска стоила 14,6 рублей за литр, а пустые банки - 24 и 30 руб., соответственно. Осталось выбрать: в каких емкостях взять краску, чтобы максимизировать суммарный объем. Целочисленная оптимизация. Задача о краске

49 Имеется: целевая функция - объем краски, переменные - количества наполненных краской банок по 15 и 55 литров, которые нужно забрать, три ограничения: 1. стоимость краски не должна превышать оговоренных 14 тыс. рублей, 2. нельзя брать неполную банку (ограничение на целочисленность переменных) и 3. количества банок разной вместимости не должны быть отрицательными числами. Целочисленная оптимизация. Задача о краске

50 В таблице приведены данные, занесенные в Excel и решение, полученное с помощью надстройки Поиск решения: Сумма денег руб. Предложение Товарстоимость Краска 14,6 руб./л. Пустая тара 15 л.24 руб./шт. Пустая тара 55 л.30 руб./шт. Выбор Банка 15 л.6 Банка 55 л.15 Решение при помощи решателя Истрачено денег руб. Остаток 47 руб. Всего литров краски 915 Задача о краске. Решение в Excel

51 Если в качестве целевой функции выбрать не количество краски, а сумму истраченных денег, то решение окажется другим! Очень важный результат, который указывает на необходимость точно формулировать оптимизационную задачу. Правильное решение можно получить только изменив начальные установки точности Поиска решения с 5 до 1%: Задача о краске. Решение в Excel