Рассмотрим метод решения задачи ЦП, использующий идеи симплексного метода. Основная особенность задач ЦП заключается в конструкции целевой функции и в переменных, которые показывают отклонения от желаемого уровня достижения целей. Если учесть эти особенности, то для решения таких задач может быть применён обычный симплексный метод. Проиллюстрируем это на рассмотренном ранее примере. Алгоритм в некоторой степени упрощается из-за того, что исходное базисное решение здесь очевидно. Роль базисных переменных для начального плана здесь играют отрицательные отклонения «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. Оценка потребностей каждой операции в ресурсах; пересмотр плана выполнения операций с учётом обеспечения ресурсами либо
перераспределение денежных или других ресурсов, которое улучшит план.

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

Для решения задач линейного программирования существует множество методов. Рассмотрим один из них улучшенный (модифицированный) симплекс-метод

Для начала расскажем, что такое симплекс-метод. Слово SIMPLEX в обычном смысле означает простой, несоставной, в противоположность слову COMPLEX.

Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.

Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

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

Одним из модификаций симплекс-метода является улучшенный симплекс-метод. В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.

При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), улучшенный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.

В улучшенном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A -1 , обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису A x .

Рассмотрим поэтапно шаги решения задачи линейного программирования улучшенным симплекс-методом:

• 1. В начале первого цикла нам известны обратная матрица (единичная матрица), базисное решение x b = b.
• 2. Образуем для каждой небазисной переменной характеристическую разность j , используя уравнение:

j = c j -- = c j -- P j , (2)

где - двойственные переменные, которые можно найти следующим образом:

где c x - вектор коэффициентов целевой функции при базисных переменных.

3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим:

• 4. Если s 0 - процедура останавливается. Текущее базисное решение является оптимальным.
• 5. Если s 0, вычисляем преобразованный столбец:

= (, ...,) . (2.4)

Если все 0 - процедура останавливается: оптимум неограничен.

7. В противном случае находим выводимую из базиса переменную:

8. Строим увеличенную матрицу:

и трансформируем ее с ведущим элементом. Первые m столбцов дают матрицу, обратную новому базису.

9. Преобразуем базисное решение:

x b i x b i -- * , i r, (2.7)

и переходим к этапу 2.

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

Для этого нужно:

• 1. Сохранять исходную запись задачи на протяжении всей работы метода, это та цена, которую приходится платить за больше быстродействие;
• 2. Использовать так называемые симплекс - множители р - коэффициенты для непосредственного перехода от исходной записи задачи к ее текущей канонической форме базиса;
• 3. Использовать обращенный базис ВО№ - матрицу размера m x m, позволяющую вычислять на каждом шаге ведущий столбец aґs и обновлять симплекс - множители р.

Улучшенный симплекс-метод, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабо заполненными, содержат малый процент ненулевых элементов.

Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабо заполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается.

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

Поясним вычисления a i , j ¢ с использованием “правила прямоугольника“. Необходимо взять разрешающий элемент a k , s и мысленно соединить его с тем коэффициентом, новое значение которого требуется найти. Эту прямую следует считать главной диагональю, на ней строится прямоугольник, сторонами которого являются строки и столбцы. В прямоугольнике нужно провести побочную диагональ, тогда значение нового коэффициента будет равно его исходному значению, из которого вычитается произведение элементов, стоящих на побочной диагонали, поделœенному на разрешающий элемент. Поясним эти действия на схеме (рис. 1.9). Прежде чем заполнить симплекс-таблицу исходные уравнения следует представить в виде (1.21).

	a k,j
			a i,j

Суть преобразований симплекс-метода рассмотрим на примере 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 - равным единице.

Важно заметить, что для симплекс-метода в матричной форме итерация симплекс-метода эквивалентна умножению матричного уравнения слева на следующую квадратную матрицу:

(1.23)

, гдеk 0; s 0.

В случае если всœе столбцы матрицы 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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Подобные документы

Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.

реферат , добавлен 15.06.2010


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

курсовая работа , добавлен 17.02.2010


Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.

контрольная работа , добавлен 15.08.2012


Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.

контрольная работа , добавлен 18.02.2014


Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.

контрольная работа , добавлен 11.05.2014


Основы математического моделирования экономических процессов. Общая характеристика графического и симплексного методов решения прямой и двойственной задач линейного программирования. Особенности формулирования и методика решения транспортной задачи.

курсовая работа , добавлен 12.11.2010


Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.

контрольная работа , добавлен 01.06.2014

МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОДСимплекс-метод – не самая эффективная
компьютерная процедура, так как она вычисляет и
хранит информацию, которая не нужна для текущей
итерации и может вообще не использоваться для
принятия решений при последующих итерациях. Для
коэффициентов неосновных переменных в уравнении
(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.

- Итерация 1
so
so

11.

- Итерация 2
so
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). (Для исходного ОД решения).