Задачи линейного программирования

Размещено на http://www.allbest.ru/

1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Используя геометрическую интерпретацию задачи линейного программирования найдите решение задачи:

;

.

Значения коэффициентов A, B, C, D, E, F, G, K, L, M приведены в табл. 1.

Номер варианта	A	B	C	D	E	F	G	H	K	L	M
4	5	4	25	8	200	20	11	220	10	25	250

Решение:

Необходимо найти максимальное значение целевой функции F = 5x1+4x2 > max, при системе ограничений:

25x1+8x2?200 (1)

20x1+11x2?220 (2)

10x1+25x2?250 (3)

x1?0 (4)

x2?0 (5)

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



Или



Границы области допустимых решений.

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

Рассмотрим целевую функцию задачи F = 5x1+4x2 > max. Построим прямую, отвечающую значению функции F = 0: F = 5x1+4x2 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (5; 4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.



Изменить масштаб

Пределы по оси OX: x1=, x2 = . Пределы по оси OY: y1=, y2 =



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

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых(1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

25x1+8x2=200

10x1+25x2=250

Решив систему уравнений, получим: x1 = 5.5046, x2 = 7.7982

Откуда найдем максимальное значение целевой функции:

F(X) = 5*5.5046 + 4*7.7982 = 58.7156

задача решение линейный программирование

1.1 Транспортная задача

Имеются три завода по производству бетона А1, А2, А3. На заводе А1 производится 160 тонн бетона, на заводе А2 - 210 тонн бетона, на заводе А3 160 тонн бетона. Полученный бетон требуется перевезти в пять строительных объектов: 170 тонн на объект В1, 70 тонн на объект В2, 100 тонн на объект В3, 90 тонн на объект В4, 100 тонн на объект В5. Расстояние между заводами-поставщиками бетона и объектами указано в таблице 1 (матрица расстояний или себестоимость перевозок).

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

Таблица 1

Номер варинта анта	Заводы -- отправители	Объекты, назначения (объем их спроса Bi ). Матрица расстояний или себестоимость перевозок
		В1	В2	В3	В4	В5
4	A1 = 160	9	21	8	12	17
	A2= 210	5	15	13	16	18
	А3=160	16	22	12	13	20
	В	170	70	100	90	100

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

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

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

При решении транспортной задачи распределительным методом процесс вычислений включает следующие основные этапы:

1) Составление первоначального (базисного) опорного плана перевозок.

2) Проверку на оптимальность составленного базисного плана.

3) Перераспределение плана поставок в случае не оптимальности полученного плана и проверку его на оптимальность.

4) Вычисление целевой функции.

1. Составление базисного (опорного) плана перевозок.

Наиболее рациональным приёмом составления базисного плана транспортной задачи считается сочетание методов “северо-западного угла” и наименьшего элемента по столбцу или строке. Данное сочетание обеспечивается тем, что, взяв за основу распределения поставок метод “северо-западного угла”, мы варьируем строками и столбцами таблицы так, чтобы клетки с наименьшими, или базисными к ним, затратами оказались загруженными. Составленный в соответствии с методом “северо-западного угла” базисный план перевозок бетона в строительные объекты приведён в табл. 2. С целью упрощения записи реквизиты данной и последующих таблиц поставленной задачи не приводятся.

Поставщики	1	2	3	4	5	Ресурсы
1	9	21	8	12	17	160
2	5	15	13	16	18	210
3	16	22	12	13	20	160
Потребности	170	70	100	90	100

Проверим необходимое и достаточное условие разрешимости задачи.

? a = 160 + 210 + 160 = 530

? b = 170 + 70 + 100 + 90 + 100 = 530

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность. Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова.

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 9

Для этого элемента запасы равны 160, потребности 170. Поскольку минимальным является 160, то вычитаем его.

x11 = min(160,170) = 160.

9	x	x	x	x	160 - 160 = 0
5	15	13	16	18	210
16	22	12	13	20	160
170 - 160 = 10	70	100	90	100	0

Искомый элемент равен 5.

Для этого элемента запасы равны 210, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x21 = min(210,10) = 10.

