Алгоритм симплексного метода

1. Записываем данную задачу в исходную симплексную таблицу.

2. Если все элементы оценочной строки симплексной таблицы неотрицательны, то соответствующий план является оптимальным.

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

4. Если в каждом столбце соответствующем отрицательной оценке содержится хотя бы один положительный элемент, то можно перейти к “лучшему ” плану следующим образом:

а) выбираем разрешающий столбец по наименьшей отрицательной оценке;

б) выбираем разрешающую строку по минимальному значению ;

равно отношению свободных членов к соответствующим положительным элементам разрешающего столбца;

в) на пересечении разрешающего столбца и разрешающей строки лежит разрешающий элемент;

г) элементы разрешающей строки делим на разрешающий элемент и записываем в новой таблице, сохраняя порядок строки, оставшиеся элементы разрешающего столбца заполняем нулями;

д) элементы остальных строк, в том числе и оценочной строки, вычисляем по формулам прямоугольников (см. метод Жордана – Гаусса).

Составим симплексную таблицу.

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

В столбце “a_i0” записываются свободные члены уравнений (16), в столбцах “ x₁”, “x₂”, …, “x₆” − коэффициенты при соответствующих неизвестных этой системы.

В столбце “базис” выписываются базисные переменные, содержащиеся в соответствующих уравнениях системы (16).

Верхняя строчка и крайний левый столбец содержат коэффициенты при соответствующих неизвестных целевой функции Z выражения (17).

Последняя строка таблицы называется оценочной строкой, а её элементы a_0j оценками. Первый элемент a₀₀ оценочной строки равен значению целевой функции Z для начального опорного плана

.

Это значение может быть получено как результат скалярного умножения вектора – столбца “с_j “ на вектор – столбец свободных членов “a_i0” :

Z(₀) = a₀₀ = 0∙220 + 0∙140 + 0∙100 = 0.

Остальные значения a_0к оценочной строки получаются в результате скалярного умножения вектора – столбца “с_j “ на вектор – столбец коэффициентов при переменной х_к с последующим вычитанием соответствующего элемента с_к верхней строки:

a₀₁ = 0∙7 + 0∙2 +0∙5 – 2 = -2;

a₀₂ = 0∙0 + 0∙3 +0∙1 – 1 = -1;

a₀₃ = 0∙5 + 0∙2 +0∙1 – 1 = -1.

Оценки для базисных переменных всегда равны 0.

cj	Базис xj	ai0	2	1	1	0	0	0
			x1	x2	x3	x4	x5	x6
0 0 0	x4 x5 x6	220 140 100	7 2 5	0 3 1	5 2 1	1 0 0	0 1 0	0 0 1	220/7 140/2 100/5 min
	Z	0	-2	-1	-1	0	0	0
0 0 2	x4 x5 x1	80 100 20	0 0 1	-7/5 13/5 1/5	18/5 8/5 1/5	1 0 0	0 1 0	-7/5 -2/5 1/5	min
	Z	40	0	-3/5	-3/5	0	0	2/5
0 1 2	x4 x2 x1	1740/13 500/13 160/13	0 0 1	0 1 0	58/13 8/13 1/13	1 0 0	7/13 5/13 -1/13	-21/13 -2/13 3/13	500/8 160
	Z	820/13	0	0	-3/13	0	3/13	4/13
1 1 2	x3 x2 x1	30 20 10	0 0 1	0 1 0	1 0 0	13/58 -8/58 -1/58	7/58 18/58 -5/58	-21/58 4/58 15/58
	Z	70	0	0	0	3/58	15/58	13/58

y₁ y₂ y₃

Исходное опорное решение ,не является оптимальным, в оценочной строке три отрицательные оценки (-2), (-1), (-1), ситуация соответствует пункту 4 алгоритма симплексного метода. Перейдём к новому опорному плану:

а) разрешающий столбец соответствует переменной , т.к. оценка (-2) ─ наименьшая отрицательная оценка оценочной строки;

б) третья строка является разрешающей, т.к. для неё ;

в) на пересечении разрешающих столбца и строки лежит разрешающий элемент 5, при этом в базис войдёт переменная , а переменнаявыйдет из базиса.

Далее заполнение новой таблицы осуществляется по методу Жордана – Гаусса.

