1. 2.7.3.Алгоритм модифицированного симплекс-метода.

Шаг 1. Определение включаемого вектора . Вычислить . Для каждого небазисного вектора найти

(2.26)

В задаче максимизации (минимизации) в качестве включаемого в базис вектора выбирается тот, которому соответствует наибольшая по абсолютной величине отрицательная (положительная) величина (при наличии альтернатив выбор делается произвольно). Если для всех j, то полученное решение

(2.27)

является оптимальным. В противном случае осуществляется переход к Шагу 2.

Шаг 2. Определение исключаемого вектора . При известном исключаемом векторе вычислить:

1. значения текущих базисных переменных, то есть ;

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

(2.28)

где и - k-е элементы и . Случай , когда все , свидетельствует о неограниченности решения.

Шаг 3. Определение нового базиса. По известной обратной матрице текущего базиса найти обратную матрицу для нового базиса , используя формулу . Затем положить и перейти к Шагу 1.

Таблица 2.43

Базисные переменные							Решение
z

На шаге 1 вычисляются коэффициенты z-строки и определяется включаемая в базис переменная . Затем на Шаге 2 путём вычисления элементов правой части таблицы (=) и коэффициентов ограничений при вводимой в базис переменной () определяется исключаемая переменная.

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

Пример 2.15:

Максимизировать при ограничениях

Начальное решение

Первая итерация

Шаг 1. Вычисление для небазисных векторов и .

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

Таблица 2.44

Базисные переменные							Решение
z	-3	-2	0	0	0	0

(Заметим, что автоматически обращаются в нуль для всех базисных переменных.) В соответствии с полученными результатами в качестве включаемого в базис вектора выбирается .

Шаг 2. Определение исключаемого вектора при условии введения в базис вектора .

Результаты вычислений на шагах 1 и 2 можно представить в виде следующей таблицы:

Таблица 2.45

Базисные переменные							Решение
z	-3	-2	0	0	0	0	0
	1						6
	2						8
	-1						1
	0						2

Отсюда следует, что

Соответствует переменной . Таким образом, исключению из базиса подлежит вектор .

Шаг 3. Определение обратной матрицы, соответствующей новому базису.

Так как вместо вектора в базис вводится вектор и , то

Новому базису соответствуют векторы

Вторая итерация

Шаг 1. Вычисление для небазисных векторов и .

Следовательно, включению в базис подлежит вектор .

Шаг 2. Определение исключаемого вектора при условии ввода в базис вектора .

Результаты вычислений на шагах 1 и 2 алгоритма можно представить в виде следующей таблицы:

Таблица 2.46

Базисные переменные							Решение
z	0	-1/2	0	3/2	0	0
		3/2					2
		1/2					4
		3/2					5
		1					2

Отсюда следует, что

Соответствует переменной . Таким образом, исключению из базиса подлежит вектор .

Шаг 3. Определение новой обратной матрицы.

Так как в базис вместо вектора вводится вектор и , то

Новому базису соответствуют векторы

Третья итерация

Шаг 1. Вычисление для векторов и .

Так как для всех j, полученный базис соответствует оптимальному решению.

Оптимальное решение

Гомори

Пример 2.17:

Найти решение ЗЦЛП методом Гомори.

ЗЛП имеет вид:

- канонический вид.

Таблица 2.52

базис	значение	x1	x2	x3	x4	x5	x6
x3	4,2	0	0	1	-0,4	0,2	0
x6	32,6	0	0	0	1,3	-0,9	1
x2	10,6	0	1	0	0,3	0,1	0
x1	10,8	1	0	0	-0,1	0,3	0
f (x)	32,2	0	0	0	0,1	0,7	0

Решение:

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

В данном случае наибольшая дробная часть у x₁.

Определяем значение и :

10,8 – [10,8] = 0,8;

1 – [1] = 0;

0 – [0] = 0;

0 – [0] = 0;

-0,1 – [-0,1] = 0,9;

0,3 – [0,3] = 0,3;

0 – [0] = 0.