9	x	x	x	x	0
5	15	13	16	18	210 - 10 = 200
x	22	12	13	20	160
10 - 10 = 0	70	100	90	100	0

Искомый элемент равен 15.

Для этого элемента запасы равны 200, потребности 70. Поскольку минимальным является 70, то вычитаем его.

x22 = min(200,70) = 70.

9	x	x	x	x	0
5	15	13	16	18	200 - 70 = 130
x	x	12	13	20	160
0	70 - 70 = 0	100	90	100	0

Искомый элемент равен 13

Для этого элемента запасы равны 130, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x23 = min(130,100) = 100.

9	x	x	x	x	0
5	15	13	16	18	130 - 100 = 30
x	x	x	13	20	160
0	0	100 - 100 = 0	90	100	0

Искомый элемент равен 16.

Для этого элемента запасы равны 30, потребности 90. Поскольку минимальным является 30, то вычитаем его.

x24 = min(30,90) = 30.

9	x	x	x	x	0
5	15	13	16	x	30 - 30 = 0
x	x	x	13	20	160
0	0	0	90 - 30 = 60	100	0

Искомый элемент равен 13.

Для этого элемента запасы равны 160, потребности 60. Поскольку минимальным является 60, то вычитаем его.

x34 = min(160,60) = 60.

9	x	x	x	x	0
5	15	13	16	x	0
x	x	x	13	20	160 - 60 = 100
0	0	0	60 - 60 = 0	100	0

Искомый элемент равен 20.

Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x35 = min(100,100) = 100.

9	x	x	x	x	0
5	15	13	16	x	0
x	x	x	13	20	100 - 100 = 0
0	0	0	0	100 - 100 = 0	0

	1	2	3	4	5	Запасы
1	9[160]	21	8	12	17	160
2	5[10]	15[70]	13[100]	16[30]	18	210
3	16	22	12	13[60]	20[100]	160
Потребности	170	70	100	90	100

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

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

F(x) = 9*160 + 5*10 + 15*70 + 13*100 + 16*30 + 13*60 + 20*100 = 7100

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

9*160 + 5*10 + 15*70 + 13*100 + 16*30 + 13*60 + 20*100 = 7100

Этап II. Улучшение опорного плана.

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

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

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина ?ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки хij=1 от поставщика Аi к потребителю Вj.

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

Величина ?ij называется оценкой свободной клетки (или характеристика).

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

Необходимо вычислить значение оценок ?ij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).

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

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

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

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

Следующий этап решения транспортной задачи заключается в улучшении опорного плана.

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

Шаг 1. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[160][-]	21[+]	8	12	17	160
2	5[10][+]	15[70][-]	13[100]	16[30]	18	210
3	16	22	12	13[60]	20[100]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,2 > 1,1 > 2,1 > 2,2).

Оценка свободной клетки равна ?12 = (21) - (9) + (5) - (15) = 2.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[160][-]	21	8[+]	12	17	160
2	5[10][+]	15[70]	13[100][-]	16[30]	18	210
3	16	22	12	13[60]	20[100]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,3 > 1,1 > 2,1 > 2,3).

Оценка свободной клетки равна ?13 = (8) - (9) + (5) - (13) = -9.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[160][-]	21	8	12[+]	17	160
2	5[10][+]	15[70]	13[100]	16[30][-]	18	210
3	16	22	12	13[60]	20[100]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,4 > 1,1 > 2,1 > 2,4).

Оценка свободной клетки равна ?14 = (12) - (9) + (5) - (16) = -8.

