Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
рием крайнего пессимизма. Значение выбирается субъективно: чем больше желание подстраховаться, тем ближе к 1 должно быть .
Лекция 9
Транспортная задача
Вопросы:
1.Постановка транспортной задачи. Закрытая модель. Теорема о существовании решения.
2.Метод потенциалов: а) построение опорного плана; б) схема решения.
.Метод дифференциальных рент.
.Дополнительные ограничения транспортной задачи.
1.Постановка транспортной задачи. Закрытая модель. Теорема о существовании решения
Транспортная задача является одним из наиболее важных частных случаев общей задачи линейного программирования, в силу специфики ее построения и области применения. Транспортная модель изначально предназначена для выбора наиболее экономного планирования грузопотоков и работы различных видов транспорта. Однако сфера применения транспортной модели этим не ограничивается. Примерами использования транспортной модели могут служить задачи календарного планирования производства, рационального использования природных и людских ресурсов и др.
Пусть в пунктах А1,А2,...,Аm производится некоторый продукт, причем объем производства в п. Аi составляет ai единиц, . Произведенный про-дукт должен быть доставлен в пункты потребления В1,В2,...,Вn, причем объем потребления в п. Вj составляет bj единиц, . Предполагается, что тран-спортировка готовой продукции возможна из любого пункта производства в лю-бой пункт потребления, транспортные издержки на перевозку единицы продукции из п. Аi в п. Вj составляют cij денежных единиц. Задача состоит в организа-ции такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.
Математически транспортная задача может быть записана следующим образом. Пусть xij - количество продукта, перевозимого из п. Аi в п. Вj . Требуется определить совокупность (mn)величин xij , удовлетворяющих условиям:
(1)
и обращающих в минимум линейную форму
(2)
Специфическими для транспортной задачи являются следующие два обстоятельства: а) каждое из переменных xij входит в два уравнения системы (1); б) все коэффициенты при переменных xij принимают лишь два значения 0 или 1.
ОПРЕДЕЛЕНИЕ 1. Если общая потребность в продукте в пунктах потребления равна общему запасу продукта в пунктах производства, т.е.
, (3)
то модель транспортной задачи называется закрытой. Если это условие не выполняется, то модель называется открытой.
ТЕОРЕМА: Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы продукта в пунктах производства были равны потребностям в пунктах потребления, т.е. чтобы выполнялось равенство (3).
Замечания: 1.Если запас превышает потребность, т.е. , вводится фиктивный (n+1)-й пункт потребления с потребностью
, а соответствующие транспортные издержки равны нулю, сi(n+1) = 0, i = .
2.Если потребности превышают запасы, т.е. вводится фиктивный (m+1)-й пункт производства с запасом
,
а соответствующие тарифы равны нулю, c(m+1)j = 0,j = .
ОПРЕДЕЛЕНИЕ 2. Всякое неотрицательное решение системы линейных уравнений (1) называется планом транспортной задачи.
ОПРЕДЕЛЕНИЕ 3. План X* = , ; , при котором функция (2) принимает минимальное значение, называется оптимальным планом транспортной задачи.
Часто план транспортной задачи, с которого начинают решение, называют опорным.
Число переменных xij в транспортной задаче с m пунктами производства и n пунктами потребления равно mn, а число уравнений в системе (1) равно m+n. Т.к. предполагается, что выполняется условие (3), то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план может иметь не более n+m-1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно в точности n+m-1 , то план является невырожденным, а если - меньше - то вырожденным.
Для определения оптимального плана транспортной задачи разработаны алгоритмы, существенно более простые, чем симплекс-метод, который является одним из основных методов решения задач линейного программирования. Наиболее известными из этих алгоритмов являются метод потенциалов и метод дифференциальных рент (или венгерский).
2. Метод потенциалов
Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплекс-методом: сначала находят опорный план (начальное допустимое базисное решение), а затем его последовательно улучшают до получения оптимального. Рассмотрим три метода построения опорного плана. При заполнении клеток таблицы необходимо помнить, что суммы величин по столбцам и строкам должны соответствовать потребностям и запасам.
Методы построения опорного плана
а) Метод северо-западного угла.
Метод позволяет за n+m-1 шаг заполнить клетки таблицы таким образом, чтобы удовлетворить все потребности, исчерпав при этом все запасы. Заполнение клеток таблицы начинается с левой верхней клетки ("северо-западной"), в которую ставят максимально возможное число, т.е. минимальное из чисел запасов и потребностей для этой клетки. При этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая северо-западная клетка и т.д.
б) Метод минимального элемента.
Заполнение клеток осуществляется по принципу: "Самая дешевая перевозка осуществляется первой