Решение задач линейного программирования. 3 Краткое сведение о задаче линейного программировани

Часть 1. Модели оптимизационных задач.

1.1. Моделирование и решение задач линейного программирования.

Краткое сведение о задаче линейного программирования.

max(c,x)

где x=(x₁, x₂,… x_n), c=(c₁, c₂,… c_n), b=(b₁, b₂,… b_m), A=(a_ij)- матрица коэффициентов. Вектор с называется вектором коэффициентов линейной формы (с,х), b-вектором ограничений.

Все другие формы задач линейного программирования простыми преобразованиями можно привести к стандартной форме задачи линейного программирования. Например, уравнение можно заменить двумя неравенствами

a_i1x₁+a_i2x₂+…+ a_inx_n=b_i a_i1x₁+a_i2x₂+…+ a_inx_n

i, -a_i1x₁-a_i2x₂-…-a_inx_ni;

задачу минимизации линейной формы легко свести к задаче максимизации линейной формы min(c,x) max(-c,x) и т.д.

Линейная форма (c,x) подлежащая максимизации (или минимизации), называется целевой функцией. Вектор х, удовлетворяющий всем ограничениям задачи линейного программирования, называется допустимым вектором, или планом. Задача линейного программирования, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор x*, доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором х, т.е. (с, x*)>=(c,x), называется решением задачи, или оптимальным планом. Максимальное значение d=(с, x*) целевой функции называется значением задачи.

Величина прироста целевой функции на единицу увеличения элемента вектора ограничений называется теневой ценой (или двойственной оценкой) этого ограничения.

Величина прироста целевой функции при увеличении (уменьшении) на единицу от нижней (верхней) границы переменной называется нормированной стоимостью (или относительной оценки) этой переменной.

Задачей, двойственной к (1) (двойственной задачей), называется задача линейного программирования от m переменных y₁, y₂,… y_m вида

min(b,y)

A'y>=c, y>=0, (2)

где y=(y₁, y₂,… y_m), A' транспонированная матрица.

Теорема двойственности. Если прямая и двойственные задачи (1) и (2) имеют допустимые решения, то обе они имеют решения x* и y* и эти решения удовлетворяют условию (с, x*)=(b, y*) т.е. значения исходной и двойственной задачи совпадают.

Отметим, что оптимальное решение двойственной задачи (2) y* совпадает с вектором двойственных (теневых) оценок задачи (1).

Примеры моделирования и решения задач линейного программирования.

Пример 1. Оптимальное распределение финансовых средств, отпускаемых на рекламу (задача о рекламе).

5xr+100xt

-xr+2xt

xr>=0, xt>=0

найти такие количества используемых минут xr и xt в радио - и телесети соответственно, которые реализуют максимальную величину общего объёма сбыта в линейной функции цели:

xr+25xt мах.

В следующей таблице пакета EXCEL [3-4] введём матрицу (массив B5:C6), вектора ограничений (массив D5:D6), вектора коэффициентов целевой функции (массив B4:B5) и линейные формы задачи о рекламе (массив E4:E6). Формулы для линейных форм заданы ниже. Стрелка означает, что в ячейке E4 набирается формула, которая указана в таблице, а потом эта формула копируется в ячейки E5:E6. Ячейки B3:C3 резервированы для переменных задачи (изменяемые ячейки).

Таблица 1.

Формулы таблицы:

Отметим, что для формирования блока ограничений поставленной задачи необходимо нажать кнопку "Добавить". Открывается диалоговое окно "Добавление ограничение", где сформируются соответствующие ограничения задачи. На рисунке 2 формированы ограничения на линейные формы.

Нажмите на кнопку "Добавить", чтобы, не возвращаясь в окно диалога "Поиск решения", наложить новое условие на поиск решения задачи. А именно B3:C3>=0. Если формируются последние ограничения задачи, необходимо нажать кнопку "ОК".

Чтобы изменить, или удалить ограничение необходимо выделить её, а потом нажать на соответствующую кнопку "Изменить" или "Удалить" в окне "Поиск решения".

Далее компьютеру необходимо указать, что решается задача линейного программирования. Для этого нажмите кнопку "Параметры" диалогового окна "Поиск решения". В диалоговом окне "Параметры поиска решения" установите флажок "Линейная модель" и нажмите кнопку "ОК".

Для получения более подробную информацию о диалоговых окнах нажмите кнопку "Справка".