В результате первой итерации получим новое опорное решение ,.

Вторая итерация приводит к решению:

, .

После третьей итерации получаем оптимальное решение: ,. Дальнейшее увеличениеZ невозможно, т.к. все оценки оценочной строки стали неотрицательными.

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

Двойственность в линейном программировании

Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования, так называемую двойственную задачу.

Рассмотрим задачу об оптимальном выпуске продукции (12)-(13):

(12)

(13)

Каждому ограничению ставится в соответствие переменная двойственной задачи . Двойственная задача имеет вид:

(18)

(19)

Для составления модели двойственной задачи необходимо учесть следующие свойства:

1.Число ограничений исходной задачи равно числу неизвестных двойственной.

2. Матрица коэффициентов при неизвестных одной задачи транспонируется для неизвестных другой задачи.

3. Знаки в неравенствах исходной задачи и двойственной имеют противоположный смысл, в исходной знак “”, в двойственной знак “”.

4. Свободные члены ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи, коэффициенты целевой функции исходной задачи ─ свободными членами неравенств двойственной задачи.

5. В исходной задаче целевая функция , в двойственной задаче.

Задачи (12)–(13) и (18)–(19) называются симметричными взаимно двойственными задачами. Модель двойственной задачи к исходной (14) – (15) имеет вид:

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

, ,.

.

Задание 7. Транспортная задача

В пунктах производства ,,имеется однородный груз в количестве соответственно,,,. Данный груз необходимо доставить в 3 пункта назначения,,в количестве соответственно,,. Стоимость перевозки единицы груза (тариф) из пунктав пунктравна. Требуется составить план перевозок, при котором все грузы будут вывезены с минимальными затратами.

Таблица 8 – Данные задания 7 «Транспортная задача»

№
1	4	3	6	4	1	6	2	8	2	8	3	7
2	4	3	6	4	1	6	7	8	2	4	5	3
3	4	3	5	4	1	6	7	8	2	8	5	7
4	4	3	6	4	1	6	7	8	2	9	5	7
5	2	7	3	6	4	3	7	4	5	4	6	2
6	4	7	6	6	4	3	1	4	3	4	6	2
7	2	5	6	6	4	3	1	4	3	4	6	2
8	8	3	5	2	4	6	6	7	1	9	4	3
9	8	6	5	2	4	1	6	7	5	9	4	3
10	8	6	5	2	2	1	6	7	1	9	4	3
11	8	6	5	2	3	1	6	7	1	9	4	3
12	4	5	7	7	8	2	4	1	6	4	3	6
13	8	5	7	7	8	2	4	1	6	4	3	3
14	7	5	8	2	8	7	6	1	4	2	3	4
15	3	5	4	2	8	7	6	3	4	5	3	7
16	2	5	4	2	8	7	6	3	4	6	3	5
17	2	5	4	2	4	7	6	3	2	6	3	5
18	2	5	4	2	4	7	6	3	2	4	3	6
19	2	5	4	2	4	6	5	3	2	4	3	6
20	5	4	6	2	4	6	5	3	2	4	3	6

Таблица 9 – Данные задания 7 «Транспортная задача»

№
1	30	40	50	10	40	70	20
2	25	45	50	10	35	65	20
3	20	40	45	10	35	65	20
4	20	40	55	10	35	70	20
5	22	44	54	20	35	70	60
6	25	45	30	20	35	70	60
7	25	45	30	20	20	70	60
8	20	40	30	20	20	70	60
9	15	40	30	20	20	30	55
10	15	40	30	15	20	30	55
11	15	26	30	15	20	32	55
12	10	25	30	15	40	15	15
13	10	25	30	35	40	15	15
14	10	25	30	35	30	30	40
15	28	25	10	15	34	25	25
16	20	15	10	15	30	10	20
17	15	15	10	20	30	10	20
18	35	15	10	20	30	10	20
19	23	15	10	20	30	10	25
20	16	15	10	20	30	10	29

Пример 7. Решить транспортную задачу, используя следующие данные:

Решение: Транспортная задача называется закрытой если .

Проверим модель на сбалансированность:

Так как , условие баланса не выполняется, данная модель является открытой. Приведём задачу к закрытому виду; введём фиктивного потребителя, потребность которого равнаед. груза. Стоимости перевозки единицы груза (тарифы) для фиктивного потребителя (поставщика) принимаются равными 0.