Дополнительное ограничение имеет вид:

;

Приводим к канонической форме:

Вводим выражение в симплекс – таблицу:

Итерация №0 Таблица 2.53

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	4,2	0	0	1	-0,4	0,2	0	0
x6	32,6	0	0	0	1,3	-0,9	1	0
x2	10,6	0	1	0	0,3	0,1	0	0
x1	10,8	1	0	0	-0,1	0,3	0	0
x7	-0,8	0	0	0	-0,9	-0,3	0	1
f (x)	32,2	0	0	0	0,1	0,7	0	0

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

Переменную x₄ вводим в число базисных вместо переменной x₇

Ведущий элемент равен -0,9.

Итерация №1 Таблица 2.54

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	41/9	0	0	1	0	1/3	0	-4/9
x6	283/9	0	0	0	0	-4/3	1	13/9
x2	31/3	0	1	0	0	0	0	1/3
x1	98/9	1	0	0	0	1/3	0	-1/9
x4	8/9	0	0	0	1	1/3	0	-10/9
f (x)	289/9	0	0	0	0	2/3	0	1/9

В решении задачи базисные переменные нецелые.

Наибольшая дробная часть у x₁ и x₄ . Выберем x_1.

Определяем значение и :

98/9 – [98/9] = 8/9;

1 – [1] = 0;

0 – [0] = 0;

0 – [0] = 0;

0 – [0] = 0;

1/3 – [1/3] = 1/3;

0 – [0] = 0;

-1/9 – [-1/9] = 8/9.

Дополнительное ограничение имеет вид:

;

Приводим к канонической форме:

Вводим выражение в симплекс – таблицу:

Итерация №0 Таблица 2.55

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	41/9	0	0	1	0	1/3	0	-4/9	0
x6	283/9	0	0	0	0	-4/3	1	13/9	0
x2	31/3	0	1	0	0	0	0	1/3	0
x1	98/9	1	0	0	0	1/3	0	-1/9	0
x4	8/9	0	0	0	1	1/3	0	-10/9	0
x8	-8/9	0	0	0	0	-1/3	0	-8/9	1
f (x)	289/9	0	0	0	0	2/3	0	1/9	0

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

Переменную x₇ вводим в число базисных вместо переменной x₈

Ведущий элемент равен -8/9.

Итерация №1 Таблица 2.56

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	5	0	0	1	0	0,5	0	0	-0,5
x6	30	0	0	0	0	-1,875	1	0	1,625
x2	10	0	1	0	0	-0,125	0	0	0,375
x1	11	1	0	0	0	0,375	0	0	-0,125
x4	2	0	0	0	1	0,75	0	0	-1,25
x7	1	0	0	0	0	0,375	0	1	-1,125
f (x)	32	0	0	0	0	0,625	0	0	0,125

Ответ:

Ветви

Пример 2.18:

Найти max

1. Решим эту задачу, отбросив условие целочисленности, любым методом линейного программирования.

Обозначим эту задачу ЛП-1

Так как х₂ – не целочисленно, решение не является решением исходной задачи, но представляет собой верхнюю границу оптимального целочисленного решения, то есть при достижении целочисленности х₂ значения целевой функции может лишь ухудшиться.

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

В нашем случае вводиться ограничение х₂  1 или х₂  2.

Таким образом, из задачи ЛП-1 получается две задачи

ЗЛП-2

ЗЛП-3

Для ЗЛП-2 оптимальное решение:

Для ЗЛП-3 оптимальное решение

Оптимальное решение ЗЛП-3 больше, чем ЗЛП-2, однако условие целочисленности выполняется только во второй задаче, следовательно, оптимальное решение ЗЛП-2 можно считать нижней границей оптимального целочисленного решения.

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

Так как верхняя граница = 9, а решение задачи ЛП-3 находится внутри диапазона от нижней до верхней границы, то нельзя утверждать, что ЛП-2 оптимальна для исходной задачи, следовательно, необходимо проанализировать задачу ЛП-3.