(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[160][-]	21	8	12	17[+]	160
2	5[10][+]	15[70]	13[100]	16[30][-]	18	210
3	16	22	12	13[60][+]	20[100][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,5 > 1,1 > 2,1 > 2,4 > 3,4 > 3,5).

Оценка свободной клетки равна ?15 = (17) - (9) + (5) - (16) + (13) - (20) = -10.(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[160]	21	8	12	17	160
2	5[10]	15[70]	13[100]	16[30][-]	18[+]	210
3	16	22	12	13[60][+]	20[100][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (2,5 > 2,4 > 3,4 > 3,5).

Оценка свободной клетки равна ?25 = (18) - (16) + (13) - (20) = -5.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[160]	21	8	12	17	160
2	5[10][-]	15[70]	13[100]	16[30][+]	18	210
3	16[+]	22	12	13[60][-]	20[100]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,1 > 3,4 > 2,4 > 2,1).

Оценка свободной клетки равна ?31 = (16) - (13) + (16) - (5) = 14.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[160]	21	8	12	17	160
2	5[10]	15[70][-]	13[100]	16[30][+]	18	210
3	16	22[+]	12	13[60][-]	20[100]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,2 > 3,4 > 2,4 > 2,2).

Оценка свободной клетки равна ?32 = (22) - (13) + (16) - (15) = 10.

(3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[160]	21	8	12	17	160
2	5[10]	15[70]	13[100][-]	16[30][+]	18	210
3	16	22	12[+]	13[60][-]	20[100]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,3 > 3,4 > 2,4 > 2,3).

Оценка свободной клетки равна ?33 = (12) - (13) + (16) - (13) = 2.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (1,5;) равные: (-10).

Переход от неоптимального опорного плана к лучшему.

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

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	9[130]	21	8	12	17[30]	160
2	5[40]	15[70]	13[100]	16	18	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

9*130 + 17*30 + 5*40 + 15*70 + 13*100 + 13*90 + 20*70 = 6800

Шаг 2. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[130][-]	21[+]	8	12	17[30]	160
2	5[40][+]	15[70][-]	13[100]	16	18	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,2 > 1,1 > 2,1 > 2,2).

Оценка свободной клетки равна ?12 = (21) - (9) + (5) - (15) = 2.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[130][-]	21	8[+]	12	17[30]	160
2	5[40][+]	15[70]	13[100][-]	16	18	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,3 > 1,1 > 2,1 > 2,3).

Оценка свободной клетки равна ?13 = (8) - (9) + (5) - (13) = -9.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[130]	21	8	12[+]	17[30][-]	160
2	5[40]	15[70]	13[100]	16	18	210
3	16	22	12	13[90][-]	20[70][+]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,4 > 1,5 > 3,5 > 3,4).

Оценка свободной клетки равна ?14 = (12) - (17) + (20) - (13) = 2.

