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

Рассмотрим закрытую транспортную задачу.

1. Неизвестными транспортной задачи являются - объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные так же можно записать в виде матрицы перевозок:

Таблица 13

Поставщики	Мощности (запасы) поставщиков	Потребители и их спрос
		…	n
		…
				…
				…
…	…
m				…

2.Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . Т.е. целевая функция будет иметь вид:

3. Система ограничений транспортной задачи состоит из двух групп уравнений.

4. Оптимальным решением транспортной задачи является матрица размерности :

Замечание. Запись математических моделей открытой и закрытой транспортной задачи в табличных редакторах Microsoft Excel и OpenOffice.org Calc осуществляется с помощью встроенных функций СУММ() (SUM()) и СУММПРОИЗВ() (SUMPRODUCT()). Мы рассмотрим это далее на примерах задачи 6 и задачи 8 (Л.Р. №5).

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

1. Нахождение исходного опорного решения;

2. Проверка полученного решения на оптимальность;

3. Переход от одного опорного решения к другому до достижения оптимального значения (минимума) целевой функции.

При решении ТЗ ее условие и исходное опорное решение записывается в распределительную таблицу. Клетки, в которых записан объем перевозки от i-го поставщика к j-му потребителю называются занятыми, им соответствуют базисные переменные опорного решения. Остальные, незанятые клетки называются пустыми и им соответствуют свободные переменные. В верхнем правом углу каждой клетки записывается тариф перевозки груза от данного i-го поставщика к j-му потребителю.

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

Для определения исходного опорного плана ТЗ существует несколько методов. Рассмотрим два из них: метод «северо-западного угла» и метод минимального элемента (метод наименьшей стоимости).

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

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

При нахождении опорного плана транспортной задачи методом «северо-западного угла» на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения.

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

Задача 6. На складах , , имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители , , должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Построить первоначальный допустимый опорный план закрепления потребителей за поставщиками. Найти оптимальный план закрепления потребителей за поставщиками, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей С в у.е.

Решение.Запишем исходные данные задачи в виде таблицы 14

Таблица 14

Поставщики	Запасы поставщиков	Потребители и их спрос

Математическая модель задачи

Матрица перевозок:

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

; ;

Целевая функция:

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

Запись математической модели данной транспортной задачи в табличном редакторе Microsoft Excel имеет вид (рисунок 13).

Р и с. 13.

1. Найдем исходное опорное решение методом «северо-западного угла»:

Таблица 15

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

Число занятых клеток в таблице равно 5, , т.е. условие невырожденности выполнено. Получим исходное опорное решение:

Стоимость перевозки (значение целевой функции) при исходном опорном решении составляет:

Метод минимального тарифа (элемента)

(метод наименьших затрат)

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

Найдем исходное опорное решение для задачи 6 методом минимального элемента:

Возможны два варианта (1) таблица 16, 2) таблица 17).

Таблица 16

- опорный план

Таблица 17

- опорный план

Задание

1. Для задачи 7 построить первоначальный допустимый опорный план с помощью метода «северо-западного угла» и метода минимального элемента.

Задача 7.Транспортная компания занимается перевозкой зерна специальными зерновозами от трех элеваторов к четырем мельницам. Возможности отгрузки зерна элеваторами (в зерновозах) составляет 15, 25, 10 соответственно, а потребности мельниц (так же в зерновозах) составляет 5, 15, 15, 15. Матрица стоимостей перевозок зерна одним зерновозом от i-го элеватора к j-ой мельнице имеет вид:

.

2. Записать математическую модель задачи 7 на листе Excel.

Контрольные вопросы

1. Какая цель ставится при решении транспортной задачи? К чему стремится целевая функция транспортной задачи?

2. Что означают коэффициенты у неизвестных в целевой функции транспортной задачи?

3. Какая транспортная задача называется закрытой?

4. Какая транспортная задача называется открытой?

5. Как называется таблица, с помощью которой находится решение транспортной задачи?

6. Как найти опорный план транспортной задачи методом "северо-западного угла"?

7. Как найти опорный план транспортной задачи методом минимального элемента?

Лабораторная работа №5