1.Экономико-математическая модель транспортных задач

3 поставщика – A_i, 4 потребителя – B_j.

Мощность поставщика – количество товара у этого поставщика (A_i). Мощность потребителя – спрос потребителя (B_j).

C_ij – коэффициент затрат, затраты на перевозку 1 единицы груза от i поставщика к j потребителю.

		B1	B2	B3	B4
	280	20	110	40	110
A1	60	1	2	5	3
		x11	x12	x13	x14
A2	120	1	6	5	2
		x21	x22	x23	x24
A3	100	6	3	7	4
		x31	x32	x33	x34

Найти план перевоза (т.е. объем перевоза для каждой пары поставщик - потребитель) чтобы: 1.мощности всех поставщиков были реализованы; 2.спрос всех поставщиков был удовлетворен; 3.затраты на перевозку были минимальны.

X_ij≥0; X_ij – объем перевозки A_i к B_j. Целевая функция Z(x) суммарные затраты: x₁₁+2x₁₂+5x₁₃+3x₁₄+x₂₁+6x₂₂+5x₂₃+2x₂₄+6x₃₁+3x₃₂+7x₃₃+4x₃₄→min

Система ограничений:

x11+x12+x13+x14=60; x21+x22+x23+x24=120; x31+x32+x33+x34=100;

x11+x21+x31=20; x12+x22+x32=110; x13+x23+x33=40; x14+x24+x34=110;

Транспортная задача – частный метод ЗЛП. Система ограничений представляет собой систему уравнений. Решение: находим опорное решение (допустимое), разрабатываем критерий оптимальности или другое решение.

2.Общая формулировка тз

m – поставщики; n – потребители.

Целевая функция Z(x)= (1)

условие баланса

X=	x11	x12	x13
	x21	x22	x23
	x31	x32	x33

удовлетворяет (2,3,4), при котором (1) принимает минимальное значение. Любое допустимое значение (2,3,4) – распределение поставок. Если (5) выполняется, то ТЗ называется сбалансированной, закрытой, в противном случае несбалансированной, открытой.

3.Теор. (о ранге сис-мы ограниченной закр. Тз) и следствие из нее. Открытая тз

Любое допустимое значение – распределение поставок.

Если выполняется, то ТЗ называется сбалансированной, закрытой, в противном случае несбалансированной, открытой.

Рангом системы (число линейно зависимых уравнений)(1), (2) при условии (3) равен r=m+n-1. Любое распределение поставок соответствует базисное решение системы (1), (2). m+n-1 – базисных переменных. m+n-1>0;оставшиеся переменные – свободные переменные равны нулю.

Открытая транспортная задача (суммарная мощность A_i не совпадает с суммарной мощностью B_j) Вводится или фиктивный поставщик или фиктивный потребитель с нулевым коэффициентом затрат. При заполнении планом минимальных затрат нули не учитываются и заполняются в последнюю очередь.

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

Z(x)↑ - плохо; ∆_ij>0. Z(x)↓ - хорошо – наша цель∆_ij<0.

Оценка клетки (i, j), ∆_ij:

X = {x_ij} – оптимальное, если оценки всех свободных клеток не отрицательны. Если хотя бы одна оценка отрицательна, то решение не оптимально. Для пересчета таблицы составляется цикл. Цикл пересчета: начинается в свободной клетке и заканчивается в ней же, все остальные базисные. Все повороты в базисных клетках под 90 градусов. Ломанная цикла замкнута. Оценка свободной клетки равна приращению суммарных затрат на перевозку, если дать в эту клетку единичную поставку.