Транспортная задача - Основы экономико-математического моделирования

На трех складах А1, А2 и А3 хранится А1=100, А2=200, а3=60+10N единиц одного и того же груза, соответственно. Этот груз требуется доставить трем потребителям В1, В2 и В3, заказы которых B1=190, B2=120,B3=10MЕдиниц груза, соответственно. Стоимости перевозок CIjЕдиницы груза с I-го складаJ-му потребителю указаны в соответствующих клетках транспортной таблицы:

Потребности Запасы	В1	В2	В3
B1=190	B2=120	B3=10m
А1	А1=100	4	2	M
А2	А2=200	N	5	3
А3	А3=60+10n	1	M + 1	6

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

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

Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.

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

1	2	3	Запасы
1	4	2	5	100
2	1	5	3	200
3	1	6	6	70
Потребности	190	120	50

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

? a = 100 + 200 + 70 = 370 ? b = 190 + 120 + 50 = 360

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 10 (370--360).

Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

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

1	2	3	4	Запасы
1	4	2	5	0	100
2	1	5	3	0	200
3	1	6	6	0	70
Потребности	190	120	50	10

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.

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

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

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

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

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

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

X11 = min(100,190) = 100.

4	X	X	X	100 - 100 = 0
1	5	3	0	200
1	6	6	0	70
190 - 100 = 90	120	50	10	0

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

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

X21 = min(200,90) = 90.

4	X	X	X	0
1	5	3	0	200 - 90 = 110
X	6	6	0	70
90 - 90 = 0	120	50	10	0

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

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

X22 = min(110,120) = 110.

4	X	X	X	0
1	5	X	X	110 - 110 = 0
X	6	6	0	70
0	120 - 110 = 10	50	10	0

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

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

X32 = min(70,10) = 10.

4	X	X	X	0
1	5	X	X	0
X	6	6	0	70 - 10 = 60
0	10 - 10 = 0	50	10	0

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

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

X33 = min(60,50) = 50.

4	X	X	X	0
1	5	X	X	0
X	6	6	0	60 - 50 = 10
0	0	50 - 50 = 0	10	0

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

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

X34 = min(10,10) = 10.

4	X	X	X	0
1	5	X	X	0
X	6	6	0	10 - 10 = 0
0	0	0	10 - 10 = 0	0

1	2	3	4	Запасы
1	4[100]	2	5	0	100
2	1[90]	5[110]	3	0	200
3	1	6[10]	6[50]	0[10]	70
Потребности	190	120	50	10

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

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

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

F(x) = 4*100 + 1*90 + 5*110 + 6*10 + 6*50 + 0*10 = 1400

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

4*100 + 1*90 + 5*110 + 6*10 + 6*50 + 0*10 = 1400

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1	2	3	4	Запасы
1	4[100][-]	2[+]	5	0	100
2	1[90][+]	5[110][-]	3	0	200
3	1	6[10]	6[50]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д12 = (2) - (4) + (1) - (5) = -6.

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

