76. Математическая модель транспортной задачи: открытая и закрытая виды моделей.

Пусть имеется m поставщиков, располагающих объемом продукции a_i (i=1,m) и n получателей с объемами потребления b_j (j=1,n). c_ij - стоимость перевозки единицы продукции от i-поставщика к j-потребителю. Необходимо составить план перевозок x, при кот. суммарные затраты min и полностью удовл-ся запросы потребителей.

	В1	В2	…	Вn	Запас, ai
А1	c11 x11	c12 x12	…	c1n x1n	a1
А2	c21 x21	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Аm	cm1 xm1	cm2 xm2	…	cmn xmn	am
Потребность, bj	b1	b2	…	bn

Если , то задача наз-ся закрытой. Иначе - открытая.

Матем. модель закрытой задачи:

Ограничения:

- на запасы продукции у поставщиков

- на запросы потребителей

- условие неотрицательности

Если задача открытая, то ее приводят к закрытому виду, возможны 2 случая:

1) запасы поставщиков > потребностей потребителей :

вводят фиктивного потребителя с номером n+1 c запросами , тарифы c_in+1 считаются = 0. Получим расширенную закрытую задачу. Ее оптим. план даст оптим. план исходной задачи. Поставки x_{i n+1} покажут сотатки продукции на складе поставщиков.

2) потребности > запасов :

вводят m+1 фиктивного поставщика. Его запасы равны недостающей продукции , тарифы c_m+1j равны некоторому большому положительному числу М. Поставки x_m+1j покажут объемы недостающей продукции.

77. Построение начального опорного плана транспортной задачи: методы северо-западного угла и минимального элемента.

Метод северо-западного угла.

	В1	В2	…	Вn	Запас, ai
А1	c11 x11	c12 x12	…	c1n x1n	a1
А2	c21 x21	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Аm	cm1 xm1	cm2 xm2	…	cmn xmn	am
Потребность, bj	b1	b2	…	bn

Построение нач. опорного плана начинается с клетки (1,1).

а) если , то , т.е. запросы 1-го потребителя будут полностью удовлетворены. В дальнейшем 1-ый столбец таблицы в расчет не принимается и все переменные в нем x_i1 = 0 (i=2,m).

Двигаясь вправо по 1-ой строке заносим в клетку (1,2) меньшее из чисел (a₁-b₁) и b₂. Когда запасы 1-го поставщика будут исчерпаны, то дальнейшие расчеты производят по 2-ой строке и т.д.

б) если , то , т.е. запас 1-го поставщика будет полностью исчерпан, поэтому x_1j = 0 (j=2,n).

1-ая строка исключается из дальнейшего рассмотрения. Аналогичные расчеты производят во всех остальных строках.

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

Недостаток метода: при построении плана перевозок не учитывается матрица тарифов, поэтому он может оказаться далеко от оптимального.

Метод минимального элемента.

Здесь рассматриваются тарифы и в 1-ю очередь заполняется клетка с min значением тарифа. При этом в клетку записывается max возможное значение объема поставки. Затем из рассмотрения исключают строку, соотв. поставщику, запасы кот. полностью израсходованы, или столбец, соотв. потребителю, спрос кот. полностью удовлетворен.

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

В рез-те получаем опорный план, кот. должен содержать m+n-1 заполненных клеток. В процессе заполнения таблицы могут быть одновременно исключены столбец и строка. Тогда полученный опорный план будет вырожденным, т.к. не будет выполн-ся условие кол-ва занятых клеток m+n-1. В этом случае необх. в своб. клетку записать кол-во груза 0, условно считая эту клетку занятой («ноль-загрузка»). Число 0 записыв-ся в те свободные клетки, кот. не образуют циклов с ранее занятыми клетками. Циклом в матрице назыв-ся непрерывная замкнутая ломаная линия, вершины кот. находятся в клетках матрицы, а звенья расположены вдоль строк и столбцов. Если цикл образуется самопересекающейся ломаной, то точки ее самопересечения вершин не образуют. Число вершин в цикле д.б. четным; одна вершина -свободная клетка, остальные – занятые.