(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[130][+]	21	8	12	17[30][-]	160
2	5[40][-]	15[70]	13[100]	16[+]	18	210
3	16	22	12	13[90][-]	20[70][+]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (2,4 > 2,1 > 1,1 > 1,5 > 3,5 > 3,4).

Оценка свободной клетки равна ?24 = (16) - (5) + (9) - (17) + (20) - (13) = 10.(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[130][+]	21	8	12	17[30][-]	160
2	5[40][-]	15[70]	13[100]	16	18[+]	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (2,5 > 2,1 > 1,1 > 1,5).

Оценка свободной клетки равна ?25 = (18) - (5) + (9) - (17) = 5.(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[130][-]	21	8	12	17[30][+]	160
2	5[40]	15[70]	13[100]	16	18	210
3	16[+]	22	12	13[90]	20[70][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,1 > 3,5 > 1,5 > 1,1).

Оценка свободной клетки равна ?31 = (16) - (20) + (17) - (9) = 4.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[130][-]	21	8	12	17[30][+]	160
2	5[40][+]	15[70][-]	13[100]	16	18	210
3	16	22[+]	12	13[90]	20[70][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,2 > 3,5 > 1,5 > 1,1 > 2,1 > 2,2).

Оценка свободной клетки равна ?32 = (22) - (20) + (17) - (9) + (5) - (15) = 0. (3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[130][-]	21	8	12	17[30][+]	160
2	5[40][+]	15[70]	13[100][-]	16	18	210
3	16	22	12[+]	13[90]	20[70][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,3 > 3,5 > 1,5 > 1,1 > 2,1 > 2,3).

Оценка свободной клетки равна ?33 = (12) - (20) + (17) - (9) + (5) - (13) = -8.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (1,3;) равные: (-9).

Переход от неоптимального опорного плана к лучшему.

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

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	9[30]	21	8[100]	12	17[30]	160
2	5[140]	15[70]	13	16	18	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

9*30 + 8*100 + 17*30 + 5*140 + 15*70 + 13*90 + 20*70 = 5900

Шаг 3. Определяем оценку для каждой свободной клетки.

(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[30][-]	21[+]	8[100]	12	17[30]	160
2	5[140][+]	15[70][-]	13	16	18	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,2 > 1,1 > 2,1 > 2,2).

Оценка свободной клетки равна ?12 = (21) - (9) + (5) - (15) = 2.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[30]	21	8[100]	12[+]	17[30][-]	160
2	5[140]	15[70]	13	16	18	210
3	16	22	12	13[90][-]	20[70][+]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (1,4 > 1,5 > 3,5 > 3,4).

Оценка свободной клетки равна ?14 = (12) - (17) + (20) - (13) = 2.

(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[30][+]	21	8[100][-]	12	17[30]	160
2	5[140][-]	15[70]	13[+]	16	18	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (2,3 > 2,1 > 1,1 > 1,3).

Оценка свободной клетки равна ?23 = (13) - (5) + (9) - (8) = 9.

(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[30][+]	21	8[100]	12	17[30][-]	160
2	5[140][-]	15[70]	13	16[+]	18	210
3	16	22	12	13[90][-]	20[70][+]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (2,4 > 2,1 > 1,1 > 1,5 > 3,5 > 3,4).

Оценка свободной клетки равна ?24 = (16) - (5) + (9) - (17) + (20) - (13) = 10. (2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[30][+]	21	8[100]	12	17[30][-]	160
2	5[140][-]	15[70]	13	16	18[+]	210
3	16	22	12	13[90]	20[70]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (2,5 > 2,1 > 1,1 > 1,5).

Оценка свободной клетки равна ?25 = (18) - (5) + (9) - (17) = 5.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[30][-]	21	8[100]	12	17[30][+]	160
2	5[140]	15[70]	13	16	18	210
3	16[+]	22	12	13[90]	20[70][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,1 > 3,5 > 1,5 > 1,1).

Оценка свободной клетки равна ?31 = (16) - (20) + (17) - (9) = 4.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	Запасы
1	9[30][-]	21	8[100]	12	17[30][+]	160
2	5[140][+]	15[70][-]	13	16	18	210
3	16	22[+]	12	13[90]	20[70][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,2 > 3,5 > 1,5 > 1,1 > 2,1 > 2,2).

Оценка свободной клетки равна ?32 = (22) - (20) + (17) - (9) + (5) - (15) = 0. (3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	9[30]	21	8[100][-]	12	17[30][+]	160
2	5[140]	15[70]	13	16	18	210
3	16	22	12[+]	13[90]	20[70][-]	160
Потребности	170	70	100	90	100

Цикл приведен в таблице (3,3 > 3,5 > 1,5 > 1,3).

Оценка свободной клетки равна ?33 = (12) - (20) + (17) - (8) = 1.

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

Таким образом, последний опорный план является оптимальным.

Минимальные затраты составят: 9*30 + 8*100 + 17*30 + 5*140 + 15*70 + 13*90 + 20*70 = 5900

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

Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп--(m+n--1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 -- 361 цикл.

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (30), в 3-й магазин (100), в 5-й магазин (30)

Из 2-го склада необходимо груз направить в 1-й магазин (140), в 2-й магазин (70)

Из 3-го склада необходимо груз направить в 4-й магазин (90), в 5-й магазин (70)

1.2 Задача о назначениях

Исходная матрица имеет вид:

11	1	6	3	7
6	14	10	4	5
13	0	15	9	13
5	8	15	4	5
12	12	14	15	7

Шаг №1.

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

10	0	5	2	6	1
2	10	6	0	1	4
13	0	15	9	13	0
1	4	11	0	1	4
5	5	7	8	0	7

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

9	0	0	2	6
1	10	1	0	1
12	0	10	9	13
0	4	6	0	1
4	5	2	8	0
1	0	5	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем.

Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем.

Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем.

Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 4 и столбце 1 вычеркиваем.

Фиксируем нулевое значение в клетке (5, 5). Другие нули в строке 5 и столбце 5 вычеркиваем.

В итоге получаем следующую ...