Так как в ЗЛП-3 х₁ имеет не целочисленное значение, то в ЗЛП-3 необходимо добавить ограничения

ЗЛП-4

ЗЛП-5

Решение ЗЛП-4:

Полученное решение не превосходит нижней границы из ЛП-2 ( = 8), следовательно, дальнейшее исследование данной ветви прекращаем.

ЗЛП-5 не имеет допустимых решений, следовательно, решение задачи ЛП-2, то есть

- является оптимальным для исходной задачи.

Последовательность задач ЛП, возникающих при использовании процедуры ветвей и границ удобно представить в виде дерева следующего вида:

Метод потенциалов

Пример 3.4. Решить заданную транспортную задачу методом потенциалов. Для построения исходного плана использовать следующие методы:

• Метод северо-западного угла;

• Метод минимального элемента.

Таблица 3.9

Всего	99	97	95	95	95
96	16	15	14	15	6	А1
97	8	11	6	8	8	А2
99	12	7	9	13	8	А3
189	10	8	4	3	8	А4
	В1	В2	В3	В4	В4

1. Метод северо-западного угла.

Таблица 3.10

Транспортные расходы:

2. Метод минимального элемента

Таблица 3.11

Транспортные расходы:

3. Метод потенциалов (для оптимизации исходного плана, полученного методом северо-западного угла)

Таблица 3.12

Косвенные тарифы для незаполненных клеток:

Значение целевой функции на данном этапе:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»: 1. Перейдем к следующей таблице.

Таблица 3.13

Косвенные тарифы для незаполненных клеток:

Значение целевой функции на данном этапе:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»: 93. Перейдем к следующей таблице.

Таблица 3.14

Косвенные тарифы для незаполненных клеток:

Значение целевой функции на данном этапе:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»:1. Перейдем к следующей таблице.

Таблица 3.15

Косвенные тарифы для незаполненных клеток:

Проверка на оптимальность:

Полученный план является оптимальным.

Транспортные расходы:

4. Метод потенциалов (для оптимизации исходного плана, полученного методом минимального элемента).

Таблица 3.16

Косвенные тарифы для незаполненных клеток:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»:1. Перейдем к следующей таблице.

Таблица 3.17

Косвенные тарифы для незаполненных клеток:

Проверка на оптимальность:

Полученный план является оптимальным.

Транспортные расходы:

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

Таблица 3.19

Перейдем от таблицы 3.19 к таблице 3.20, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну для записи соответствующих разностей.

Таблица 3.20

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

В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения B₂,B₃ и B₅ и частично – пункта назначения B₁ и B₄. При этом полностью распределены запасы пункта отправления А₂, так как запасы пункта отправления А₂ полностью использованы, а потребности пункта назначения B₁ удовлетворены частично. Величина недостатка равна 2 ед.

Строки А₁ и А₃ являются избыточными, поскольку запасы пунктов отправления А₁ и А₃ распределены не полностью. При этом величина избытка строки А₁ равна 1 ед., а строки А₃ – 2 ед. Общая величина избытка 1+2=3 совпадает с общей величиной недостатка, равной 3.

После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 4,5,10 (таблица 3.20). Для столбцов B₂ и B₅ разность не определена, так как число, записанное в кружке в данных столбцах, находится в положительной строке. В столбце B₁ число, стоящее, стоящее в кружке, равно 8, а в избыточных строках в клетках данного столбца наименьшим является число 12. Следовательно, разность для данного столбца равна 12-8=4. Аналогично находим разности для других столбцов.

Выбираем наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна 4 и находится в столбце B₁. Найдя промежуточную ренту переходим к таблице 3.21.

Таблица 3.21

В этой таблице в строках А₁ и А₃ (являющихся избыточными) переписываем соответствующие тарифы из строк А₁ и А₃ таблицы 3.20. Элемент строк А₂ и А₄, которые были недостаточными получаются в результате прибавления к соответствующим тарифам, находящимся в строках А₂ и А₄ (таблицы 3.20) промежуточной ренты, то есть 4.