Наконец компьютерная модель задачи готова. С помощью кнопки "Выполнить" диалогового окна "Поиск решения" запустите процесс поиска решения. После завершение этого процесса появится диалоговое окно "Результаты поиска решения":

Для выдачи ещё и отчетов, выделяем соответствующие отчеты и нажимаем кнопку "ОК".

На листе Excel, где формировали задачу, получаем решение задачи:

Таблица 2.

На отдельных листах Excel получаем каждого из этих трёх отчетов.

Из таблиц 2 и 3 получаем, что оптимальное распределение финансовых средств достигается тогда, когда ежемесячно используется 18,2 минут радиорекламы, 9,1 минут телерекламы. При этом достигается максимальный объём - 245,45 единиц сбыта. Все деньги отпускаемые фирмой на рекламу использованы (ограничение E6

Таблица 4.

В нашем примере, например коэффициента 25 переменного xt, в целевой функции, можно изменить в интервале [5,). При этом будет выгодно останавливаться на прежнем решении, т.е. использовать теле- и радиорекламы одновременно (хотя и другими оптимальными значениями). Далее, если затраты на рекламу в бюджете фирмы были на 1 доллар больше, т.е. были 1001 долларов, то это дало бы 0,245 единиц дополнительного сбыта в оптимальном решении. Правый часть ограничения на строке затраты можно изменить в интервале [1000, ). При этом будет выгодно останавливаться на прежнем решении, т.е. использовать теле- и радиорекламы одновременно (хотя и другими оптимальными значениями).

Таблица 5.

В нашем примере, например число 0 является наименьшим значением ячейки С3 (переменного xt), которое совместно со значением ячейки В3 (переменного xr) равное 18,1818 удовлетворяют все ограничения. При этом значение целевой функции (целевой результат) равно 18,18182.

1.2. Моделирование и решение транспортной задачи.

Краткое сведение о транспортной задачи

В этой задаче (3) имеет смысл требования минимизации суммарной стоимости перевозок, а условия (4) и (5)-соответственно ограничений на количество продукта, которое может быть вывезено от каждого производителя и ограничений на потребление этого продукта каждым потребителем.

Транспортная задача имеет решение в том и только в том случае, когда выполняется условие

(7)

Если имеет место равенство

то модель называется сбалансированной моделью и имеет следующий вид

Транспортную модель всегда можно сбалансировать. Если спрос превышает объём производства, можно ввести дополнительный фиктивный исходный пункт с производительностью . Количество продукции, "отправляемой" фиктивным заводом в пункт назначения, будет объём недостающей продукции в этом пункте. , или равен штрафу за единицу продукции, недополученную в соответствующем пункте назначении. Если же , то вводится фиктивный пункт назначения со спросом . Продукции, поступающие с некоторого исходного пункта в фиктивный пункт назначения, представляют избыток производства на этом заводе. Соответствующая стоимость перевозки равно нулю или штрафу за хранение продукции на складе завода.

Многопродуктовая модель изменяется следующим образом. Вместо того, чтобы каждый завод рассматривать как один исходный пункт, разбивается он на несколько исходных пунктов в соответствии с числом выпускаемом им продуктом. Считается, что каждый пункт назначения состоит из пунктов назначения равной количеству всех продуктов.

Запрещенным маршрутам соответствует очень высокая стоимость перевозки.

Пример 2. Задача об оптимальном плане перевозки муки

С=.

Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.

Экономико-математическая постановка задачи. Обозначим через x_ij количество муки, поставляемой хлебокомбинатом P_i хлебозаводу G_j (i=1, 2, 3, j=1, 2, 3, 4). Вектор объёма производства муки в хлебокомбинатах равен (a₁, a₂, a₃)=(110, 190, 90), а вектор объёма спроса хлебокомбинатов на муку равен (b₁, b₂, b₃, b₄)=(80, 60, 170, 80). Общий объём муки, поставляемой хлебокомбинатом P₁ хлебозаводам G_j, j=1, 2, 3, 4 удовлетворяет неравенство x₁₁ + x₁₂ + x₁₃ + x₁₄ 2, P₃ верны неравенства x₂₁ + x₂₂ + x₂₃ + x₂₄ 31 + x₃₂ + x₃₃ + x₃₄ 11 + x₂₁ + x₃₁12 + x₂₂ + x₃₂>=60, x₁₃ + x₂₃ + x₃₃>=170, x₁₄ + x₂₄ + x₃₄>=80. Суммарная стоимость перевозок вычисляется линейной формой 8x₁₁ + x₁₂ + 9x₁₃ + 7x₁₄ + 4x₂₁ + 6x₂₂ + 2x₂₃ + 12x₂₄ + 3x₃₁ + 5x₃₂ + 8x₃₃ + 9x₃₄ .

Экономико-математическая формулировка и модель задачи. =390, т.е. спрос равен предложению и задача является сбалансированной транспортной задачей. Поэтому экономико-математическую модель задачи можно формулировать следующим образом

min (8x₁₁+x₁₂+9x₁₃+7x₁₄+4x₂₁+6x₂₂+2x₂₃+12x₂₄+3x₃₁+5x₃₂+8x₃₃+9x₃₄)

x₁₁ + x₁₂ + x₁₃ + x₁₄=110,

x₂₁ + x₂₂ + x₂₃ + x₂₄=190,

x₃₁ + x₃₂ + x₃₃ + x₃₄=90,

x₁₁ + x₂₁ + x₃₁=80,

x₁₂ + x₂₂ + x₃₂=60,

x₁₃ + x₂₃ + x₃₃=170,

x₁₄ + x₂₄ + x₃₄=80,

x_ij>=0, i=1, 2, 3, j=1, 2, 3, 4.

В следующей таблице введём матрицу затрат перевозок муки (ячейки С9:F11), предложения муки в хлебокомбинатах (ячейки B9:B11), спрос на муку в хлебозаводах (ячейки C7:F7):

Таблица 6.

Формулы таблицы:

В меню Сервис выполняем команду Поиск решения. Так как значения ячеек C13 и F13 совпадают, то спрос равен предложению. Тогда в окне "Поиск решения" мы должны моделировать сбалансированную транспортную задачу, которого должен решать компьютер:

После запуска процесса поиска решения на листе 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 рублей.

1.3. Моделирование и решение задачи о назначениях

(каждый механизм назначается на одну работу) и

(на каждую работу назначен один механизм). Суммарная производительность при данном варианте назначения машин на работы выразится суммой:

Таким образом, математическая модель нашей задачи будет такой:

max; (13)

, (14)

; (15)

(16)

Задачи математического программирования, в которых на переменные наложены условия (16), называются задачами с булевыми переменными. Однако, если в задаче (13)-(16) условия (16) заменить просто условием неотрицательности и целочисленности переменных, т.е. условиями

то задача (13)-(16) превращается целочисленной транспортной задачи (13)-(15), (17) и они эквивалентны.

Пример 3. Задача о назначениях

В следующей таблице введём матрицу эффективностей в ячейки С11:G15, целевую функцию в ячейке B16, линейных форм задачи в ячейки B3:B7 и С8:G8:

Таблица 8.

Формулы таблицы:

Рис.7. Диалоговое окно "Поиск решения".

Экономическая интерпретация полученных результатов и формулировка рекомендаций для принятия решений.

После запуска процесса поиска решения на листе Excel, где формировали задачу, получаем решение задачи:

Таблица 9.

Получаем, что оптимальный план назначений: x14= x23= x31= x45= x52=1, остальные xij=0, т.е. первый механизм назначается на четвёртую работу, второй - на третью, третий - на первую, четвёртый - на пятую, пятый - на вторую. При этом максимальная суммарная производительность равна 17 единиц.

1.4. Моделирование и решение задач в конфликтных ситуациях (матричные игры).

Краткое сведение о матричных играх

Процесс разыгрывания конечной антагонистической игры состоит в том, что игроки 1 и 2, независима друг от друга, выбирают соответственно некоторые чистые стратегии x и y , в результате чего складывается ситуация (х,у). После этого игрок 1 получает выигрыш f(х,у). Игрок 2 столько же проигрывает. Функцию -f называют функцией выигрыша игрока 2.

Можно полагать, что Х={1,2,…,m} и Y={1,2,…,n} (здесь m и n - соответственно число чистых стратегий игроков 1 и 2). Тогда значения функции f представим в виде матрицы A=(a _ij), a _ij=f(i,j), 1

Матрица А называется матрицей выигрышей, игра называется матричной, выбор игроком 1 (2) стратегии i (j) означает выбор строки i (столбца j). Выигрыш игрока 1 будет при этом равен a _ij.

Принципы оптимальности. Если игрок 1 выбирает стратегию x⁰X, то игрок 2 может выбирать такую стратегию yY, при которой выигрыш игрока 1 будет равен

. Поэтому игрок 1 будет склонен выбрать свою стратегию x⁰ так, чтобы этот минимальный выигрыш был наибольшим, т.е. равным

==v₁(Г).

Величину v₁(Г) будем называть нижним значением игры Г, а x⁰ - максиминной чистой стратегией игрока 1.

Аналогично стратегия ==v₂(Г), называется минимаксной стратегией игрока 2, а v₂(Г) - верхним значением игры Г.

Придерживаясь стратегию x⁰, игрок 1 поступает очень осторожно: он желает получить v₁(Г) независимо от действий игрока 2. Принцип это называется принципом максимина.

Элемент называется седловым элементом матрицы выигрыша А, если он удовлетворяет условий , т.е. он является самым маленьким в своей строке и самым большим в своем столбце.

Если v₁(Г)=v₂(Г)=v, то v называется значением матричной игры.

Не все матричные игры имеют седловую точку. Каков наилучший выбор игрока в таких случаях? Ответ состоит в том, что стратегия должна выбираться случайно.

Определение. Распределение вероятностей на множестве чистых стратегий игрока называется его смешанной стратегией.

В случае, когда игрок имеет только конечное число m чистых стратегий, смешанная стратегия представляет собой вектор x=(x₁, x₂,…, x_m), удовлетворяющий условиям: Обозначим множество всех смешанных стратегий игрока 1 через , а множество всех смешанных стратегий игрока 2 через Если игрок 1 выбирает хХ, а игрок 2 уУ, то ожидаемый выигрыш будет равен A(x,y)= =, где y' вектор столбец. Обозначим v₁=, v₂=, где А_.j - j-й столбец, А_i.- i-ая строка матрицы А. Стратегия х: v₁=, - называется максиминной стратегией игрока 1, а стратегия y: v₂=, минимаксной стратегией игрока 2. v₁, v₂ - называются значениями игры для игроков 1 и 2 соответственно.

Эта теорема показывает, что каждая матричная игра имеет решение в смешанных стратегиях. v=v₁ = v₂ - называется значением игры.

Сведение матричной игры к задаче линейного программирования.

max z (18)

при условиях (19)

(20)

(21)

и двойственной ей задачи

min w (22)

при условиях (23)

а решения этих задач линейного программирования x^*, y^* являются соответственно оптимальными стратегиями игроков 1 и 2.

Пример 4. Рациональная организация товароснабжения при неопределенности покупательского спроса

Таблица 10.

A==,

и будет теоретико-игровой моделью рассматриваемого конфликта.

Компьютерная модель и решение задачи. На компьютере будем решать эквивалентные этой игры задач (18) - (21) и (22) - (25). Как отмечали в пункте 1.1, оптимальное решение двойственной задачи (22) - (25) y* совпадает с вектором двойственных (теневых) оценок задачи (18) - (21), а оптимальные значения целевых функций совпадают. Поэтому будем решать задачу (18) - (21), а вместо того, чтобы решить задачу (22) - (25) будем выводить лишь "Отчет по устойчивости" для задачи (18) - (21), где выдаются теневые оценки задачи (18) - (21).

Матрицу задачи (18) - (21) для примера 6 будем вводить в ячейках E2:J7 следующей таблицы:

Таблица 11

Формулы и комментарии для таблицы 11 даны в таблице 12.

Таблица 12.

Рис.8. Диалоговое окно "Поиск решения".

С помощью кнопки "Выполнить" диалогового окна "Поиск решения" запустим процесс поиска решения. После завершение этого процесса появится диалоговое окно "Результаты поиска решения", где в поле тип отчета отмечаем "Устойчивость" и нажимаем кнопку "ОК".

На листе Excel, где формировали задачу, получаем решение задачи:

Таблица 13

На отдельном листе получаем "Отчет по устойчивости", часть которого здесь приводим:

Из таблицы 14 делаем вывод, что оптимальная стратегия для второго игрока равна у^*=(0,317; 0,251; 0,166; 0,147; 0,12), т.е. равна вектору теневых цен ограничений для ячеек E9:I9. Отметим, что y* является и решением двойственной задачи (22) - (25).