Модифицированный симплексный метод решения задач целевого программирования

Рассмотрим метод решения задачи ЦП, использующий идеи симплексного метода. Основная особенность задач ЦП заключается в конструкции целевой функции и в переменных, которые показывают отклонения от желаемого уровня достижения целей. Если учесть эти особенности, то для решения таких задач может быть применён обычный симплексный метод. Проиллюстрируем это на рассмотренном ранее примере. Алгоритм в некоторой степени упрощается из-за того, что исходное базисное решение здесь очевидно. Роль базисных переменных для начального плана здесь играют отрицательные отклонения «d », которые включены в модель с коэффициентами +1. Сложнее со строкой для коэффициентов целевой функции, т.е. с оценочной строкой. Как мы знаем, коэффициентами для отклонений в целевой функции задачи ЦП служат веса, ранжирующие цели по приоритетам. Их численные значения, как правило, не определены. Важно, чтобы коэффициент при отклонении для целевого ограничения с более высоким приоритетом был бы значимо больше коэффициента при отклонении от цели с более низким приоритетом. Поэтому для удобства расчетов оценочная строка разбивается на несколько строк (по числу приоритетов), и вычисления ведутся по каждой строке в отдельности.

Итак, пусть решается задача min Z = P₁d₁^- + P₂d₂^- + P₃d₃⁺ + P₄d₄ ^-,

при условии, что

7x₁ + 6x₂ + d₁^- – d₁⁺ = 30;

2x₁ + 3x₂ + d₂^- – d₂⁺ = 12;

6x₁ + 5x₂ + d₃^- – d₃⁺ = 30;

x₂ + d₄ ^- – d₄⁺ = 7;

x₁, x₂, d_i^-, d_i⁺ ³ 0 (i = ).

Составим исходную симплексную таблицу (таблица 5.1.)

Таблица 5.1 – Исходная симплексная таблица

Cj CB

Базис

Реше-ние

0 x1

0 x2

P1 d1-

P2 d2-

d3-

P4 d4-

d1+

d2+

P3 d3+

d4+

q

P1 P2 P4

d1- d2- d3- d4-

7

-1

-1

-1

-1

30/7 30/6 -

Zj– Сj

P4 P3 P2 P1

-1

-1

-1

-1

Как известно, элементы оценочной строки (Z_j – C_j) рассчитываются по правилу: «от суммы произведений элементов столбца «С_в» на элементы соответствующего столбца отнимается элемент верхней строки». Например, для столбца «решение» элемент «Z_j – C_j» равен: Р₁ *30 + Р₂ *12 + 0* 30 + р₄ *7 – 0 = 30Р₁ + 12Р₂ + 7Р₄ и коэффициенты при соответствующих P_i (i = ) выписаны в этом столбце в блоке «Z_j – C_j» (читать снизу вверх). Для столбца «х₁»: Р₁ *7 + Р₂ *2 + 0 * 6 + Р₄ *0 – 0 = 7Р₁ + 2Р₂, а это и есть коэффициенты при Р₁ и Р₂ в блоке «Z_j – C_j» и т.д.

Поскольку задача ЦП всегда решается на минимум, то решение будет оптимальным, если все элементы оценочной строки будут не положительны. В нашем случае две оценки (в столбцах «х₁» и «х₂») положительны, следовательно, план не оптимальный. Для определения переменной, входящей в базис, на первой итерации определяем наибольшую положительную оценку. Определяется она по знаку коэффициента при Р₁, т.к. P₁ >> P₂ >> P₃ >> P₄. При равных коэффициентах при Р₁, «поднимаемся» на строку выше и выбираем наибольший коэффициент там. В случае полного равенства по всем строкам – выбирается любой из них. В нашем случае разрешающим столбцом будет столбец «х₁» (т.к. 7 > 6). Разрешающая строка выбирается так же как и в симплексном методе – по наименьшему симплексному отношению q (элементы столбца «решение» делим на положительные элементы разрешающего столбца). В таблице 5.1 наименьшее отношение q находится в первой строке. Итак, на следующей итерации в базис вводится переменная «х₁», выводится «d₁^-». Пересчитываем таблицу как в обычном симплекс-методе (таблица 5.2.)

Таблица 5.2 – Вторая симплексная таблица

Как видим, на второй итерации из базиса выводится d₂^-, в базис вводится х₂. И т.д., пока не получим оптимальное решение. После 4-й итерации получим таблицу 5.3.

Таблица 5.3 – Итоговая симплексная таблица

Тот факт, что в строке при P₄ имеется положительный элемент (в столбце d₃⁺) означает, что четвёртая цель выполнена не полностью. При этом, целевая функция равна Р₄, это минимально возможное её значение. В целом оценка переменной d₃⁺ равна (0,2 Р₄ – Р₃), и поскольку Р₃ >> Р₄, то в итоге она отрицательна. Все остальные оценки неположительны, следовательно, план с точки зрения симплексного метода оптимален.

Решение этой задачи можно прокомментировать следующим образом. Для выполнения поставленной задачи необходимо выпустить вторую продукцию в объёме 6 ед. (х₂ = 6). Первую продукцию не выпускать. При этом первая и вторая цели перевыполнены на 6 ед. (d₁⁺ = d₂⁺ = 6), а четвёртая недовыполнена на 1ед. (d₄^- =1). Таким образом, прибыли получили на 6 ед. больше желаемого уровня, первый ресурс использован сверх нормального лимита на 6 ед., а продукцию 2-го вида выпустить в желаемом объёме не получилось – вместо 7 ед. выпустили 6 (не хватило 2-го ресурса; его «экономия» – цель более высокого приоритета).

В заключение в качестве примера составления модели задачи ЦП составим модель ещё одной задачи.