1	2	3	4	Запасы
1	4[100][-]	2	5[+]	0	100
2	1[90][+]	5[110][-]	3	0	200
3	1	6[10][+]	6[50][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д13 = (5) - (4) + (1) - (5) + (6) - (6) = -3.

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

1	2	3	4	Запасы
1	4[100][-]	2	5	0[+]	100
2	1[90][+]	5[110][-]	3	0	200
3	1	6[10][+]	6[50]	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д14 = (0) - (4) + (1) - (5) + (6) - (0) = -2.

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

1	2	3	4	Запасы
1	4[100]	2	5	0	100
2	1[90]	5[110][-]	3[+]	0	200
3	1	6[10][+]	6[50][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д23 = (3) - (5) + (6) - (6) = -2.

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

1	2	3	4	Запасы
1	4[100]	2	5	0	100
2	1[90]	5[110][-]	3	0[+]	200
3	1	6[10][+]	6[50]	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д24 = (0) - (5) + (6) - (0) = 1.

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

1	2	3	4	Запасы
1	4[100]	2	5	0	100
2	1[90][-]	5[110][+]	3	0	200
3	1[+]	6[10][-]	6[50]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д31 = (1) - (6) + (5) - (1) = -1.

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

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

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

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190]	5[10]	3	0	200
3	1	6[10]	6[50]	0[10]	70
Потребности	190	120	50	10

2*100 + 1*190 + 5*10 + 6*10 + 6*50 + 0*10 = 800

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

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

1	2	3	4	Запасы
1	4[+]	2[100][-]	5	0	100
2	1[190][-]	5[10][+]	3	0	200
3	1	6[10]	6[50]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д11 = (4) - (2) + (5) - (1) = 6.

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

1	2	3	4	Запасы
1	4	2[100][-]	5[+]	0	100
2	1[190]	5[10]	3	0	200
3	1	6[10][+]	6[50][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д13 = (5) - (2) + (6) - (6) = 3.

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

1	2	3	4	Запасы
1	4	2[100][-]	5	0[+]	100
2	1[190]	5[10]	3	0	200
3	1	6[10][+]	6[50]	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д14 = (0) - (2) + (6) - (0) = 4.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190]	5[10][-]	3[+]	0	200
3	1	6[10][+]	6[50][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д23 = (3) - (5) + (6) - (6) = -2.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190]	5[10][-]	3	0[+]	200
3	1	6[10][+]	6[50]	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д24 = (0) - (5) + (6) - (0) = 1.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190][-]	5[10][+]	3	0	200
3	1[+]	6[10][-]	6[50]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д31 = (1) - (6) + (5) - (1) = -1.

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

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

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

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190]	5	3[10]	0	200
3	1	6[20]	6[40]	0[10]	70
Потребности	190	120	50	10

2*100 + 1*190 + 3*10 + 6*20 + 6*40 + 0*10 = 780

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

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

1	2	3	4	Запасы
1	4[+]	2[100][-]	5	0	100
2	1[190][-]	5	3[10][+]	0	200
3	1	6[20][+]	6[40][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д11 = (4) - (2) + (6) - (6) + (3) - (1) = 4.

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

1	2	3	4	Запасы
1	4	2[100][-]	5[+]	0	100
2	1[190]	5	3[10]	0	200
3	1	6[20][+]	6[40][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д13 = (5) - (2) + (6) - (6) = 3.

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

1	2	3	4	Запасы
1	4	2[100][-]	5	0[+]	100
2	1[190]	5	3[10]	0	200
3	1	6[20][+]	6[40]	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д14 = (0) - (2) + (6) - (0) = 4.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190]	5[+]	3[10][-]	0	200
3	1	6[20][-]	6[40][+]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д22 = (5) - (3) + (6) - (6) = 2.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190]	5	3[10][-]	0[+]	200
3	1	6[20]	6[40][+]	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д24 = (0) - (3) + (6) - (0) = 3.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[190][-]	5	3[10][+]	0	200
3	1[+]	6[20]	6[40][-]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д31 = (1) - (6) + (3) - (1) = -3.

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

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

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

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[150]	5	3[50]	0	200
3	1[40]	6[20]	6	0[10]	70
Потребности	190	120	50	10

2*100 + 1*150 + 3*50 + 1*40 + 6*20 + 0*10 = 660

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

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

1	2	3	4	Запасы
1	4[+]	2[100][-]	5	0	100
2	1[150]	5	3[50]	0	200
3	1[40][-]	6[20][+]	6	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д11 = (4) - (2) + (6) - (1) = 7.

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

1	2	3	4	Запасы
1	4	2[100][-]	5[+]	0	100
2	1[150][+]	5	3[50][-]	0	200
3	1[40][-]	6[20][+]	6	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д13 = (5) - (2) + (6) - (1) + (1) - (3) = 6.

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

