- •Раздел 3. Специальные методы решения транспортной задачи
- •3.1 Постановка транспортной задачи и построение математической модели
- •3.2 Открытая и закрытая модели транспортной задачи (тз)
- •3.3 Необходимость специальных методов для решения тз.
- •Практическая задача
- •Нахождение опорного и оптимального плана в тт. Количество переменных в тт и их характеристика.
- •3.5 Методы нахождения опорного плана (первоначального, допустимого, базисного)
- •3.5.1 Метод северо-западного угла
- •3.5.2 Метод минимального элемента (тарифа)
- •3.5.3 Метод двойного предпочтения (минимальных затрат, минимального тарифа с двойным предпочтением)
- •3.6 Вырожденность плана тз
- •3.7 Нахождение оптимального плана тз (оптимального решения)
- •3.7.1 Цикл пересчета тт для нахождения оптимального плана
- •3.7.2 Распределительный метод нахождения оптимального плана тз
- •Практическое решение задач распределительным методом
- •Решение открытых тз
- •Практическое решение открытых тз
- •Метод потенциалов для нахождения оптимального решения тз (метод потенциалов)
- •Экономическая интерпретация. Понятие платежей и псевдостоимостей
- •Особые случаи при решении тз
- •Неединственность решения тз
- •Раздел 4. Графовые модели. Алгоритмы на графах
- •4.1 Теория графов и ее применение
- •4.2 Основные определения графов
- •4.3 Типы графов
- •4.4 Маршруты и связность
- •4.5 Деревья
- •4.6 Сети
- •4.7 Математическое представление графов. (Методы хранения графов в памяти пк)
- •4.8 Нахождение кратчайших путей в графе
Раздел 3. Специальные методы решения транспортной задачи
3.1 Постановка транспортной задачи и построение математической модели
Общая экономическая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления в A 1, A 2,…, Am в n пунктов назначения B1, B2, …, Bn.
Груз хранится в пунктах отправления в количествах a1, a2,…, am.
Пункты назначения подали заявки на груз в количествах b1, b2,…bn .
Кроме того, задается матрица тарифов перевозок C
C =
Или в общем, виде эту матрицу можно записать C=(Cij) (i=1..m, j=1..n).
Критерием оптимальности является минимальная стоимость перевозок всего груза (чаще всего), а иногда минимальное время его доставки (транспортная задача по критерию времени).
Математическое построение модели.
Обозначим матрицу решений транспортной задачи X=(xij) i=1..m, j=1..n, где xij – количество груза перевозимого из i–пункта отправления Ai в j – пункт назначения Bj.
Матрица X - матрица поставок (перевозок груза) или план поставок (перевозок).
Аналогично матрица C называется матрицей тарифов перевозок или просто матрицей тарифов.
Система линейных ограничений (СЛО) составляется из выполнения следующих условий:
Запасы грузов в каждом пункте отправления ограничены.
i=1..m
Заявки всех пунктов назначения должны быть выполнены.
j=1..n
Целевая функция по критерию минимальной стоимости общей стоимости перевозок имеет вид:
(min)
i=1..m, j=1..n – по экономическому смыслу задачи количество груза не может быть отрицательным.
Пункты 1-4 составляют модель линейного программирования, т.к. СЛО (1),(2)-линейная и целевая функция Z (п.3) тоже линейная функция.
Модель читается:
Среди не отрицательных решений (4) найти такие, которые удовлетворяли бы СЛО (1),(2) и обращали целевую функцию (3) в минимум.
Всякое не отрицательное решение СЛО (1),(2) определяется матрицей значений X=(xij) i=1..m j=1..n и называется допустимым решением (опорным) транспортной задачи или допустимым (опорным) планом.
Оптимальный план X*=(x*ij) i=1..m, j=1..n – это тот из опорных планов, при котором целевая функция (3) принимает минимальное значение.
Решить транспортную задачу – значит найти ее оптимальный план (или оптимальное решение).
3.2 Открытая и закрытая модели транспортной задачи (тз)
Если запасы грузов в пунктах отправления равняются общей потребности в них в пунктах назначения, т.е. математически = , то модель такой ТЗ называется закрытой моделью или говорят, это ТЗ с правильным балансом.
Если же запаса грузов больше, чем требуется пунктам назначения, т.е. математически > , то модель называется открытой моделью или говорят, это ТЗ с неправильным балансом.
При решении такой открытой задачи ее сводят к закрытой модели путем введения фиктивного пункта назначения Bn+1 с потребностью (заявкой) bn+1 = - .
Соответственно тарифы перевозок в этот фиктивный пункт назначения считаются = 0, т.е. по существу грузы не перевозятся, а остаются в пунктах отправления.
Существует и открытая модель другого типа, когда сумма заявок пунктов потребления превышает имеющиеся запасы пунктов (назначения) отправления.
В этом случае говорят о фиктивном пункте отправления Am+1 с запасом груза am+1 = - .
Тарифы перевозок из фиктивного пункта отправления также = 0,это означает, что такой груз вообще не доставляется потребителю, т.е. его заявка не выполняется на это количество грузов.
Переход от открытой модели к закрытой означает приведение ТЗ к каноническому виду.
Так как в канонической форме (закрытой модели) сумма заявок всегда равняется сумме грузов на складах, то в СЛО (1), (2) будут только равенства, а каноническая форма в общей теории линейного программирования тем и характерна, что в СЛО имеются только равенства (уравнения).
Отличием (исключением) является лишь то, что целевая функция Z в канонической форме ТЗ в отличие от общей постановки канонической формы ЗЛП минимизируется.