Методы линейного программирования для решения транспортной задачи

при ограничениях

(1)

Если к этим ограничениям добавить еще одно:

,(2)

т.е. суммарная мощность поставщиков равна суммарному спросу потребителей, то соо

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

Задачам, в которых ограничение (2) отсутствует, т.е.

,

первоначально соответствует открытая модель.

Отметим некоторые особенности экономико-математической модели транспортной задачи.

Система ограничений (1) сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.

Матрица коэффициентов при переменных в системе (1) состоит только из единиц и нулей.

Система ограничений (1) включает k уравнений, связывающих поставки i-того поставщика с мощностью Mi (i=1,2,…,k) этого поставщика, и l уравнений, связывающих поставки j-тому потребителю со спросом Nj (j=1,2,…,l) этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число l - числу столбцов.

Число переменных xij, входящих в целевую функцию и в систему уравнений (1), равно произведению kl, т.е. числу клеток таблицы.

Таким образом, система ограничений (1) есть система из k+l уравнений с kl переменными.

Любое решение транспортной задачи (x11, x12,…, xkl) называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях.

Оптимальному решению транспортной задачи соответствует оптимальное распределение поставок, при котором целевая функция достигает своего минимума.

В ходе решения задачи и нужно получить это оптимальное распределение поставок, которому соответствует какое-то допустимое базисное решение системы ограничений (1). [4]

3. Необходимое и достаточное условия разрешимости транспортной задачи

Ограничение (1) и условия неотрицательности переменных, исключающие обратные перевозки xij>0; i= 1, 2, …, k; j= 1, 2,., l.

Эти условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.

Как видим, система ограничений задана в основном (k + l) уравнениями. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения.

Сложим элементы xij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим . Сложим те же элементы по столбцам, каждый столбец дает Nj, и в сумме получим . Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие

.

Равенство является необходимым условием совместности ограничений задачи.

Докажем и достаточность этого условия: если запасы равны потребностям, то всегда имеется допустимый план.

Действительно, пусть . Рассмотрим такие числа:

Убедимся, что эти числа образуют допустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениям задачи.

Просуммируем эти числа по индексу i:

.

Но величины Nj, от индекса i не зависят и их можно вынести за знак суммы. В результате

или

,

Следовательно, взятые числа удовлетворяют группе уравнений (1).

Просуммируем эти числа по индексу j:

Вынося постоянные Mi и за знак суммы и имея в виду, что , получаем

или в развернутом виде

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

Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи. [5]

4. Свойство системы ограничений транспортной задачи

Согласно теореме о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться r отличных от нуля координат, где r - ранг системы ограничений

.

В этой системе ограничений уравнений закрытой транспортной задачи имеется k+l-1 линейно-независимых уравнений, т.е. ранг системы ограничений равен k+l-1. [6]

5. Опорное решение транспортной задачи

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

При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких "вершинных" решений, не обязательно оптимальное, и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен, если нет - последовательно проверяют, не будут ли оптимальными соседние вершинные точки. Ту из них, в которой план эффективнее, принимают снова за исходную точку и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся так называемый симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием "методы последовательного улучшения допустимого решения (МПУ)": метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов для транспортной задачи и другие. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному. [2]

 Скачать реферат