1	2	3	4	Запасы
1	4	2[100][-]	5	0[+]	100
2	1[150]	5	3[50]	0	200
3	1[40]	6[20][+]	6	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д14 = (0) - (2) + (6) - (0) = 4.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[150][-]	5[+]	3[50]	0	200
3	1[40][+]	6[20][-]	6	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д22 = (5) - (1) + (1) - (6) = -1.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[150][-]	5	3[50]	0[+]	200
3	1[40][+]	6[20]	6	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д24 = (0) - (1) + (1) - (0) = 0.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[150][+]	5	3[50][-]	0	200
3	1[40][-]	6[20]	6[+]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д33 = (6) - (1) + (1) - (3) = 3.

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

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

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

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[130]	5[20]	3[50]	0	200
3	1[60]	6	6	0[10]	70
Потребности	190	120	50	10

2*100 + 1*130 + 5*20 + 3*50 + 1*60 + 0*10 = 640

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

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

1	2	3	4	Запасы
1	4[+]	2[100][-]	5	0	100
2	1[130][-]	5[20][+]	3[50]	0	200
3	1[60]	6	6	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д11 = (4) - (2) + (5) - (1) = 6.

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

1	2	3	4	Запасы
1	4	2[100][-]	5[+]	0	100
2	1[130]	5[20][+]	3[50][-]	0	200
3	1[60]	6	6	0[10]	70
Потребности	190	120	50	10

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

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

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

1	2	3	4	Запасы
1	4	2[100][-]	5	0[+]	100
2	1[130][-]	5[20][+]	3[50]	0	200
3	1[60][+]	6	6	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д14 = (0) - (2) + (5) - (1) + (1) - (0) = 3.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[130][-]	5[20]	3[50]	0[+]	200
3	1[60][+]	6	6	0[10][-]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д24 = (0) - (1) + (1) - (0) = 0.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[130][+]	5[20][-]	3[50]	0	200
3	1[60][-]	6[+]	6	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д32 = (6) - (1) + (1) - (5) = 1.

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

1	2	3	4	Запасы
1	4	2[100]	5	0	100
2	1[130][+]	5[20]	3[50][-]	0	200
3	1[60][-]	6	6[+]	0[10]	70
Потребности	190	120	50	10

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

Оценка свободной клетки равна Д33 = (6) - (1) + (1) - (3) = 3.

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

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

Минимальные затраты составят:

2*100 + 1*130 + 5*20 + 3*50 + 1*60 + 0*10 = 640

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

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

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

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

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

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

На 3-ом складе остался невостребованным груз в количестве 10 ед.

Оптимальный план является вырожденным, так как базисная переменная x34=0.

Похожие статьи

• Решение транспортной задачи. Нахождение опорного плана тремя методами, Метод минимального элемента - Математическое моделирование в менеджменте и маркетинге

  A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...

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

  Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...

• Пример решения транспортной задачи - Экономико-математические методы

  На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...

• Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге

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

• Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи

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

• Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы

  Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...

• Задача линейного программирования - Основы экономико-математического моделирования

  Предприятие планирует выпуск продукции I и II видов, на производство которых расходуется три вида сырья А , В И С . Потребность A Ij I -го вида сырья для...

• Оценка времени поездки на основе моделирования транспортных потоков

  Оценка времени поездки на основе моделирования транспортных потоков С. Н.Козорезова Постоянное увеличение количества транспортных заторов на...

• Введение - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

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

• Пример транспортной задачи линейного программирования - Оптимальное программирование

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

• МНОГОГРАННИКИ - Основы моделирования геометрических объектов

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

• Классификация экономико-математических методов и моделей в управлении предприятием и их задачи в повышении экономической эффективности производства, Основные понятия теории экономико-математического моделирования, Кибернетический подход к исследованию экономико-математических систем - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...

• Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы

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

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

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

• Литература - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

  1. Золотарев А. А. Математическое моделирование и оптимизация распределительных систем. Saarbrucken: LAP Lambert Academic Publishing, 2016. 184 с. 2....

