Учеба и наука

• Всего ответов: 2


Еva
6-й в Учебе и науке
4.9 399 отзывов
Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 2
Для этого элемента запасы равны 200, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x₂₂ = min(200,100) = 100.


4	x	5	6	100
8	2	4	7	200 — 100 = 100
50	100 — 100 = 0	75	75	0


Искомый элемент равен 4
Для этого элемента запасы равны 100, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x₁₁ = min(100,50) = 50.


4	x	5	6	100 — 50 = 50
x	2	4	7	100
50 — 50 = 0	0	75	75	0


Искомый элемент равен 4
Для этого элемента запасы равны 100, потребности 75. Поскольку минимальным является 75, то вычитаем его.
x₂₃ = min(100,75) = 75.


4	x	x	6	50
x	2	4	7	100 — 75 = 25
0	0	75 — 75 = 0	75	0


Искомый элемент равен 6
Для этого элемента запасы равны 50, потребности 75. Поскольку минимальным является 50, то вычитаем его.
x₁₄ = min(50,75) = 50.


4	x	x	6	50 — 50 = 0
x	2	4	7	25
0	0	0	75 — 50 = 25	0


Искомый элемент равен 7
Для этого элемента запасы равны 25, потребности 25. Поскольку минимальным является 25, то вычитаем его.
x₂₄ = min(25,25) = 25.


4	x	x	6	0
x	2	4	7	25 — 25 = 0
0	0	0	25 — 25 = 0	0




	1	2	3	4	Запасы
1	4[50]	8	5	6[50]	100
2	8	2[100]	4[75]	7[25]	200
Потребности	50	100	75	75

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n — 1 = 5. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 4*50 + 6*50 + 2*100 + 4*75 + 7*25 = 1175
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₁ + v₄ = 6; 0 + v₄ = 6; v₄ = 6
u₂ + v₄ = 7; 6 + u₂ = 7; u₂ = 1
u₂ + v₂ = 2; 1 + v₂ = 2; v₂ = 1
u₂ + v₃ = 4; 1 + v₃ = 4; v₃ = 3


	v1=4	v2=1	v3=3	v4=6
u1=0	4[50]	8	5	6[50]
u2=1	8	2[100]	4[75]	7[25]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.
Минимальные затраты составят:
F(x) = 4*50 + 6*50 + 2*100 + 4*75 + 7*25 = 1175
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (50), в 4-й магазин (50)
Из 2-го склада необходимо груз направить в 2-й магазин (100), в 3-й магазин (75), в 4-й магазин (25)
март 3, 2014 г.
Ответ понравился автору

Еva
6-й в Учебе и науке
4.9 399 отзывов
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен 4
Для этого элемента запасы равны 100, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x₁₁ = min(100,50) = 50.


4	8	5	6	100 — 50 = 50
x	2	4	7	200
50 — 50 = 0	100	75	75	0


Искомый элемент равен 8
Для этого элемента запасы равны 50, потребности 100. Поскольку минимальным является 50, то вычитаем его.
x₁₂ = min(50,100) = 50.


4	8	x	x	50 — 50 = 0
x	2	4	7	200
0	100 — 50 = 50	75	75	0


Искомый элемент равен 2
Для этого элемента запасы равны 200, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x₂₂ = min(200,50) = 50.


4	8	x	x	0
x	2	4	7	200 — 50 = 150
0	50 — 50 = 0	75	75	0


Искомый элемент равен 4
Для этого элемента запасы равны 150, потребности 75. Поскольку минимальным является 75, то вычитаем его.
x₂₃ = min(150,75) = 75.


4	8	x	x	0
x	2	4	7	150 — 75 = 75
0	0	75 — 75 = 0	75	0


Искомый элемент равен 7
Для этого элемента запасы равны 75, потребности 75. Поскольку минимальным является 75, то вычитаем его.
x₂₄ = min(75,75) = 75.


4	8	x	x	0
x	2	4	7	75 — 75 = 0
0	0	0	75 — 75 = 0	0




	1	2	3	4	Запасы
1	4[50]	8[50]	5	6	100
2	8	2[50]	4[75]	7[75]	200
Потребности	50	100	75	75

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n — 1 = 5. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 4*50 + 8*50 + 2*50 + 4*75 + 7*75 = 1525
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₁ + v₂ = 8; 0 + v₂ = 8; v₂ = 8
u₂ + v₂ = 2; 8 + u₂ = 2; u₂ = -6
u₂ + v₃ = 4; -6 + v₃ = 4; v₃ = 10
u₂ + v₄ = 7; -6 + v₄ = 7; v₄ = 13


	v1=4	v2=8	v3=10	v4=13
u1=0	4[50]	8[50]	5	6
u2=-6	8	2[50]	4[75]	7[75]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij
(1;3): 0 + 10 > 5; ∆₁₃ = 0 + 10 — 5 = 5
(1;4): 0 + 13 > 6; ∆₁₄ = 0 + 13 — 6 = 7
max(5,7) = 7
Выбираем максимальную оценку свободной клетки (1;4): 6
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».


	1	2	3	4	Запасы
1	4[50]	8[50][-]	5	6[+]	100
2	8	2[50][+]	4[75]	7[75][-]	200
Потребности	50	100	75	75

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


	1	2	3	4	Запасы
1	4[50]	8	5	6[50]	100
2	8	2[100]	4[75]	7[25]	200
Потребности	50	100	75	75

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₁ + v₄ = 6; 0 + v₄ = 6; v₄ = 6
u₂ + v₄ = 7; 6 + u₂ = 7; u₂ = 1
u₂ + v₂ = 2; 1 + v₂ = 2; v₂ = 1
u₂ + v₃ = 4; 1 + v₃ = 4; v₃ = 3


	v1=4	v2=1	v3=3	v4=6
u1=0	4[50]	8	5	6[50]
u2=1	8	2[100]	4[75]	7[25]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.
Минимальные затраты составят:
F(x) = 4*50 + 6*50 + 2*100 + 4*75 + 7*25 = 1175
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (50), в 4-й магазин (50)
Из 2-го склада необходимо груз направить в 2-й магазин (100), в 3-й магазин (75), в 4-й магазин (25)
март 3, 2014 г.

Похожие вопросы