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

Составим математическую модель транспортной задачи.

(Из чего состоит математическая модель общей задачи ЛП?)

(Давайте запишем целевую функцию транспортной задачи?)

(2)

(Что можно сказать про переменные? Каким ограничениям они будут удовлетворять?)

Переменные должны удовлетворять ограничениям по запасам:

(3)

ограничениям по потребностям

(4)

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

(5)

Пример: В резерве железнодорожных станций A₁,A₂ и A₃ находится соответственно 100, 150 и 50 порожних вагонов, пригородных для перевозки зерна. Зерно находится в четырех пунктах, которым требуется 75, 80, 60 и 85 вагонов соответственно. Стоимость перегона одного вагона со станции А₁ в указанные пункты составляет 6, 7, 3 и 5 ден. ед., со станции A₂ - 1, 2, 5 и 6 ден. ед., со станции A₃ - 3, 10, 20 и 1 ден. ед. соответственно. Составить экономико-математическую модель задачи, пользуясь которой, можно найти вариант перегона вагонов со станций в пункты погрузки зерна, при котором общие затраты минимизируются.

Составим транспортную таблицу задачи (Учащиеся пытаются составить транспортную таблицу самостоятельно):

	(75)	(80)	(60)	(85)
(100)	6	7	3	5
(150)	1	2	5	6
(50)	3	10	20	1

Составим математическую модель данной задачи (Учащиеся пытаются составить математическую модель задачи самостоятельно):

Переменные должны удовлетворять ограничениям по запасам:

ограничениям по потребностям:

По смыслу переменных, они должны выражаться неотрицательными числами:

(Два учащихся выходят к доске - один записывает транспортную таблицу, другой - математическую модель задачи)

В. Опорный план транспортной задачи.

Структура опорного плана задачи:

Теорема. Ранг матрицы системы ограничительных уравнений транспортной задачи (2)-(5) на единицу меньше числа уравнений, т.е.

r=m+n-1.

(Сколько всего переменных имеет транспортная задача?) (mn)

Из теоремы следует, что каждый опорный план задачи имеет (Сколько базисных переменных?) m+n-1 базисных переменных и (Сколько свободных?) mn-(m+n-1) – свободных переменных, (Чему равны свободные переменные?) равных нулю.

Согласно сформулированной теореме, каждый опорный план будет «загружать» (Как вы думаете, что означает слово «Загружать») (Сколько клеток?) m+n-1 клеток, а остальные останутся свободными. Это не единственное требование к опорному плану. Второе связано с циклами в транспортной таблице.

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

Графическим изображением цикла является замкнутая ломаная линия, звенья которой расположены только в строках и столбцах таблицы. Каждое звено соединяет две и только две соседние клетки цикла.

Таким образом, план транспортной задачи является опорным тогда и только тогда, когда из занятых им m+n-1 клеток нельзя образовать ни одного цикла.

При решении транспортной задачи используются следующие этапы:

1. Построение начального опорного плана;

2. Оценка этого плана;

3. Переход от имеющегося опорного плана к новому плану с меньшими транспортными затратами.

(На основании выше сказанного, учащиеся в рабочей тетради пытаются самостоятельно построить опорный план задачи, записанной в транспортной таблице)