Студент группа ди 13 21 тиловмуродов жавохир

Студент группа ДИ 13_21 ТИЛОВМУРОДОВ ЖАВОХИР
ВАРИАНТ №20
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен c₁₃=1. Для этого элемента запасы равны 166, потребности 104. Поскольку минимальным является 104, то вычитаем его.
x₁₃ = min(166,104) = 104.

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

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

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

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

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

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


Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*43 + 5*19 + 1*104 + 5*9 + 1*42 + 0*37 + 0*19 = 415
Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5
u₂ + v₂ = 5; 5 + u₂ = 5; u₂ = 0
u₃ + v₂ = 1; 5 + u₃ = 1; u₃ = -4
u₄ + v₂ = 0; 5 + u₄ = 0; u₄ = -5
u₄ + v₄ = 0; -5 + v₄ = 0; v₄ = 5
u₁ + v₃ = 1; 0 + v₃ = 1; v₃ = 1

все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 3*43 + 5*19 + 1*104 + 5*9 + 1*42 + 0*37 + 0*19 = 415
Из 1-го склада необходимо груз направить в 1-й магазин (43 ед.), в 2-й магазин (19 ед.), в 3-й магазин (104 ед.)
Из 2-го склада необходимо весь груз направить в 2-й магазин.
Из 3-го склада необходимо весь груз направить в 2-й магазин.
Потребность 2-го магазина остается неудовлетворенной на 37 ед.
Оптимальный план является вырожденным, так как базисная переменная x₄₂=0.
Потребность 4-го магазина остается неудовлетворенной на 19 ед.
Оптимальный план является вырожденным, так как базисная переменная x₄₄=0.