Модифицированный симплекс-метод. Курсовая работа: Симплекс метод в форме презентации

1.5.1. Вычислительная схема, основанная на преобра­зовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, не­трудно заметить, что наиболее критичным в этом плане являет­ся этап пересчета значений А и b при переходе от одного базис­ного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n , можно добиться существенной «экономии», вы­полняя на очередной итерации q преобразование Жордана-Га­усса не над матрицей А (β ( q )), а над матрицей Δ -1 (β ( q )). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно получить А (β ( q )) по Δ -1 (β ( q )). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А (β ( q )) целиком. Реаль­но в ней использовались только строка оценок a 0 (β ( q )) и ведущий столбец a l (β ( q )). Данные соображения положены в основу вы­числительной схемы симплекс-метода, основанной на преобра­зовании обратных матриц, которую также называют модифици­рованным симплекс-методом . Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.

Вычислительной схеме модифицированного симплекс-мето­да соответствует система таблиц T 1 и Т 2 ( q ) . Таблица T 1 (рис. 1.7 ) является общей для всех итераций и служит для получения строки оценок текущего базисного плана a 0 (β ( q )). Если обозна­чить через δ i (β ( q )) (i Î 0: m ) строки матрицы Δ -1 (β ( q )), то из (1.26), в частности, следует, что

Как видно из рис. 1.7 , T 1 состоит из трех блоков:

Ø Ø в центре содержится матрица А ;

Ø Ø в левом блоке таблицы на каждой итерации дописывают­ся нулевые строки матрицы Δ -1 (β ( q ))для текущего ба­зиса ;

Ø Ø нижний блок, расположенный под матрицей А , на каж­дой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).

Симплекс-таблица Т 2 ( q ) , изображенная на рис. 1.8 , соответ­ствует допустимому базису КЗЛП β ( q ) , получаемому на q -й ите­рации. Столбец N (β ( q )) содержит номера базисных столбцов (в последовательности вхождения в базис); столбец b (β ( q )) - компоненты вектора ограничений относительно текущего ба­зиса β ( q ) ; Δ -1 (β ( q )) - матрица, обратная по отношению к матри­це расширенных столбцов текущего базиса β ( q ) ; графа а l со­держит расширенный вектор условий, вводимый в базис на текущей итерации, а следующая графа - координаты а l (β ( q )) этого же столбца в текущем базисе β ( q ) .

По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.

0-этап. Нахождение допустимого базисного плана.

1. Для поиска допустимого базиса может быть применен ме­тод минимизации невязок, рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедура модифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план x (β (1)) и соответствую­щие ему матрицу Δ -1 (β (1)) и вектор b (β (1)).

2. Заполняем центральную часть таблицы T 1 , содержащую матрицу А .

3. Содержимое матрицы Δ -1 (β (1)) и вектора b (β (1)), получен­ных на этапе поиска допустимого базисного плана, переносит­ся в таблицу T 2 (1) .

4. Полагаем номер текущей итерации q равным 1 и перехо­дим к I-этапу.

1-этап. Стандартная итерация алгоритма - выполня­ется для очередного базисного плана x (β ( q )).

1°. Проверка оптимальности текущего базисного плана . Содержимое нулевой строки таблицы T 2 ( q ) - δ 0 (β ( q )) переписы­вается в соответствующую графу таблицы T 1 . По формуле (1.42) рассчитываем и заполняем строку a 0 (β ( q )). Осуществля­ем просмотр строки оценок a 0 (β ( q )). Возможны два варианта:

1΄. a 0 (β ( q ))≥0 -план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Со­гласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х * = x (β ( q )) и оптимальное значение целевой функ­ции f (х *) = f (x (β ( q ))).

1". В строке оценок a 0 (β ( q )) существует по меньшей мере один элемент a 0, j (β ( q ))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x (β ( q )) - неоптимален . Выбирает­ся номер l , соответствующий элементу, имеющему минималь­ную (максимальную по абсолютной величине) отрицательную оценку:

l -й столбец матрицы A становится ведущим и должен быть вве­ден в очередной базис. Переходим к пункту 2° алгоритма.

2°. Определение столбца, выводимого из базиса . Перепи­сываем ведущий столбец а l из таблицы T 1 в текущую таблицу Т 2 ( q ) . По формуле а l (β ( q )) = Δ -1 (β ( q ))а l заполняем соответствую­щий столбец в таблице Т 2 ( q ) . Возможны два варианта:

2". Для всех i Î 1: m а i , l (β ( q ))≤0. Делается вывод о неограни­ченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере один индекс i Î 1: m , для ко­торого а i , l (β ( q ))>0. Согласно правилу (1.27) определяются мес­то r и номер N r (β ( q )) для столбца, выводимого из базиса. Пере­ходим к пункту 3° алгоритма.

3°. Пересчет относительно нового базиса элементов столбца b и матрицы Δ -1 . Переход к новому базису β ( q +1) , кото­рый получается введением в базис β ( q ) столбца а l и выводом из него столбца а r , осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:

Полагаем номер текущей итерации q : =q +l и переходим к первому пункту алгоритма.

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

1.5.2. Пример решения ЗЛП модифицированным сим­плекс-методом. Приведем решение рассмотренной ранее за­дачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3 оно начинается с выбора очевидного исходного базиса, обра­зуемого столбцами {5,2,3}. Для него уже были вычислены Δ -1 (β ( q )) и b (β ( q )), поэтому заполнение начальных таблиц T 1 и Т 2 (1) не представляет труда.

На первой итерации мы переписываем нулевую строку

из Т 2 (1) в T 1 и, умножив ее на матрицу A , получаем строку оце­нок

Так как a 0 (β (1)) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β (1) , и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l = 4.

Переписываем столбец

из таблицы T 1 в Т 2 (1) и пересчитываем его координаты относи­тельно текущего базиса, т. е. умножаем матрицу Δ -1 (β ( q )), рас­положенную в таблице Т 2 (1) слева, на а 4 .

После заполнения таблицы Т 2 (1) данными по вводимому в но­вый базис столбцу можно перейти к определению номера выво­димого столбца. Эта процедура осуществляется в полной ана­логии с обычным симплекс-методом. Рассмотрев отношения элементов b i (β (1)) и a i , l (β (1)) для {i Î1:m| a i , l (β (1))>0} и определив минимальное из них, находим, что r = 2. Следовательно, стол­бец с номером N 2 (β ( q )) = 2 должен быть выведен из базиса. Та­ким образом, получаем очередной допустимый базис задачи с N (β (2)) = {5, 4, 3}. Элемент a 2,3 (β (1)) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к сим­плекс-таблице, соответствующей второй итерации Т 2 (2) , и пола­гаем индекс текущей итерации q = 2.

Повторяя те же самые действия (их легко проследить по при­водимым здесь таблицам Т 2 (2) и Т 2 (3) , на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т 2 (3) . Легко заметить, что в процессе решения мы «про­шли» по той же самой последовательности допустимых базис­ных планов, которая встречалась в п. 1.4.3.

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

Основная идея модифицированного симплекс-метода заключается в использовании текущей обратной матрицы (и исходных данных задачи) при выполнении вычислений, необходимых для определения включаемой и исключаемой переменных. Представление обратной матрицы в мультипликативной форме позволяет вычислять последовательность обратных матриц непосредственно по исходным данным без использования многократных операций обращения каждого базиса. Как и в обычном симплекс-методе, в данном случае исходный базис всегда представляет собой единичную матрицуI, обратной к которой является сама эта матрица. Поэтому, если
- последовательность обратных матриц, соответствующих итерациям 1, 2,…,i, а
- последовательность соответствующих им матриц, то

Последовательность подстановок приводит к следующей формуле:

(2.23)

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

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

1. 2.7.2. Мультипликативное представление обратной матрицы

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

Определим единичную матрицу следующим образом:

(2.24)

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

(2.25)

при условии, что
. Если
, матрицы
не существует. Заметим, что матрицаполучается из матрицыпутём замены еёr-го вектор-столбцастолбцом.

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

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

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

МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД  

Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является э ап пересчета значений А и b при переходе от одного базисного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных я, можно добиться существенной экономии, выполняя на очередной итерации q преобразование Жордана-Гаусса не над матрицей Л(р() по Д Чр(ведущий столбец аЧр О. Данные соображения положены в основу вычислительной схемы симплекс-метода , основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.  

Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц 7] и T q). Таблица 7J (рис. 1.7) является общей для всех итераций и служит для получения  

По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.  

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

Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3  

Еще раз вернемся к таблице Т (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс--метода. Более подробно рассмотрим нулевую строку матрицы A 4p(

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

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

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

Сформулируйте основные отличия модифицированного симплекс-метода по отношению к стандартному.  

Перечислите преимущества модифицированного симплекс-метода.  

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

Метод разложения (декомпозиции) был разработан для решения задач линейного программирования большой размерности, имеющих блочную структуру. Его вычислительная процедура главным образом основана на идеях модифицированного симплекс-метода. Однако значение метода Данцига-Вулфа состоит не только и (не столько) в его вычислительных преимуществах, сколько в возможности дать содержательную экономическую интерпретацию . Метод предусматривает разложение исходной задачи (5.6)-(5.9) на локальные задачи, соответствующие обособленным частям объединения (в данном случае предприятиям), и главную задачу (соответствует объединению в целом и связывает эти локальные задачи).  

Р. Б. Д у б и н а, К. Е. Ч е р н и н. Программа образования и записи на М. Б. матрицы для модифицированного симплекс-метода.- Сборник программ для ЭВМ Урал. Л., Аркт. и антаркт. ин-т, 1966.  

Среди методов нахождения оптимального решения наибольшее распространение приобрёл метод последо -ват. улучшения допустимого решения (МНУ), к-рый имеет большое число вычислит, реализаций (