• Цели и задачи эконометрики - Основы эконометрии

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

• Моделирование в условиях противодействия, игровые модели - Основы теории систем и системного анализа

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

• Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами

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

• Задача, Список используемой литературы - Основы статистики

  > Рассчитать средний процент выполнения плана по трем предприятиям, если известно: Предприятие % выполнения плана Удельный вес предприятия плановом...

• Погрешности оценивания по ACL-шкале, Применение ACL-шкалы - Моделирование лингвистических оценок на основе ACL-шкалы

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

• Модель лингвистической ACL-шкалы - Моделирование лингвистических оценок на основе ACL-шкалы

  Формально шкалой называется кортеж из трех элементов, где реальный объект со свойствами xI, на которых задано отношение RX, определяет шкалу как знаковую...

• ТИПЫ ЗАДАЧ НАЧЕРТАТЕЛЬНОЙ ГЕОМЕТРИИ - Основы моделирования геометрических объектов

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

• Компьютерное решение поставленной задачи рационального распределения ресурсов - Математическое моделирование в лесной промышленности

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

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

  В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....

• Моделирование одномерных временных рядов - Моделирование на основе парной регрессии и корреляции. Моделирование одномерных временных рядов

  По данным динамики валют (вариант 14) выявить трендовую, периодическую и случайную составляющие ряда (T, S,E), оценить качество модели, сделать прогноз...

• Свертка скалярных критериев и условия компромисса - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

  Пусть ограничения (4) не противоречивы, т. е. не пусто множество допустимых решений, а оптимальное решение достигается я в точке для каждой K -ой...

• Оценка существенности параметров уравнения множественной регрессии и корреляции - Моделирование на основе парной регрессии и корреляции. Моделирование одномерных временных рядов

  Множественная регрессия - уравнение связи с несколькими независимыми переменными: где - зависимая переменная (результативный признак); - независимые...

• Использование современных информационно-коммуникационных технологий. Задачи использования - Компьютерное моделирование физических процессов и явлений, как метод научного познания

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

• История развития экономико-математического моделирования в США - История развития методов и моделей в экономике

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

• Процесс создания модели на основе классического и системного подходов - Сущность метода статистического моделирования

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

• Классификация систем эконометрических уравнений, различие содержательной интерпретации - Моделирование на основе парной регрессии и корреляции. Моделирование одномерных временных рядов

  В состав системы эконометрических уравнений входят множество зависимых или эндогенных переменных и множество предопределенных переменных (лаговые и...

• Исходные данные - Задача оптимизации городской транспортной сети

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

• Задание на лабораторную работу - Задача оптимизации городской транспортной сети

  Создать и оптимизировать в Microsoft Excel табличную модель задачи оптимизации городской транспортной сети. Табл. 1 Номер варианта Номера вершин 8 1 - 8,...

• Охарактеризуйте внешние для предприятия факторы, влияющие на принятие решений в задаче закупочной логистике"сделать или купить" - Основы логистики

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

• Введение - Методы экономико-математического моделирования

  Экономико-математическое моделирование является неотъемлемой частью любого исследования в области экономики. Бурное развитие математического анализа,...

• Этапы экономико-математического моделирования - Методы экономико-математического моделирования

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

• Заключение - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов

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

• Прогнозирование на основе нейронных сетей - Использование нейродинамики для моделирования производственных процессов предприятия

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

• Процесс экономико-математического моделирования - Экономико-математические методы

  Этот процесс состоит из нескольких взаимосвязанных этапов. Разбиение на этапы и выделение на каждом этапе присущих ему процессов условно: на одном из...

• Прогностическое управление на основе нейросетевой модели системы - Использование нейродинамики для моделирования производственных процессов предприятия

  Программное управление является приемлемым подходом во многих прикладных ситуациях. На этом принципе основаны, например, простые металлорежущие станки...

Транспортная задача - Основы экономико-математического моделирования

Предыдущая | Следующая