Постановка тз по критерию стоимости в матричной форме.

Формулировка ТЗ. В m пунктах отправления A₁, A₂, …, A_m сосредоточен однородный груз в количествах a₁, a₂, a_m. Этот груз необходимо доставить потребителям B₁, B₂, …, B_n, спрос каждого потребителя выражается в единицах b₁, b₂, …, b_n. Известна стоимость c_ij перевозки груза из i-го пункта в j-й.

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

Пункт отправления	Потребитель				Запас груза в пункте отправления
	B1	B2	…	Bm
	Затраты на перевозку груза
A1	c11	c12	…	c1n	a1
	x11	x12		x1n
A2	c21	c22	…	c2n	a2
	x21	x22		x2n
…	…	…	...	…	…
An	cm1	cm2	…	cmn	am
	xm1	xm2		xmn
	b1	b2	…	bn

Рассмотрим матрицу: X=[x_ij]_mn, где x_ij – количество единиц груза, который необходимо доставить из i-го пункта отправления в j-й пункт назначения. Эту матрицу назовем матрицей перевозок, где x_ij0.

Транспортные издержки запишем в виде матрицы тарифов: C=[c_ij].

Для наглядности ТЗ будем представлять в виде распределительной таблицы.

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

Цель ТЗ. Минимизировать общие затраты на реализацию плана перевозок.

В матричной форме ТЗ запишется:

x_ij0

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

Теорема о существовании допустимого плана

Для того чтобы ТЗ имела допустимые планы необходимо и достаточно выполнение равенства .

Открытая и закрытая модели ТЗ

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

Открытую модель ТЗ при решении нужно привести к закрытой. Для этого в

первом случае вводят фиктивного потребителя B_n+1, спрос фиктивного потребителя равен

;

во втором случае вводят фиктивного поставщика A_m+1, тогда груз этого поставщика равен

,

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

Теорема о ранге матрицы ТЗ

Ранг матрицы ограничений на единицу меньше числа уравнений.

Построение исходного опорного плана

Построение опорного плана будем производить по одним из следующих правил:

1. правило северо-западного угла;

2. правило минимального элемента;

3. метод Фогеля.

Правило 1.

Пользуясь распределительной таблицей, будем распределять груз, начиная с левой верхней клетки (1,1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1,1) внесем меньшее из чисел b₁ и a₁: x₁ = min(a₁, b₁). Если a₁>b₁, то в клетку внесем b₁, и первый потребитель будет полностью удовлетворен. В дальнейшем первый столбец не рассматривается. Если a₁<b₁, то x₁₁=a₁, т.е. запас первого поставщика исчерпан, и переходим к распределению запасов второго поставщика. В клетку (2,1) вносим наименьшее из чисел a₂ и b₁-a₁ и т.д.

Если спрос потребителей удовлетворен, а запас поставщика исчерпан, то соответственно столбец или строка выпадают из рассмотрения.

Район	Элеватор			Запас зерна
	B1	B2	B3
A1	3	5	6	800
	800	-	-
A2	7	2	4	700
	200	500	-
A3	4	3	5	1000
	-	600	400
A4	6	4	7	500
	-	-	500
	1000	1100	900

Составить план перевозок зерна из 4-х районов, в которых запасы составляют соответственно: 800, 700, 1000, 500 тыс. центнеров зерна, на три элеватора, мощность которых: 1000, 1100, 900 тыс. центнеров. Затраты на перевозку единицы груза определяются по таблице.

r (ранг матрицы) = m + n – 1 = 6, заполненных ячеек также 6,  план допустим.

f(x) = 3*800 + 7*200 + 2*500 + 3*600 + 5*400 + 7*500 = 12100.