Модифицированный симплексный метод решения задач целевого программирования.
Рассмотрим метод решения задачи ЦП, использующий идеи симплексного метода. Основная особенность задач ЦП заключается в конструкции целевой функции и в переменных, которые показывают отклонения от желаемого уровня достижения целей. Если учесть эти особенности, то для решения таких задач может быть применён обычный симплексный метод. Проиллюстрируем это на рассмотренном ранее примере. Алгоритм в некоторой степени упрощается из-за того, что исходное базисное решение здесь очевидно. Роль базисных переменных для начального плана здесь играют отрицательные отклонения «d », которые включены в модель с коэффициентами +1. Сложнее со строкой для коэффициентов целевой функции, т.е. с оценочной строкой. Как мы знаем, коэффициентами для отклонений в целевой функции задачи ЦП служат веса, ранжирующие цели по приоритетам. Их численные значения, как правило, не определены. Важно, чтобы коэффициент при отклонении для целевого ограничения с более высоким приоритетом был бы значимо больше коэффициента при отклонении от цели с более низким приоритетом. Поэтому для удобства расчетов оценочная строка разбивается на несколько строк (по числу приоритетов), и вычисления ведутся по каждой строке в отдельности.
Итак, пусть решается задача min Z = P 1 d 1 - + P 2 d 2 - + P 3 d 3 + + P 4 d 4 - ,
при условии, что
7x 1 + 6x 2 + d 1 - – d 1 + = 30;
2x 1 + 3x 2 + d 2 - – d 2 + = 12;
6x 1 + 5x 2 + d 3 - – d 3 + = 30;
x 2 + d 4 - – d 4 + = 7;
x 1 , x 2 , d i - , d i + ³ 0 (i = ).
Составим исходную симплексную таблицу (таблица 5.1.)
Таблица 5.1 – Исходная симплексная таблица
| C j C B | Базис | Реше-ние | 0 x 1 | 0 x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d 1 + | d 2 + | P 3 d 3 + | d 4 + | q |
| P 1 P 2 P 4 | d 1 - d 2 - d 3 - d 4 - | 7 | -1 | -1 | -1 | -1 | 30/7 30/6 - | ||||||
| Z j – С j | P 4 P 3 P 2 P 1 | -1 | -1 | -1 | -1 |
Как известно, элементы оценочной строки (Z j – C j) рассчитываются по правилу: «от суммы произведений элементов столбца «С в » на элементы соответствующего столбца отнимается элемент верхней строки». Например, для столбца «решение» элемент «Z j – C j » равен: Р 1 *30 + Р 2 *12 + 0* 30 + р 4 *7 – 0 = 30Р 1 + 12Р 2 + 7Р 4 и коэффициенты при соответствующих P i (i = ) выписаны в этом столбце в блоке «Z j – C j » (читать снизу вверх). Для столбца «х 1 »: Р 1 *7 + Р 2 *2 + 0 * 6 + Р 4 *0 – 0 = 7Р 1 + 2Р 2 , а это и есть коэффициенты при Р 1 и Р 2 в блоке «Z j – C j » и т.д.
Поскольку задача ЦП всегда решается на минимум, то решение будет оптимальным, если все элементы оценочной строки будут не положительны. В нашем случае две оценки (в столбцах «х 1 » и «х 2 ») положительны, следовательно, план не оптимальный. Для определения переменной, входящей в базис, на первой итерации определяем наибольшую положительную оценку. Определяется она по знаку коэффициента при Р 1 , т.к. P 1 >> P 2 >> P 3 >> P 4 . При равных коэффициентах при Р 1 , «поднимаемся» на строку выше и выбираем наибольший коэффициент там. В случае полного равенства по всем строкам – выбирается любой из них. В нашем случае разрешающим столбцом будет столбец «х 1 » (т.к. 7 > 6). Разрешающая строка выбирается так же как и в симплексном методе – по наименьшему симплексному отношению q (элементы столбца «решение» делим на положительные элементы разрешающего столбца). В таблице 5.1 наименьшее отношение q находится в первой строке. Итак, на следующей итерации в базис вводится переменная «х 1 », выводится «d 1 - ». Пересчитываем таблицу как в обычном симплекс-методе (таблица 5.2.)
Таблица 5.2 – Вторая симплексная таблица
| C j C B | Базис | Решение | x 1 | x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d 1 + | d 2 + | P 3 d 3 + | d 4 + | q |
| P 2 P 4 | x 1 d 2 - d 3 - d 4 - | 30/7 24/7 30/7 | 6/7 9/7 1/7 | 1/7 2/7 6/7 | 1/7 2/7 6/7 | -1 | -1 | -1 | 30/6 24/9 - | ||||
| Z j – C j | P 4 P 3 P 2 P 1 | 24/7 | 9/7 | 2/7 -1 | 2/7 | -1 | -1 | -1 |
Как видим, на второй итерации из базиса выводится d 2 - , в базис вводится х 2 . И т.д., пока не получим оптимальное решение. После 4-й итерации получим таблицу 5.3.
Таблица 5.3 – Итоговая симплексная таблица
| C j C B | Базис | Реше-ние | x 1 | x 2 | P 1 d 1 - | P 2 d 2 - | d 3 - | P 4 d 4 - | d 1 + | d 2 + | P 3 d 3 + | d 4 + |
| P 4 | d 2 + x 2 d 1 + d 4 - | 1,6 1,2 0,2 -1,2 | -1 | -1 | 0,6 0,2 1,2 -0,2 | -0,6 -0,2 -1,2 0,2 | -1 | |||||
| Z j – C j | P 4 P 3 P 2 P 1 | -1,2 | -1 | -1 | -0,2 | 0,2 -1 | -1 |
Тот факт, что в строке при P 4 имеется положительный элемент (в столбце d 3 +) означает, что четвёртая цель выполнена не полностью. При этом, целевая функция равна Р 4 , это минимально возможное её значение. В целом оценка переменной d 3 + равна (0,2 Р 4 – Р 3), и поскольку Р 3 >> Р 4 , то в итоге она отрицательна. Все остальные оценки неположительны, следовательно, план с точки зрения симплексного метода оптимален.
Решение этой задачи можно прокомментировать следующим образом. Для выполнения поставленной задачи необходимо выпустить вторую продукцию в объёме 6 ед. (х 2 = 6). Первую продукцию не выпускать. При этом первая и вторая цели перевыполнены на 6 ед. (d 1 + = d 2 + = 6), а четвёртая недовыполнена на 1ед. (d 4 - =1). Таким образом, прибыли получили на 6 ед. больше желаемого уровня, первый ресурс использован сверх нормального лимита на 6 ед., а продукцию 2-го вида выпустить в желаемом объёме не получилось – вместо 7 ед. выпустили 6 (не хватило 2-го ресурса; его «экономия» – цель более высокого приоритета).
В заключение в качестве примера составления модели задачи ЦП составим модель ещё одной задачи.
Пример 5.2 . Администрация города планирует расширить спортивную базу. На эти цели в городском бюджете выделено 5,4 млн руб. Было запланировано дополнительно построить четыре типа спортивных сооружений: теннисные корты, плавательные бассейны, микростадионы (атлетические площадки) и гимнастические залы. Данные относительно этих проектов следующие (таблица 5.4).
Таблица 5.4 – Информация о строящихся объектах
Решение. В городе для этих целей выделено 20 га свободных площадей, но при необходимости эта площадь может быть увеличена. При реализации этого проекта администрация ставит следующие цели в порядке их важности:
1) уложиться в отведённую бюджетом сумму;
2) построенные спортивные сооружения должны обеспечить не менее 14 000 посещений в неделю;
3) по возможности удовлетворить ожидаемый спрос на спортивные сооружения. При формировании целевой функции для этих целевых ограничений использовать веса, пропорциональные ожидаемому использованию;
4) при осуществлении проекта по возможности не занимать более отведённого свободного пространства в 20 га.
При составлении модели этой задачи будем иметь в виду, что ограничения при формулировке целей не категоричные и могут быть как пере-, так и недовыполнены.
Переменные задачи: х 1 , х 2 , х 3 , х 4 – соответственно количество построенных сооружений: теннисных кортов, плавательных бассейнов, атлетических площадок и гимнастических залов.
Все ограничения будут целевыми, системных ограничений нет.
Первая цель – уложиться в отведённую сумму:
120х 1 + 600х 2 + 480х 3 + 1 200х 4 + d 1 - – d 1 + = 5 400 .
Минимизируем «перерасход»: min Z = P 1 d 1 + .
Вторая цель – не менее 14 000 посещений в неделю:
500 x 1 + 1 000x 2 + 2 000x 3 + 1 500x 4 + d 2 - – d 2 + = 14 000
Минимизируем «недопосещения». С учётом первой цели имеем:
min Z = P 1 d 1 + + P 2 d 2 - .
Реализация третьей цели потребует выполнения 4 ограничений по каждому виду сооружений:
x 1 + d 3 - – d 3 + = 8;
x 2 + d 4 - – d 4 + = 3;
x 3 + d 5 - – d 5 + = 3;
x 4 + d 6 - – d 6 + = 2.
Минимизируем «недовыполнение». Это третья по важности цель, поэтому в целевой функции все 4 слагаемых будут иметь коэффициент Р 3 , но с разными весами:
min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - .
Четвёртая цель: 0,8x 1 + 5x 2 + 3,2x 3 + 1,6x 4 + d 7 - – d 7 + = 20.
Целевая функция с учётом всех целей:
min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - + P 4 d 7 + .
Итак, модель задачи примет вид:
Найти min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - + P 4 d 7 +
при условии, что
120x 1 + 600x 2 + 480x 3 + 1200x 4 + d 1 - – d 1 + = 5 400,
500x 1 + 1 000x 2 + 2 000x 3 + 1 500x 4 + d 2 - – d 2 + = 14 000,
x 1 + d 3 - – d 3 + = 8,
x 2 + d 4 - – d 4 + = 3,
x 3 + d 5 - – d 5 + = 3,
x 4 + d 6 - – d 6 + = 2,
0,8x 1 + 2x 2 + 3,2x 3 + 1,6x 4 + d 7 - – d 7 + = 20.
x j ³ 0 (j = ) ; d i - , d i + ³ 0 (i = ).
Если эту задачу решать обычным симплексным методом, то весам P i надо придавать конкретные значения, но учитывать, что P 1 >> P 2 >>…>> P 7 . Разработаны специальные программы для решения таких задач. Реализуя одну из них (программа QM for Window), получим следующее оптимальное решение (таблица 5.5):
Таблица 5.5 – Решение задачи из примера 5.2.
(Целевое программирование)
x 1 = 8, x 2 = 3, x 3 = 3, x 4 = 1, d 2 + = 500, d 6 - = 1, d 7 + = 3,6. (d 7 + = –653 994 – это закодированное число 3,6 – оно указано в строке Priority 4). Указанное недовыполнение (Nonachievement) в строке Priority 3, равное 1,5 – это с учётом весового коэффициента в целевой функции при ).
Итак, на выделенные средства можно построить 8 теннисных кортов, 3 плавательных бассейна, 3 министадиона и один гимнастический зал. Как видим, четвёртая цель недовыполнена на 1 (d = 1), т.е. вместо двух запланированных будет построен один гимнастический зал. Вторая цель перевыполнена (d 2 + = 500), т.е. вместо 14 000 посещений возможны 14 500. Перевыполнена так же 4-я цель (d 7 + = 3,6), т.е. вместо отведённых 20 га под эти спортивные сооружения потребуется 23,6 га.
Глава 6. Методы сетевого планирования и управления
Методы сетевого планирования позволяют осуществить анализ комплекса работ, который включает в себя большое число взаимосвязанных операций. Можно определить вероятную продолжительность выполнения всех работ, их стоимость, возможные размеры экономии времени или денежных средств, а также то, выполнение каких операций нельзя отсрочить, не задержав при этом срок выполнения проекта в целом. Немаловажным является и проблема обеспечения ресурсами. Методы сетевого анализа могут быть использованы при составлении календарного плана выполнения операций, удовлетворяющего существующим ограничениям на обеспечение ресурсами.
Анализ любого проекта осуществляется в три этапа:
1. Расчленение проекта на ряд отдельных работ (или операций), из которых затем составляется логическая схема.
2. Оценка продолжительности выполнения каждой операции; составление календарного плана выполнения проекта и выделение работ, которые определяют завершение выполнения проекта в целом.
3. Оценка потребностей каждой операции в ресурсах; пересмотр плана выполнения операций с учётом обеспечения ресурсами либо
перераспределение денежных или других ресурсов, которое улучшит план.
После того как составлен список, логическая последовательность выполнения операций может быть проиллюстрировала с помощью графа. Существуют различные типы графов, но наиболее широкое применение получили, так называемые вершинные и стрелочные графы.
Задачей оптимизации в математике называется задача о нахождении экстремума вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.
3.1. Описание
Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом.
Уравнение W(x) = c, где W(x) – максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. При этом экстремальная задача приобретает следующую формулировку: требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.
Сущность симплекс-метода состоит в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяются на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придаются произвольные значения и затем подставляются в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях – несколько оптимальных решений, причем все они обеспечат экстремум целевой функции. Таким образом, если найти какой-то базисный план и затем улучшить его, то получится оптимальное решение. На этом принципе построен симплекс-метод.
Последовательность вычислений симплекс-методом можно разделить на две основные фазы:
1. нахождение исходной вершины множества допустимых решений;
2. последовательный переход от вершины к вершине, ведущий к оптимизации значения целевой функции.
В некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, – например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно есть допустимое решение, хотя, скорее всего, далеко не оптимальное). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод соответственно делится на однофазный и
двухфазный .
3.2. Алгоритм симплекс-метода
Усиленная постановка задачи
Рассмотрим следующую задачу линейного программирования:
Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:
Здесь x – переменные из исходного линейного функционала; x s – новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство; c – коэффициенты исходного линейного функционала; Z – переменная, которую необходимо максимизировать. Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт число степеней свободы. Проще говоря, если рассматривать вершину многогранника, это есть число рёбер, по которым можно продолжать движение.
Тогда можно присвоить такому числу переменных значение 0 и назвать
3. Модифицированный симплекс-метод
В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы.
В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Способность хороша для ситуаций, когда число переменных n значительно превышает число ограничений m.
В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс – разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана – Гаусса. Особенности заключаются в наличии двух таблиц – основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.
Зная оптимальный план этой задачи, на основе соотношений получаем оптимальный план исходной задачи.
Таким образом, процесс нахождения решения задачи нелинейного программирования включает следующие этапы:
1. Первоначальную задачу сводят к задаче линейного программирования.
2. Находят решение линейной задачи
Используя соотношения, определяют оптимальный план исходной задачи и находят максимальное значение целевой функции нелинейной задачи.
Первый этап: Получение задания к курсовой работе
1. Все числовые данные, касающиеся предполагаемых производственных и экономических процессов, берутся на основе шестизначного шифра:
Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде:
из последней строки таблицы индивидуальных заданий находим столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а – том столбце в строке 9, b – том столбце в строке 5, c – том столбце в строке 5, d – том столбце в строке 8, e – том столбце в строке 7и f – том столбце в строке 2.
По таблице исходных заданий для любого варианта заданий по столбцу а исполнитель получает вариант выполняемого задания. В моем случае для цифры 9 соответствует вариант 9.
На некотором заводе производится три вида продукта и при этом расходуется два вида ресурсов. Производственная функция каждого вида продукта на предприятии опишется равенствами:
где С i и - постоянные величины, i = 1, 2, 3;
X 1 – трудовые ресурсы в человеко-днях;
Х 2 – денежно-материальные средства, в тенге;
У i – получаемый продукт
Х 1 = а 1 х 1 + b 1 x 2 + c 1 x 3
Х 2 = а 2 х 1 + b 2 x 2 + c 2 x 3
Найти все неотрицательные базисные решения и определить оптимальный план F = y 1 + y 2 + y 3 .
Известно, что продукт для производства j – того вида затрачивается a ij единиц i – того ресурса. Эти затраты даются в таблицах 3.9.1. – 3.9.10
Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11.
2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица:
| Продукты ресурсы | |||
| I | 8 | 4 | 6 |
| II | 160 | 240 | 200 |
3. По столбцу c – на 3 строке находим с 1 =6, α 1 =0,6
4. По столбцу d – на 5 строке определяем с 2 =5, α 2 =0,5
5. По столбцу e – по 4 строке установим, что с 3 =8, α 3 =0,4.
6. И наконец по столбцу f – в 1 строке найдем Т чел.дней =1000, П тенге = 280000
Для производства имеются трудовые ресурсы Т чел.дней и денежно-материальные средства П тенге.
Требуется найти оптимальный план выпуска продукции, при котором выпускаемый продукт будет наибольшим.
Второй этап – составление математической модели задачи
1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:
| Продукты ресурсы | ||||
| I | 8 | 4 | 6 | 1000 |
| II | 160 | 240 | 200 | 280000 |
Через Х 1 обозначим ресурсы I вида.
Через Х 2 обозначим ресурсы II вида.
2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений.
8Х 1 + 4Х 2 + 6Х 3 ≤ 1000
240Х 1 + 200Х 2 + 160Х 3 ≤ 280000
Таким образом, получили задачу нелинейного программирования. Такие задачи называются задачами нелинейного программирования.
Решение задач нелинейного программирования осуществляется приведением их к задачам линейного программирования.
Для решения задачи линейного программирования применяется симплекс – метод.
Третий этап – выбор метода решения полученной математической задачи
1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:
8Х 1 + 4Х 2 + 6Х 3 + Х 4 = 1000
240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000
Разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями. Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах...
Нахождение точки Куна-Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать при ограничениях С помощью теоремы 2 докажем, что решение является оптимальным. Имеем Так...
Лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...
Положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой...
МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОДСимплекс-метод – не самая эффективная
компьютерная процедура, так как она вычисляет и
хранит информацию, которая не нужна для текущей
итерации и может вообще не использоваться для
принятия решений при последующих итерациях. Для
коэффициентов неосновных переменных в уравнении
(0), коэффициентов введенных основных переменных
в других уравнениях и правых частях уравнений при
каждой итерации используется только релевантная
информация. Поэтому нужна процедура, которая
может получать эту информацию эффективно, без
вычислений и хранения всех других коэффициентов
(это и есть модифицированный симплекс-метод).
необходимую на данный момент, а важные данные
передает в более компактной форме.
Он использует операции с матрицами, поэтому
необходимо описывать задачу используя матрицы.
ЗАГЛАВНЫЕ буквы, выделенные жирным шрифтом
представляют матрицы, прописные буквы,
выделенные жирным шрифтом представляют
векторы.
Курсив – это скалярные величины, выделенный ноль
(0) обозначает нулевой вектор (его элементы равны
нулю, как строки, так и столбцы), ноль (0)
представляет обычное число 0. С использованием
матриц стандартная форма модели линейного
программирования принимает форму:Максимизировать Z = c x,
согласно
A x ≤ b and x ≥ 0,
где c вектор-строка
x, b, и 0 векторы-столбцыA - матрица
Для дополненной формы, вектор-столбец
фиктивных переменных:
Ограничения:
I = (m × m единичная матрица)
0 = (n + m элементы нулевого вектора)Нахождение базового допустимого решения
Общий подход симплекс-метода – получение
последовательности улучшающихся ОД решений до
тех пор, пока не будет найдено оптимальное
решение. Одна из ключевых особенностей
модифицированного симплекс-метода – то, как он
находит новое ОД решение после определения его
основных (базисных) и неосновных (небазисных)
переменных. Имея эти переменные, получающееся
основное решение – решение m уравнений
В котором n небазисных переменных из n + m
элементов
устанавливаются равными нулю.Исключая эти n переменных приравниванием к нулю,
получаем систему уравнений m с m переменными
(основными (базисными) переменными):
где вектор базисных переменных:
получен исключением небазисных (неосновных)
переменных:И базисная матрица
Полученная исключением столбцов, соответствующих
коэффициентам небазисных переменных из .
(В дополнение, элементы xB, и столбцы B в разном
порядке). Симплекс метод вводит только базисные
переменные, такие что B - невырожденная, так что
обратная матрица B-1 всегда будет существовать.
Чтобы решить B x B = b, обе стороны умножаются на B-1:
B-1 B x B = B-1 b.cB – вектор, чьи элементы - коэффициенты
целевых функций (включая нули для фиктивных
переменных) для соответствующих элементов xB.
Целевая функция для этого базисного решения:Пример:
- Итерация 0
so
so
10.
- Итерация 1so
so
11.
- Итерация 2so
so
12. Матричная форма для текущего множества уравнений
Матричная форма для множества уравнений,появляющаяся в симплекс-таблице для любой итерации
исходного симплекс-метода. Для исходной системы
уравнений, матричная форма такая:
Алгебраические операции, выполняемые симплексметодом (умножить уравнение на константу и прибавить
произведение одного уравнения на другое) выражаются в
виде матрицы, предварительно умножив обе части
исходной системы уравнений на соответствующие
матрицы
13.
14.
Эта матрица будет иметь те же элементы, что и единичнаяматрица, за исключением того, что каждое произведение
для определенной алгебраической операции займет
место, необходимое для выполнения этой операции,
используя перемножение матриц. Даже после серии
алгебраических операций в течение нескольких итераций,
мы все еще можем сделать вывод, что эта матрица
должна быть для всей серии, используя то, что мы знаем о
правой стороны новой системы уравнений. После любой
итерации, xB = B-1b и Z = cB B-1b, поэтому правые стороны
новой системы уравнений приняли вид
15.
Так как мы выполняем одни и те же серииалгебраических операций с обеими сторонами
исходного множества, для умножения правой и
левой части, мы используем одну и ту же матрицу.
Следовательно,
Желаемая матричная форма системы уравнений
после любой итерации:
16.
Example: матричная форма, полученная после итерации 2для задачи о стекольном заводе, используя B-1 и cB:
17.
Используя величины xB = B-1 b и Z = cB B-1 b:18.
Только B-1 должна быть получена для вычислениявсех чисел симплекс-таблицы из исходных
параметров задачи (A, b, cB). Любое из этих чисел
может быть получено индивидуально, как
правило, выполняют только векторное умножение
(одна строка на один столбец) вместо полного
матричного умножения. Необходимые числа для
выполнения итераций симплекс-метода можно
получить по мере необходимости, не проводя
ненужные вычисления, чтобы получить все числа.
19. Краткий обзор модифицированного симплекс метода
1. Инициализация: Как в исходном симплекс методе.2. Итерация: Шаг 1 Определить введенные базисные (основные)
переменные: Как в исходном симплекс методе.
Шаг 2 Определить уходящие базисные переменные: Как в исходном
симплекс методе, за исключением подсчета только необходимых для
этого чисел [коэффициенты введенных базисных переменных в
каждом уравнении за исключением Ур. (0), а затем, для каждого строго
положительного коэффициента, правая часть этого уравнения].
Шаг 3 Определить новое ОД решение: Получить B-1 и задать xB=B-1b.
3. Анализ на оптимальность: Как в исходном симплекс методе, за
исключением подсчета только необходимых для этого анализа чисел,
т.е., коэффициентов небазисных (неосновных) переменных в
Уравнении (0).
На шаге 3 итерации, B-1 можно получить каждый раз используя
стандартную компьютерную программу для обращения (инверсии)
матрицы. Так как B (затем B-1) мало изменяется от одной итерации к
другой, более эффективно получать новое B-1 (обозначаем B-1 new) из
B-1 на предыдущей итерации (B-1 old). (Для исходного ОД решения).
Модифицированный симплекс-метод
В модифицированном методе матрица
не пересчитывается, хранится и пересчитывается только матрица. В остальном алгоритм похож на вышеописанный.
1. Вычисляем двойственные переменные
2. Проверка оптимальности. преобразуется в.
Проверка заключается в вычислении для всех столбцов. Столбец со значением < 0 можно вводить в базис.
Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.
Чаще выбирают значение, меньшее некоторого заданного значения
Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и соответствующий столбец вводится в базис.
3. Определение выводимого.
Пусть - вводимый столбец, соответствующий переменной Базиный план - это решение системы Увеличиваем.
Умножим слева на, т.е.
Здесь - базисный план, - разложение вводимого столбца по базису.
Находим максимальное значение, при котором все значения не отрицательны. Если может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса.
4. Пересчет опорного(базисного) плана.
Вычисляем новый опорный план по уже приведенной формуле с найденным значением.
5. Пересчитываем обратную к базисной.
Пусть - выводимый столбец.
Матрица B представима в виде
где - базисная матрица без выводимого столбца.
После замены столбца базисная матрица будет иметь вид
Нам нужно найти матрицу, такую что
Замечание.
При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».
Мультипликативный вариант симплекс-метода
В мультипликативном варианте матрица не хранится, хранятся лишь множители
При решении экономических задач часто матрица ограничений разреженная, в таком случае мультипликативный вариант получает дополнительные преимущества - можно хранить мультипликаторы в сжатом виде (не хранить нули).
Другие варианты симплекс-метода
Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.
При подавляющем числе ограничений типа «неравенство» может быть использован метод переменного базиса .
Метод основан на том, что базисная матрица может быть представлена в виде
Обратная к ней имеет вид
При относительно небольших размерах матрицы остальная часть матрицы может не храниться.
Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).
Двойственный симплекс-метод
Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:
при ограничениях
Теорема двойственности . Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем экстремальные значения линейных функций этих задач равны.
Если линейная функция одной из задач не ограничена, то другая не имеет решения.
Загрузка...