Пример 5.2. Администрация города планирует расширить спортивную базу. На эти цели в городском бюджете выделено 5,4 млн руб. Было запланировано дополнительно построить четыре типа спортивных сооружений: теннисные корты, плавательные бассейны, микростадионы (атлетические площадки) и гимнастические залы. Данные относительно этих проектов следующие (таблица 5.4).

Таблица 5.4 – Информация о строящихся объектах

Решение. В городе для этих целей выделено 20 га свободных площадей, но при необходимости эта площадь может быть увеличена. При реализации этого проекта администрация ставит следующие цели в порядке их важности:

1) уложиться в отведённую бюджетом сумму;

2) построенные спортивные сооружения должны обеспечить не менее 14 000 посещений в неделю;

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

4) при осуществлении проекта по возможности не занимать более отведённого свободного пространства в 20 га.

При составлении модели этой задачи будем иметь в виду, что ограничения при формулировке целей не категоричные и могут быть как пере-, так и недовыполнены.

Переменные задачи: х₁, х₂, х₃, х₄ – соответственно количество построенных сооружений: теннисных кортов, плавательных бассейнов, атлетических площадок и гимнастических залов.

Все ограничения будут целевыми, системных ограничений нет.

Первая цель – уложиться в отведённую сумму:

120х₁ + 600х₂ + 480х₃ + 1 200х₄ + d₁ ^- – d₁⁺ = 5 400.

Минимизируем «перерасход»: min Z = P₁ d₁⁺.

Вторая цель – не менее 14 000 посещений в неделю:

500 x₁ + 1 000x₂ + 2 000x₃ + 1 500x₄ + d₂ ^- – d₂⁺ = 14 000

Минимизируем «недопосещения». С учётом первой цели имеем:

min Z = P₁d₁⁺ + P₂d₂ ^-.

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

x₁ + d₃^-– d₃⁺ = 8;

x₂ + d₄^-– d₄⁺ = 3;

x₃ + d₅^-– d₅⁺ = 3;

x₄ + d₆^-– d₆⁺ = 2.

Минимизируем «недовыполнение». Это третья по важности цель, поэтому в целевой функции все 4 слагаемых будут иметь коэффициент Р₃, но с разными весами:

min Z = P₁d₁⁺ + P₂d₂^- + 0,5P₃d₃^- + P₃d₄^- + 2P₃d₅^- + 1,5P₃d₆^-_.

Четвёртая цель: 0,8x₁ + 5x₂ + 3,2x₃ + 1,6x₄ + d₇^- – d₇⁺ = 20.

Целевая функция с учётом всех целей:

min Z = P₁d₁⁺ + P₂d₂^- + 0,5P₃d₃^- + P₃d₄^- + 2P₃d₅^- + 1,5P₃d₆^- + P₄d₇⁺.

Итак, модель задачи примет вид:

Найти min Z = P₁d₁⁺ + P₂d₂^- + 0,5P₃d₃^- + P₃d₄^- + 2P₃d₅ ^- + 1,5P₃d₆^- + P₄d₇⁺

при условии, что

120x₁ + 600x₂ + 480x₃ + 1200x₄ + d₁ ^- – d₁⁺ = 5 400,

500x₁ + 1 000x₂ + 2 000x₃ + 1 500x₄ + d₂ ^- – d₂⁺ = 14 000,

x₁ + d₃ ^- – d₃⁺ = 8,

x₂ + d₄ ^- – d₄⁺ = 3,

x₃ + d₅ ^- – d₅⁺ = 3,

x₄ + d₆ ^- – d₆⁺ = 2,

0,8x₁ + 2x₂ + 3,2x₃ + 1,6x₄ + d₇ ^- – d₇⁺ = 20.

x_j ³ 0 (j = ); d_i ^-, d_i⁺ ³ 0 (i = ).

Если эту задачу решать обычным симплексным методом, то весам P_i надо придавать конкретные значения, но учитывать, что P₁ >> P₂ >>…>> P₇. Разработаны специальные программы для решения таких задач. Реализуя одну из них (программа QM for Window), получим следующее оптимальное решение (таблица 5.5):

Таблица 5.5 – Решение задачи из примера 5.2.

(Целевое программирование)

x₁ = 8, x₂ = 3, x₃ = 3, x₄ = 1, d₂⁺ = 500, d₆^- = 1, d₇⁺ = 3,6. (d₇⁺ = –653 994 – это закодированное число 3,6 – оно указано в строке Priority 4). Указанное недовыполнение (Nonachievement) в строке Priority 3, равное 1,5 – это с учётом весового коэффициента в целевой функции при ).

Итак, на выделенные средства можно построить 8 теннисных кортов, 3 плавательных бассейна, 3 министадиона и один гимнастический зал. Как видим, четвёртая цель недовыполнена на 1 (d = 1), т.е. вместо двух запланированных будет построен один гимнастический зал. Вторая цель перевыполнена (d₂⁺ = 500), т.е. вместо 14 000 посещений возможны 14 500. Перевыполнена так же 4-я цель (d₇⁺ = 3,6), т.е. вместо отведённых 20 га под эти спортивные сооружения потребуется 23,6 га.

Глава 6. Методы сетевого планирования и управления

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

Анализ любого проекта осуществляется в три этапа:

1. Расчленение проекта на ряд отдельных работ (или операций), из которых затем составляется логическая схема.

2. Оценка продолжительности выполнения каждой операции; составление календарного плана выполнения проекта и выделение работ, которые определяют завершение выполнения проекта в целом.

3. Оценка потребностей каждой операции в ресурсах; пересмотр плана выполнения операций с учётом обеспечения ресурсами либо
перераспределение денежных или других ресурсов, которое улучшит план.

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