В таблице 3.21 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на 1, а именно столбце B₁ теперь имеются два минимальных элемента 12. Эти числа заключаем в кружки; клетки, в которых они стоят, следует заполнить. Необходимо заполнить и клетки, в которых стоят наименьшие для других столбцов тарифы. Это клетки таблицы 3.21, в которых соответствующие тарифы заключены в кружки. После того как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец(строку) и переходим к заполнения следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки A₃B₂, A₄B₃, A₄B₄, A₁B₅, так как они являются единственными клетками, для заполнения в столбцах B₂, B₃, B₄, B₅. После заполнения указанных клеток заполняем клетку А₂B₁, поскольку она является единственной для заполнения в строке А₂, заполнив эту клетку (таблица 3), исключаем из рассмотрения строку А₂. Тогда в столбце B₁ остается лишь одна клетка для заполнения. Эта клетка А₃B₁, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки (таблицы 3.21). Как видно из таблицы 3, еще имеется не распределенный остаток. Следовательно, получен условно оптимальный план задачи, и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках (таблица 3.21). Среди этих разностей наименьшая равна 4. Это и есть промежуточная рента. Переходим к новой таблице 3.22.

Таблица 3.22

В новой таблице элементы строки А₁ получены в результате прибавления к соответствующим числам строки А₁ (являющихся недостаточными) таблицы 3.3.8 промежуточной ренты, т.е. 4. В результате в таблице 3.22 число клеток для заполнения возросло еще на одну и стало равным 7. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₃B₂, А₄B₃, A₄B₄, A₁B₅, а затем А₂В₁, А₁В₁, А₃В₁. Как видно из таблицы 3.22, еще имеется не распределенный остаток. Следовательно, получен условно оптимальный план задачи, и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках (таблица 3.22). Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к новой таблице 3.23

Таблица 3.23

.

В новой таблице элементы строки А₄ получены в результате прибавления к соответствующим числам строки А₄ (являющихся недостаточными) таблицы 3.22 промежуточной ренты, т.е. 1. В результате в таблице 3.23 число клеток для заполнения возросло еще на одну и стало равным 8. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₃B₂, A₄B₄, A₁B₅, а затем А₂В₁, А₁В₁, А₃В₁, А₃В₃, А₄В₃. В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 8, и все они имеют наименьший показатель с_ij. Следовательно, получен оптимальный план исходной транспортной задачи.

При этом плане перевозок общие затраты таковы:

Пример решения транспортной задачи венгерским методом

Предварительный этап

Составляем матрицы C’ и

Перед началом каждой итерации выделяют знаком ‘+’ те столбцы матрицы , для которых невязка по столбцам равно 0, .

1. Первая итерация

• Первый этап.

Находим первый невыделенный 0, вычисляем значения невязки i-й строки . Отмечаем четвертую строку ‘+’, а сам нуль штрихом. Существенный нуль . Все нули матрицы оказались выделены, причем для каждого выделенного нулем штриха => переходим к третьему этапу.

• Третий этап

, где min выбирается из всех невыделенных элементов матрицы . Тогда из всех элементов невыделенных строк матрицы вычитаем h, а ко всем элементам выделенных столбцов – прибавляем.

Получили новый невыделенный нуль. Переходим к первому этапу.

• Первый этап

Невыделенный нуль находится в 1-й строке 5-м столбце . Отмечаем строку плюсом и отмечаем нуль штрихом. Находим существенные нули в этой строке.

Т.к. 1-й и 3-й столбцы уже отмечены, уничтожаем над ними ‘+’ и отыскиваем нуль, расположенный не в 1-й строке. Это . Его невязка =5>0. => отмечаем нуль штрихом и переходим ко второму этапу.

• Второй этап

Состоит в построении цепочки из нулей матрицы , отмеченных штрихами и звездочками, и переходе к новой матрице . Для нуля со штрихом в позиции невязка строки . Начиная с этого элемента, строим цепочку:

После этого переходим к матрице .

=> план оптимальный

f=3 339