Составим исходный план перевозок методом «наименьшего элемента» (минимальной стоимости). Поставки в клетки с нулевыми тарифами осуществляются в последнюю очередь.

1. Выбираем клетку (2,2) с наименьшим «реальным» тарифом равным 1. Записываем в эту клетку максимально возможную поставку 45 ед. груза, т.е. наименьшее из чисел и. Исключаем при этом из дальнейшего рассмотрения поставщика(его возможности полностью исчерпаны). Запомним, что потребительеще нуждается в 70−45=25 ед. груза.

2. Минимальный тариф равный 2 соответствует двум клеткам (3,1) и (3,3) выбираем любую, например клетку (3,1), помещаем в эту клетку 40 ед. груза (,) и исключаем из рассмотрения потребителя(его потребности полностью удовлетворены). У поставщикаещё имеется в 50−40=10 ед. груза.

3. Заполним клетку (3,3), которой соответствует минимальный тариф равный 2, поставка в этой клетке равна 10 (,), исключаем из рассмотрения. У потребителяеще имеется потребность в 30−10=20 ед. груза.

4. В оставшейся части таблицы наименьший тариф 3 соответствует клеткам (1,2) и (4,2), выберем клетку (4,2) и поместим поставку 25 ед. груза (). Исключаем из рассмотрения два пунктаиодновременно, поэтому в клетку (4,3), стоящую рядом с клеткой (4,2) запишем 0.

5. В клетку (1,3) помещаем 20 ед. груза (), исключаем потребителя. При этом у поставщикаеще имеется в 30−20=10 ед. груза.

6. Заполним последнюю оставшуюся клетку (1,4) поставкой 10 единиц груза. Все запасы распределены, а потребности удовлетворены.

В опорном плане число занятых поставками клеток должно быть равно числу .

План-1	40	70	30	10
30	5 -1 +	3 1	6 20 −	0 10
45	5 0	1 45	6 1	0 1
50	2 40 −	7 9	2 + 10	0 4
25	8 1	3 25	7 0	0 -1

Проверим полученный план на оптимальность методом потенциалов:

а) Потенциалами строк –и столбцов –называются числа, удовлетворяющие условиюдля базисных переменных (для заполненных клеток).

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

Остальные потенциалы найдём, решая систему уравнений:

б) Определяем характеристики для свободных клеток по формуле и запишем их в левом нижнем углу свободных клеток. План является оптимальным если все.

План 1 не оптимален, так как и.

Улучшим план. Выберем клетку с наименьшей отрицательной характеристикой, например, клетку (1,1) пометим знаком «+» и построим для неё контур:

(1,1)(1,3)(3,3)(3,1).

Контур удовлетворяет следующим условиям: это замкнутая ломаная, состоящая из вертикальных и горизонтальных отрезков; отрезки контура могут пересекаться; все вершины контура находятся в заполненных клетках, за исключением той клетки, для которой он строится; число вершин ─ чётное.

Клетки, в которых находятся вершины контура, поочередно помечаем знаками «+» и «─». Из клеток, помеченных знаком «─», выбираем наименьшую поставку . Числоперераспределяется по контуру, в клетках со знаком «+» добавляется, в клетках со знаком «─» отнимается. После перераспределения груза, только одна вершина контура становится свободной.

Строим новый план перевозок.

План-2	40	70	30	10
30	5 20 +	3 2	6 1	0 10 −
45	5 1	1 45	6 2	0 1
50	─ 2 20	7 9	+ 2 30	0 3
25	8 1	3 25	─ 7 0	+ 0 -2

Затраты на реализацию плана 2 составляют:

Найдем потенциалы строк и столбцов, для чего составим систему уравнений. Потенциал примем равным 0.

Определим характеристики для свободных клеток.

План 2 не является оптимальным, т.к.

После применения, рассмотренного выше алгоритма, получили план 3.

План-3	40	70	30	10
30	5 20	3 0	6 1	0 10
45	5 2	1 45	6 3	0 2
50	2 20	7 7	2 30	0 3
25	8 3	3 25	7 2	0 0

План 3 является оптимальным, т, к. все . Затраты на реализацию оптимального плана составляют

2