В. С. Алиев Решение и анализ оптимизационных задач Учебное пособие
| Вид материала | Решение |
- «решение оптимизационных экономических задач методами линейного программирования», 283.33kb.
- Решение экономических задач компьютерными средствами > Информатика в экономике: Учебное, 721.96kb.
- 1 Общая характеристика оптимизационных задач и методов их решения, 47.12kb.
- Рабочая программа дисциплины «Методы решения оптимизационных задач в бизнесе» Рекомендуется, 114.73kb.
- Н. Ю. Каменская оценка, анализ иуправление рисками Учебное пособие, 1625.75kb.
- Общий курс физики т-1 Механика: учебное пособие М.: Физматлит, 2002. Сивухин Д. В.,, 679.32kb.
- Н. А. Анализ финансовой отчетности: Учебное пособие, 4614.8kb.
- Учебное пособие для уч-ся 9 кл ср шк. / Н. А. Абасов, 212.78kb.
- Ненаглядное пособие по тригонометрии, 141.71kb.
- Учебное пособие Самара 2009 год удк 621. 313. 3 Электротехника, 2026.33kb.
В.С. Алиев
Решение и анализ оптимизационных задач
Учебное пособие для слушателей дистанционного обучения
Института открытого образования
по курсу
Информационные технологии управления
Москва – 2009 г.
Содержание
Занятие 1 3
Глава 1. Моделирование и решение задач линейного программирования. 3
1.1. Краткое сведение о задаче линейного программирования. 3
1.1.1. Примеры моделирования и решения задач линейного программирования. 4
Задача 1. Оптимальное распределение финансовых средств, отпускаемых на рекламу (задача о рекламе). 4
1.2. Моделирование и решение транспортной задачи. 10
Краткое сведение о транспортной задачи 10
Задача 2. Задача об оптимальном плане перевозки муки 12
Занятие 1
Глава 1. Моделирование и решение задач линейного программирования.
1.1. Краткое сведение о задаче линейного программирования.
Стандартная задача линейного программирования в матричной форме имеет следующий вид [1-2]
max(c,x)
Ax<=b, x>=0, (1)
где x=(x1, x2,… xn), c=(c1, c2,… cn), b=(b1, b2,… bm), A=(aij)- матрица коэффициентов. Вектор с называется вектором коэффициентов линейной формы (с,х), b-вектором ограничений.
Все другие формы задач линейного программирования простыми преобразованиями можно привести к стандартной форме задачи линейного программирования. Например, уравнение можно заменить двумя неравенствами
a
i1x1+ai2x2+…+ ainxn=bi ai1x1+ai2x2+…+ ainxn<=<=bi, -ai1x1-ai2x2-…-ainxn<=-bi;
з
адачу минимизации линейной формы легко свести к задаче максимизации линейной формы min(c,x) max(-c,x) и т.д.Линейная форма (c,x) подлежащая максимизации (или минимизации), называется целевой функцией. Вектор х, удовлетворяющий всем ограничениям задачи линейного программирования, называется допустимым вектором, или планом. Задача линейного программирования, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор x*, доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором х, т.е. (с, x*)>=(c,x), называется решением задачи, или оптимальным планом. Максимальное значение d=(с, x*) целевой функции называется значением задачи.
Величина прироста целевой функции на единицу увеличения элемента вектора ограничений называется теневой ценой (или двойственной оценкой) этого ограничения.
Величина прироста целевой функции при увеличении (уменьшении) на единицу от нижней (верхней) границы переменной называется нормированной стоимостью (или относительной оценки) этой переменной.
Задачей, двойственной к (1) (двойственной задачей), называется задача линейного программирования от m переменных y1, y2,… ym вида
min(b,y)
A'y>=c, y>=0, (2)
где y=(y1, y2,… ym), A' транспонированная матрица.
Теорема двойственности. Если прямая и двойственные задачи (1) и (2) имеют допустимые решения, то обе они имеют решения x* и y* и эти решения удовлетворяют условию (с, x*)=(b, y*) т.е. значения исходной и двойственной задачи совпадают.
Отметим, что оптимальное решение двойственной задачи (2) y* совпадает с вектором двойственных (теневых) оценок задачи (1).
1.1.1. Примеры моделирования и решения задач линейного программирования.
Задача 1. Оптимальное распределение финансовых средств, отпускаемых на рекламу (задача о рекламе).
Содержание задачи. Фирма имеет возможность рекламировать свою продукцию, используя местные радио- и телевизионную сети. Затраты на рекламу в бюджете фирмы ограничены величиной 1000 долларов в месяц. Каждая минута радиорекламы обходится в 5 долларов, а каждая минута телерекламы - в 100 долларов. Фирма хотела бы использовать радиосеть, по крайней мере, в два раза чаще, чем сеть телевидения. Опыт прошлых лет показал, что объём сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше сбыта, обеспечиваемого одной минутой радиорекламы. Определите оптимальное распределение финансовых средств, ежемесячно отпускаемых на рекламу, между радио- и телерекламой.
Экономико-математическая постановка задачи. Обозначим количества используемых минут в радио - и телесети соответственно через xr и xt. Примем за единицу объём сбыта обеспечиваемого одной минутой радиорекламы. Тогда общий объём сбыта можно выразить линейной формой xr+25xt, которого необходимо максимизировать. По условию общие затраты на рекламу ограничены сверху 5xr+100xt<=1000 и xr>=2xt. Кроме того очевидно, что xr>=0, xt>=0.
Экономико-математическая формулировка и модель задачи. Из существующего множества решений линейных ограничений
5xr+100xt<=1000,
-xr+2xt<=0,
xr>=0, xt>=0
найти такие количества используемых минут xr и xt в радио - и телесети соответственно, которые реализуют максимальную величину общего объёма сбыта в линейной функции цели:
x
r+25xt мах.Компьютерная модель и решение задачи.
В следующей таблице пакета EXCEL [3-4] введём матрицу (массив B5:C6), вектора ограничений (массив D5:D6), вектора коэффициентов целевой функции (массив B4:B5) и линейные формы задачи о рекламе (массив E4:E6). Формулы для линейных форм заданы ниже. Стрелка означает, что в ячейке E4 набирается формула, которая указана в таблице, а потом эта формула копируется в ячейки E5:E6. Ячейки B3:C3 резервированы для переменных задачи (изменяемые ячейки).
Таблица 1.
Формулы таблицы:
| Ячейка | Формула или содержание |
| E  4:E6 | =СУММПРОИЗВ(B$3:C$3;B4:C4) |
| B3:C3 | Изменяемые ячейки (переменные задачи) |
| E4 | Целевая (результирующая) ячейка |
Далее в меню Сервис выполняем команду Поиск решения. В окне "Поиск решения" моделируем оптимизационную задачу, которого должен решать компьютер:
Р
ис.1. Диалоговое окно "Поиск решения".
Отметим, что для формирования блока ограничений поставленной задачи необходимо нажать кнопку "Добавить". Открывается диалоговое окно "Добавление ограничение", где сформируются соответствующие ограничения задачи. На рисунке 2 формированы ограничения на линейные формы.
Р
ис.2. Диалоговое окно «Добавление ограничения».
Нажмите на кнопку "Добавить", чтобы, не возвращаясь в окно диалога "Поиск решения", наложить новое условие на поиск решения задачи. А именно B3:C3>=0. Если формируются последние ограничения задачи, необходимо нажать кнопку "ОК".
Чтобы изменить, или удалить ограничение необходимо выделить её, а потом нажать на соответствующую кнопку "Изменить" или "Удалить" в окне "Поиск решения".
Далее компьютеру необходимо указать, что решается задача линейного программирования. Для этого нажмите кнопку "Параметры" диалогового окна "Поиск решения". В диалоговом окне "Параметры поиска решения" установите флажок "Линейная модель" и нажмите кнопку "ОК".
Для получения более подробную информацию о диалоговых окнах нажмите кнопку "Справка".
Наконец компьютерная модель задачи готова. С помощью кнопки "Выполнить" диалогового окна "Поиск решения" запустите процесс поиска решения. После завершение этого процесса появится диалоговое окно "Результаты поиска решения":
Р
ис.3. Диалоговое окно "Результаты поиска решения".
Для выдачи ещё и отчетов, выделяем соответствующие отчеты и нажимаем кнопку "ОК".
Экономическая интерпретация полученных результатов и формулировка рекомендаций для принятия решений.
На листе Excel, где формировали задачу, получаем решение задачи:
Таблица 2.
На отдельных листах Excel получаем каждого из этих трёх отчетов.
Таблица 3.
| Отчет по результатам | | | | | |
| Целевая ячейка (Максимум) | | | | ||
| Ячейка | Имя | Исходно | Результат | | |
| $E$4 | объём сбыта лин.формы | 0 | 245,454545 | | |
| Изменяемые ячейки | | | | | |
| Ячейка | Имя | Исходно | Результат | | |
| $B$3 | колич. минут радио | 0 | 18,1818182 | | |
| $C$3 | колич. минут теле | 0 | 9,09090909 | | |
| Ограничения | | | | | |
| Ячейка | Имя | Значение | формула | Статус | Разница |
| $E$5 | xradio>=2xtele лин.формы | 0 | $E$5<=$D$5 | связанное | 0 |
| $E$6 | затраты лин.формы | 1000 | $E$6<=$D$6 | связанное | 0 |
| $B$3 | колич. минут радио | 18,182 | $B$3>=0 | не связан. | 18,18 |
| $C$3 | колич. минут теле | 9,0909 | $C$3>=0 | не связан. | 9,091 |
Статус связанное для ограничений означает, что соответствующий ресурс дефицитный (например, затраты) и в оптимальном решении линейная форма (затраты ресурса) принимает граничное значение ограничения на ресурс, а для переменных означает, что соответствующая переменная в оптимальном решении принимает граничное значение ограничения на переменную. Не связанность имеет обратный смысл. Отметим, что не связанные переменные являются базисными.
Из таблиц 2 и 3 получаем, что оптимальное распределение финансовых средств достигается тогда, когда ежемесячно используется 18,2 минут радиорекламы, 9,1 минут телерекламы. При этом достигается максимальный объём - 245,45 единиц сбыта. Все деньги отпускаемые фирмой на рекламу использованы (ограничение E6<=D6 связанное), т.е. этот ресурс дефицитный. Оба переменные базисные (не связанные).
Таблица 4.
| Отчет по устойчивости | | | | | | |
| Изменяемые ячейки | | | | | | |
| | | Результ. | Нормир. | Целевой | Допуст. | Допуст. |
| ячейка | имя | значение | стоим. | Коэфф. | Увелич. | Уменьш. |
| $B$3 | колич. минут радио | 18,18 | 0 | 1 | 0,25 | 13,5 |
| $C$3 | колич. минут теле | 9,091 | 0 | 25 | 1E+30 | 5 |
| Ограничения | | | | | | |
| | | Результ. | Теневая | Огранич. | Допуст. | Допуст. |
| ячейка | имя | значение | Цена | Прав.часть | Увелич. | Уменьш. |
| $E$5 | xradio>=2xtele лин.формы | 0 | 0,227 | 0 | 20 | 200 |
| $E$6 | затраты лин.формы | 1000 | 0,245 | 1000 | 1E+30 | 1000 |
Нормированная стоимость (или относительная оценка) показывает, насколько возрастает целевая функция при увеличении (уменьшении) на единицу от нижней (верхней) границы переменная.
Допустимое Увеличение (Уменьшение) целевого коэффициента показывает, насколько можно его увеличить (уменьшить) не меняя базис.
Теневая цена (или двойственная оценка) - величина прироста целевой функции на единицу увеличения элемента вектора ограничений.
Допустимое Увеличение (Уменьшение) правой или левой части ограничения показывает, насколько можно её увеличить (уменьшить) не меняя базис.
В нашей задаче, например коэффициента 25 переменного xt, в целевой функции, можно изменить в интервале [5,). При этом будет выгодно останавливаться на прежнем решении, т.е. использовать теле- и радиорекламы одновременно (хотя и другими оптимальными значениями). Далее, если затраты на рекламу в бюджете фирмы были на 1 доллар больше, т.е. были 1001 долларов, то это дало бы 0,245 единиц дополнительного сбыта в оптимальном решении. Правый часть ограничения на строке затраты можно изменить в интервале [1000, ). При этом будет выгодно останавливаться на прежнем решении, т.е. использовать теле- и радиорекламы одновременно (хотя и другими оптимальными значениями).
Таблица 5.
| Отчет по пределам | | | | | | |
| | Целевое | | | | | |
| Ячейка | Имя | значение | | | | |
| $E$4 | объём сбыта лин.формы | 245,45 | | | | |
| | Изменяемое | | Нижний | Целевой | Верхний | Целевой |
| Ячейка | Имя | значение | предел | результ. | предел | результат |
| $B$3 | колич. минут радио | 18,182 | 18,18 | 245,45 | 18,18 | 245,45 |
| $C$3 | колич. минут теле | 9,0909 | 0 | 18,182 | 9,091 | 245,45 |
Нижний (Верхний) предел - наименьшее (наибольшее) значение ячейки, если фиксировать оптимальных значений других ячеек и удовлетворяя все ограничения.
Целевой результат - значение целевой функции при этих значениях ячеек.
В нашем задаче, например число 0 является наименьшим значением ячейки С3 (переменного xt), которое совместно со значением ячейки В3 (переменного xr) равное 18,1818 удовлетворяют все ограничения. При этом значение целевой функции (целевой результат) равно 18,18182.
1.2. Моделирование и решение транспортной задачи.
Краткое сведение о транспортной задачи
Имеется m пунктов P1, P2…,Pm производства однородного продукта, причем объём производства в пункте Pi равен ai единиц, i=1, 2, …, m. Произведенный продукт потребляется в пунктах G1, G2…, Gn и потребность в нем в пункте Gj равен bj единиц, j=1, 2, .., n. Требуется составить план перевозок из пунктов Pi, i=1, 2, …, m, в пункты Gj, j=1, 2, .., n, чтобы удовлетворить потребности в продукте bj и минимизировать транспортные расходы. Обозначим через xij количество продукта, поставляемого производителем Pi потребителю Gj, а через cij стоимость перевозок одной единицы продукта из пункта Pi в пункт Gj (i=1, 2, …, m, j=1, 2, .., n). Тогда математический модель транспортной задачи линейного программирования имеет следующий вид:
(3)
(4)
(5)
(6)В этой задаче (3) имеет смысл требования минимизации суммарной стоимости перевозок, а условия (4) и (5)-соответственно ограничений на количество продукта, которое может быть вывезено от каждого производителя и ограничений на потребление этого продукта каждым потребителем.
Транспортная задача имеет решение в том и только в том случае, когда выполняется условие
(7)Если имеет место равенство
(8)то модель называется сбалансированной моделью и имеет следующий вид
(9)
(10)
(11) (12)Транспортную модель всегда можно сбалансировать. Если спрос превышает объём производства, можно ввести дополнительный фиктивный исходный пункт с производительностью
. Количество продукции, "отправляемой" фиктивным заводом в пункт назначения, будет объём недостающей продукции в этом пункте. 
, или 
равен штрафу за единицу продукции, недополученную в соответствующем пункте назначении. Если же 
, то вводится фиктивный пункт назначения со спросом 
. Продукции, поступающие с некоторого исходного пункта в фиктивный пункт назначения, представляют избыток производства на этом заводе. Соответствующая стоимость перевозки равно нулю или штрафу за хранение продукции на складе завода. Многопродуктовая модель изменяется следующим образом. Вместо того, чтобы каждый завод рассматривать как один исходный пункт, разбивается он на несколько исходных пунктов в соответствии с числом выпускаемом им продуктом. Считается, что каждый пункт назначения состоит из пунктов назначения равной количеству всех продуктов.
Запрещенным маршрутам соответствует очень высокая стоимость перевозки.
Задача 2. Задача об оптимальном плане перевозки муки
Содержание задачи. На трёх хлебокомбинатах ежедневно производится 110, 190 и 90т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170, 80т. Тарифы перевозок 1т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей
С=
. Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.
Экономико-математическая постановка задачи. Обозначим через xij количество муки, поставляемой хлебокомбинатом Pi хлебозаводу Gj (i=1, 2, 3, j=1, 2, 3, 4). Вектор объёма производства муки в хлебокомбинатах равен (a1, a2, a3)=(110, 190, 90), а вектор объёма спроса хлебокомбинатов на муку равен (b1, b2, b3, b4)=(80, 60, 170, 80). Общий объём муки, поставляемой хлебокомбинатом P1 хлебозаводам Gj, j=1, 2, 3, 4 удовлетворяет неравенство x11 + x12 + x13 + x14 <=110. Аналогично для объёмов продукта, поставляемого хлебокомбинатами P2, P3 верны неравенства x21 + x22 + x23 + x24 <=190, x31 + x32 + x33 + x34 <=90. Кроме того спросы хлебозаводов должны удовлетворяться, т.е. x11 + x21 + x31<=80, x12 + x22 + x32>=60, x13 + x23 + x33>=170, x14 + x24 + x34>=80. Суммарная стоимость перевозок вычисляется линейной формой 8x11 + x12 + 9x13 + 7x14 + 4x21 + 6x22 + 2x23 + 12x24 + 3x31 + 5x32 + 8x33 + 9x34 .
Экономико-математическая формулировка и модель задачи.
=390, т.е. спрос равен предложению и задача является сбалансированной транспортной задачей. Поэтому экономико-математическую модель задачи можно формулировать следующим образомmin (8x11+x12+9x13+7x14+4x21+6x22+2x23+12x24+3x31+5x32+8x33+9x34)
x11 + x12 + x13 + x14=110,
x21 + x22 + x23 + x24=190,
x31 + x32 + x33 + x34=90,
x11 + x21 + x31=80,
x12 + x22 + x32=60,
x13 + x23 + x33=170,
x14 + x24 + x34=80,
xij>=0, i=1, 2, 3, j=1, 2, 3, 4.
Компьютерная модель и решение задачи.
В следующей таблице введём матрицу затрат перевозок муки (ячейки С9:F11), предложения муки в хлебокомбинатах (ячейки B9:B11), спрос на муку в хлебозаводах (ячейки C7:F7):
Таблица 6.
Формулы таблицы:
| Ячейка | Формула или содержание |
| B3:B5 | =СУММ(C3:F3)-суммарный вывоз муки из хлебокомбината1 во все хлебозаводы |
| C6:F6 | =СУММ(C3:C5)-суммарное поступление муки в хлебозавод1 из всех хлебок-тов |
| C12:F12 | =СУММПРОИЗВ(C3:C5;C9:C11)-суммарные транспортные расходы для Хлебоз.1 |
| B12 | =СУММ(C12:F12)-целевая (результирующая) ячейка |
| C13,F13 | СУММ(B9:B11), СУММ(C7:F7) - суммарное предложение и запрос, соответственно |
| C3:F5 | Изменяемые ячейки (переменные задачи) |
| C7:F7 | Запросы хлебозаводов на муки |
| B9:B11 | Предложения муки хлебокомбинатами |
| C9:F11 | Затраты на перевозку муки от хлебокомбинатов в хлебозаводы |
Стрелки означают, что в первой ячейке диапазона набирается формула, которая указана в таблице, а потом эта формула копируется в остальные ячейки диапазона в указанном стрелками направлении.
В меню Сервис выполняем команду Поиск решения. Так как значения ячеек C13 и F13 совпадают, то спрос равен предложению. Тогда в окне "Поиск решения" мы должны моделировать сбалансированную транспортную задачу, которого должен решать компьютер:
Р
ис.5. Диалоговое окно "Поиск решения".
Экономическая интерпретация полученных результатов и формулировка рекомендаций для принятия решений.
После запуска процесса поиска решения на листе Excel, где сформировали задачу, получаем решение задачи:
Таблица 7.
Из этой таблицы видно, что для того чтобы с минимальными транспортными затратами 1280 руб. удовлетворить запросы хлебозаводов, необходимо из имеющейся в хлебокомбинат1 муки 110т, 60т завести в хлебозавод2, а 50т в хлебозавод4. Далее, из имеющейся в хлебокомбинат2 муки 190т, 20т завести в хлебозавод1, а 170т в хлебозавод3, из имеющейся в хлебокомбинат3 муки 90т, 60т завести в хлебозавод1, а 30т в хлебозавод4. При этом суммарные транспортные затраты на перевозку муки в хлебозаводы соответственно равны 260, 60, 340, 620 рублей.
Замечание. Необходимо отметить, что аналогично можно решать и другие задачи с использованием MS Excel, которые приводятся к решению задачи линейного программирования. Например, моделирование и решение транспортной задачи, задачи о назначениях, задач в конфликтных ситуациях (матричные игры).