МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОДСимплекс-метод – не самая эффективная
компьютерная процедура, так как она вычисляет и
хранит информацию, которая не нужна для текущей
итерации и может вообще не использоваться для
принятия решений при последующих итерациях. Для
коэффициентов неосновных переменных в уравнении
(0), коэффициентов введенных основных переменных
в других уравнениях и правых частях уравнений при
каждой итерации используется только релевантная
информация. Поэтому нужна процедура, которая
может получать эту информацию эффективно, без
вычислений и хранения всех других коэффициентов
(это и есть модифицированный симплекс-метод).
Рассмотрим метод решения задачи ЦП, использующий идеи симплексного метода. Основная особенность задач ЦП заключается в конструкции целевой функции и в переменных, которые показывают отклонения от желаемого уровня достижения целей. Если учесть эти особенности, то для решения таких задач может быть применён обычный симплексный метод. Проиллюстрируем это на рассмотренном ранее примере. Алгоритм в некоторой степени упрощается из-за того, что исходное базисное решение здесь очевидно. Роль базисных переменных для начального плана здесь играют отрицательные отклонения «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. Оценка потребностей каждой операции в ресурсах; пересмотр плана выполнения операций с учётом обеспечения ресурсами либо
перераспределение денежных или других ресурсов, которое улучшит план.
После того как составлен список, логическая последовательность выполнения операций может быть проиллюстрировала с помощью графа. Существуют различные типы графов, но наиболее широкое применение получили, так называемые вершинные и стрелочные графы.
Задачей оптимизации в математике называется задача о нахождении экстремума вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.
Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом.
Уравнение W(x) = c, где W(x) – максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. При этом экстремальная задача приобретает следующую формулировку: требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.
Сущность симплекс-метода состоит в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяются на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придаются произвольные значения и затем подставляются в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях – несколько оптимальных решений, причем все они обеспечат экстремум целевой функции. Таким образом, если найти какой-то базисный план и затем улучшить его, то получится оптимальное решение. На этом принципе построен симплекс-метод.
Последовательность вычислений симплекс-методом можно разделить на две основные фазы:
1. нахождение исходной вершины множества допустимых решений;
2. последовательный переход от вершины к вершине, ведущий к оптимизации значения целевой функции.
В некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, – например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно есть допустимое решение, хотя, скорее всего, далеко не оптимальное). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод соответственно делится на однофазный и
двухфазный .
Рассмотрим следующую задачу линейного программирования:
Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:
Здесь x – переменные из исходного линейного функционала; x s – новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство; c – коэффициенты исходного линейного функционала; Z – переменная, которую необходимо максимизировать. Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт число степеней свободы. Проще говоря, если рассматривать вершину многогранника, это есть число рёбер, по которым можно продолжать движение.
Тогда можно присвоить такому числу переменных значение 0 и назвать
Основная идея модифицированного
симплекс-метода заключается в использовании
текущей обратной матрицы
(и исходных данных задачи) при выполнении
вычислений, необходимых для определения
включаемой и исключаемой переменных.
Представление обратной матрицы в
мультипликативной форме позволяет
вычислять последовательность обратных
матриц непосредственно по исходным
данным без использования многократных
операций обращения каждого базиса. Как
и в обычном симплекс-методе, в данном
случае исходный базис всегда представляет
собой единичную матрицуI,
обратной к которой является сама эта
матрица. Поэтому, если
-
последовательность обратных матриц,
соответствующих итерациям 1, 2,…,i,
а
- последовательность соответствующих
им матриц, то
Последовательность подстановок приводит к следующей формуле:
(2.23)
Следует подчеркнуть, что мультипликативное представление обратной матрицы не является необходимой процедурой для реализации вычислительной схемы модифицированного симплекс-метода, и на каждой итерации можно применять любой из способов обращения текущего базиса. При использовании модифицированного симплекс-метода важно то, что обратные матрицы вычисляются способом, позволяющим уменьшить влияние машинных ошибок округления.
Шаги алгоритма модифицированного симплекс-метода, по существу, такие же, как и в алгоритме обычного симплекс-метода. После нахождения начального базиса Iопределяется соответствующий ему вектор коэффициентов целевой функции, элементы которого формируются в зависимости от того, являются ли начальные базисные переменные остаточными (избыточными) или искусственными.
При мультипликативном представлении
обратной матрицы используется операция
алгебры матриц, позволяющая вычислять
элементы матрицы, обратной к новой
матрице базисных векторов, по известной
обратной матрице предыдущего базиса
при условии, что два рассматриваемых
базиса отличаются только одним
вектор-столбцом. Такой способ представления
обратной матрицы удобно использовать
именно в вычислительной схеме
симплекс-метода, так как базисы,
соответствующие каждым двум последовательным
итерациям, отличаются лишь одним столбцом
(в результате замены исключаемого
вектор-столбца текущего базиса новым
вектор-столбцом). Другими словами,
текущая базисная матрица
и новая базисная матрица
,
соответствующая следующей итерации,
отличаются только одним столбцом. При
мультипликативном представлении
обратной матрицы
,
соответствующей новому базису, она
вычисляется путём умножения слева
обратной текущей матрицы
на формируемую по определённым правилам
матрицу.
Определим единичную матрицу следующим образом:
(2.24)
где
- единичный вектор-столбец сi-м
элементом, равным единице, и остальными
элементами, равными нулю. Допустим, что
известны матрицыи
,
и векторматрицызаменяется новым вектором;
как принято при описании симплекс-метода,
векторопределяется как включаемый в базис, а
вектор- как исключаемый из базиса. Для упрощения
записи математических соотношений
используем следующее определение
,при
этомбудет представлять собойk-й
элемент
.
Тогда новую обратную матрицу
можно вычислить по следующей формуле:
(2.25)
при условии, что
.
Если
,
матрицы
не существует. Заметим, что матрицаполучается из матрицыпутём замены еёr-го
вектор-столбцастолбцом.
|
|||||
|
|||||
Суть преобразований симплекс-метода рассмотрим на примере 1.4. Давайте вспомним ограничивающие неравенства и целевую функцию из этого примера и найдем max целевой функции, пользуясь вышеизложенным методом:
F = 908X 1 + 676X 2 ® max.
X 1 + X 2 14,
X 2 10,
10 X 1 + 8 X 2 120,
7X 1 + 5 X 2 70,
4X 1 + 2X 2 28,
|
Преобразуем ее в каноническую форму, вводя дополнительные переменные X j 0, и превратив неравенства в равенства. Следует обратить внимание, что если в неравенстве стоит знак "", то при свободной переменной пишут " - ", в противном случае - " + ":
X 1 + X 2 = 14 - X 3 ,
X 2 = 10 - X 4 ,
10 X 1 + 8 X 2 = 120 - X 5 ,
7X 1 + 5 X 2 = 70 - X 6 ,
4X 1 + 2X 2 = 28 - X 7 .
Чтобы приступить к процедуре симплекс-метода, нужно из множества базисных решений полученной системы уравнений сначала найти опорное. С учетом этого в решении задач симплекс-методом различают три этапа:
Нахождение первоначального базисного решения и формирование исходной симплекс-таблицы;
Определение допустимого решения;
Определение оптимального решения.
1-й этап
Первоначальное базисное решение систем находим, полагая свободными переменные X 1 и X 2 .
Тогда X 3 = 14 - X 1 - X 2 ,
X 4 = 10 - X 2 ,
X 5 =120 - 10X 1 - 8X 2 ,
X 6 = 70 - 10X 1 - 5X 2 ,
X 7 = 28 - 4X 1 - 2X 2 ,
F = 908X 1 + 676X 2 = 0 .
Преобразуем эти уравнения к нормальному виду:
X 3 = 14 - (X 1 + X 2),
X 4 = 10 - (0X 1 + X 2),
X 5 =120 - (10X 1 + 8X 2),
X 6 = 70 - (7X 1 + 5X 2),
X 7 = 10 - (4X 1 + 2X 2),
F = 0 + 908 X 1 + 676 X 2 .
Полученную систему уравнений запишем в виде исходной симплекс-таблицы (табл. 1.9). В табл. 1.9 нет отрицательных свободных членов. Следовательно, нами получено опорное (допустимое) решение, так как допустимым решением является любое неотрицательное решение (при котором > 0 ), но оно не является оптимальным.
Очевидно, что если бы при всех неизвестных в целевой функции F стояли положительные коэффициенты, то было бы достигнуто максимальное значение F . Отсюда вытекает признак оптимальности допустимого решения: в F - строке симплекс-таблицы не должно быть отрицательных коэффициентов.
Таблица 1.9
Базисные переменные X б | Свободный член | Свободные переменные | |
X 1 | X 2 | ||
X 3 | |||
X 4 | |||
X 5 | |||
X 6 | |||
X 7 | |||
F | - 908 | - 676 |
2-й этап
Напомним, что основная операция симплекс-метода состоит по сути в том, что некоторая базисная переменная замещается на свободную переменную . При этом операция замещения выполняется при соблюдении следующих условий:
Значение целевой функции F в новом опорном (допустимом) решении должно быть больше, чем в предыдущем;
Новое решение системы должно быть также опорным (допустимым).
В нашем примере первое условие выполняется, в случае если разрешающий элемент положительный и выбран в столбце отрицательного коэффициента F -строки.
Второе условие выполняется, в случае если разрешающий элемент находится как минимальное положительное отношение элементов столбца свободных членов к соответствующим элементам разрешающего столбца.
По выше изложенному правилу для нахождения допустимого решения меняют местами базисные и свободные переменные. Для этого находят разрешающий элемент (в табл. 1.9 он взят в рамку). В нашем случае разрешающим должна быть как столбец X 1 , так и X 2 . Деля свободные переменные на соответствующие значения X 1 иX 2 (кроме строки F ), находим наименьшее положительное значение. Важно заметить, что для столбца X 1 :
Важно заметить, что для столбца X 2 :
Наименьшее отношение 28/4 определяет разрешающую строку и разрешающий столбец, а пересечение разрешающего столбца и разрешающей строки - разрешающий элемент a ks = 4. В табл. 1.9 разрешающий столбец и разрешающую строку отмечаем стрелками (®). Определивa ks , строят следующую таблицу, в которой меняют местами переменные, входящие в строку и столбец разрешающего элемента͵ ᴛ.ᴇ. переводят базисные переменные в свободные, а свободные - в базисные.
В нашем примере меняем местами переменные Х 7 и Х 1 , отмеченные в табл. 1.9 стрелками. Коэффициенты новой табл. 1.10 находят по коэффициентам старой табл. 1.9, используя выражения, приведенные в табл. 1.8 и “правило прямоугольника”. В табл. 1.10 снова не имеем оптимального решения.
Таблица 1.10
Базисные переменные Х б | Свободный член В | Свободные переменные | |||||||||||
X 7 | X 2 | ||||||||||||
Х 3 | - 1/4 | 1/2 | |||||||||||
Х 4 | |||||||||||||
Х 5 | -5/2 | ||||||||||||
Х 6 | -7/4 | 3/2 | |||||||||||
Х 1 | 1/4 | 1/2 | |||||||||||
F | -222 | ||||||||||||
По вышеописанным правилам в табл. 1.10 находим разрешающий элемент 1 и строим новую табл. 1.11 сделав замещение базиса (Х 4 и Х 2 ). Особо подчеркнем, что для нахождения разрешающего элемента мы должны выбирать наименьшее положительное значение, ᴛ.ᴇ. отрицательные отношения свободных членов к коэффициентам разрешающего столбца мы не рассматриваем.
3-й этап
Проверим, является ли найденное решение оптимальным, а для нашего примера - максимальным. Для этого сделаем анализ целевой функции F : F = 8576 + 227 X 7 + 222 X 4 .
Целевая функция не содержит отрицательных коэффициентов и имеет наибольшее значение в последней таблице, нами получено оптимальное решение:
X 3 = 2; X 2 = 10; X 5 = 20; X 6 = 6; X 1 = 2; X 7 = X 4 = 0;
F max = 8576.
Обратите внимание, что результаты решения симплекс методом и графическим совпадают.
В соответствии с рассмотренной последовательностью, алгоритм симплекс-метода должен иметь следующие блоки:
1. Нахождения первоначального базисного (опорного) решения и формирование исходной таблицы.
2. Отыскание разрешающего элемента a ks (нахождение отрицательного свободного члена - b i < 0 и минимального отношенияb i / a ij ; если в строке отрицательного свободного члена нет отрицательных коэффициентов, то задача неразрешима).
3. Перерасчет новой таблицы по формулам табл. 1.8.
4. Проверка наличия отрицательного свободного члена. В случае если он есть, то переходим к п. 2. Отсутствие отрицательного свободного члена означает, что получено опорное (допустимое) решение.
5. Аналогично п. 2 - 4 выполняется перерасчет таблицы при поиске оптимального решения.
Решение задачи ЛП симплекс-методом в матричной форме
Требуется минимизировать ,
при ограничениях
при "x ³ 0.
Введем векторы:
C = (C 1 , ... , C n) - вектор оценок,
X = (X 1 , ... , X n) - вектор переменных,
b = (B 1 , ... , B m) - вектор ограничений
и матрицу
A =
размером (mn) - матрицу коэффициентов ограничений.
Тогда задача ЛП будет иметь следующую трактовку:
минимизировать F=CX
при условиях AX = b, X 0.
Эту задачу можно записать в матричной форме:
Введем обозначение:
А * = - здесь матрица A * размером (m+1)(n+1).
Согласно выше приведенной методике находят разрешающий элемент a ks .
Следующий шаг симплекс-метода - процедура исключения Гаусса, которая позволяет сделать все коэффициенты в s - м столбце, кроме a ks , нулевыми, a ks - равным единице.
Важно заметить, что для симплекс-метода в матричной форме итерация симплекс-метода эквивалентна умножению матричного уравнения слева на следующую квадратную матрицу:
|
В случае если все столбцы матрицы A разделить на базисные B и небазисные N, то задачу ЛП можно записать так:
,
где C b и C N - соответствующие компоненты вектора C, X b , X N - базисные и небазисные переменные.
Для выбора начальных базисных переменных x b следует умножить уравнение слева на матрицу:
где R= C b B -1 .
В результате получим
,
гдеI - единичная матрица.
Отсюда следует, что относительные оценки при небазисных переменных
c j = c j - C b B -1 a j = c j - Ra j .
Базис будет допустимым, в случае если свободные члены при базисных переменных будут неотрицательными, ᴛ.ᴇ. B -1 b ³ 0.
В случае если c j ³ 0 для , то базис является оптимальным решением задачи. Вектор называют вектором текущих цен. Каждая строка умножается на вектор R и вычитается из строки коэффициентов стоимости, для того чтобы исключить коэффициенты стоимости при базисных переменных.
В случае если задача ЛП задана не в канонической форме, ᴛ.ᴇ.
минимизировать F=CX
при условиях AX b , X 0,
то, вводя слабые переменные, их можно записать в виде
Метод исключения по строкам для матрицы эквивалентен умножению этой матрицы слева на B -1 , где B - базис подматрицы A , тогда
,
ᴛ.ᴇ. матрица, получаемая на месте единичной I , будет матрицей, обратной для текущего базиса. Относительные оценки, расположенные над единичной матрицей, будут
,
поскольку - единичные векторы.
Так как F= C b B -1 b = Rb, текущее значение целевой функции равно произведению вектора текущих цен матрицы A на исходный вектор b .
Пример.
Размещено на реф.рф
F=
5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5
® min
при ограничениях
2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,
3X 2 + 3X 4 + 6X 5 = 9,
|
Для данного примера матрицаA * будет иметь вид
.
Пусть X 1 и X 2 - базисные переменные.
Матрица B имеет вид
.
Тогда обратная матрица B -1 имеет следующий вид
.
Напомним, что , где присоединенная матрица, составленная из алгебраических дополнений элементов b ik определителя матрицы B .
Определитель равен:
= .
Следовательно, матрица B неособенная.
Алгебраические дополнения элементов определителя имеют следующие значения:
b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2 ; т.е. .
Умножив на , находим обратную матрицу:
.
Вектор текущих цен будет
R = C b B -1 = = .
Напомним, что C b - базисные компоненты вектора C :
Тогда = .
Для выбора начального базиса нужно матрицу A * умножить слева на матрицу
=
.
Разрешающий элемент находится в квадрате.
Итерация симплекс-метода эквивалентна полученной таблице, умноженной слева на следующую матрицу:
.
Эта матрица получена из матрицы (1.23)
Здесь a ks = 2 ;
a 11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;
a 13 = 0 ; a 21 = 0 ; a 22 = 1/ a ks = 1/2 ; a 23 = 0;
a 31 = 0 ; a 32 = - a ms / a ks = -1/2 ; a 33 = 1.
Тогда имеем
=
(1.24)
Разрешающий элемент помещен в квадрат.
Следующая итерация симплекс-метода равносильна умножению слева на матрицу
.
=
.
Следовательно, F min =11; X 4 =7/3; X 5 =1/3; X 1 =X 2 =X 3 =0.
Модифицированный симплекс-метод(МСМ ) отличается от обычного симплекс-метода(СМ ) тем, что в СМ все элементы симплекс-таблиц пересчитываются на каждой итерации и при получении очередной таблицы, все предыдущие таблицы, включая исходную, не сохраняются. В МСМ сохраняется исходная таблица, а на каждой итерации определяются: строка относительных оценок C , вводимых в базис , и текущее значение вектора правых частей ограничений . Для того чтобы определить все элементы таблицы после j- й итерации СМ , достаточно знать матрицу B -1 , соответствующую этой таблице, исходную матрицу и индексы текущих базисных переменных. Тогда текущий вектор R = C b B -1 (индексы текущих базисных переменных определяют, какие элементы вектора оценок из исходной таблицы входят в вектор С b ); =B -1 b , где b берется из исходной таблицы, а любой столбец новой таблицы=B -1 a j , гдеa j - столбец исходной таблицы.
Пусть задана теперь исходная таблица B -1 , соответствующая таблице i -й итерации. Для того чтобы получить матрицуB -1 , соответствующую (i+1)- й итерации, нужно определить небазисный столбец i -й таблицы , который должен быть введен в базис. ИзСМ следует, что должна быть введен в базис, в случае если C j <0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить С j для i -ой таблицы, выбрать среди них <0, а затем вычислить
a S = B -1 и =B -1 b (= C j - Ra j ).
Найдя разрешающий элемент и используя элементы векторов и , находим матрицу B -1 для следующей таблицы.
Пример. Модифицированным симплекс-методом минимизировать
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min
при ограничениях:
2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,
3X 2 + 3X 4 + 6X 5 = 9,
|
Выбрав в качестве базисных переменных X 1 и Х 2 , получили следующую задачу: F = 43 - 9/2X 3 - 12X 4 - 12X 5