Лекция МПС №5 от 12.11.2012


Специальные задачи линейного программирования
Математические модели задач транспортного типа
Транспортная задача (ТЗ) является важнейшей частной задачей ЛП, имеющей обширные приложения не только к проблемам транспорта. Она выделяется в ЛП определенностью экономической характеристики, особенностями экономической характеристики, особенностями математической модели, наличием специфических методов решения.
Простейшая формулировка транспортной задачи по критерию стоимости следующая:
В m пунктах отправления (поставщиках) находится соответственно единиц однородного груза (ресурсов), который должен быть доставлен n потребителям в количествах единиц соответственно (потребности). Известны транспортные издержки перевозок единицы груза из i-го пункта отправления в j-й пункт потребления (,).Требуется спланировать перевозки (т.е. указать, сколько единиц груза должно быть отправлено от i-го поставщика j-му потребителю) так, чтобы:
весь груз из пуктов отправления был вывезен;
потребности каждого пункта потребления были полностью удовлетворены;
суммарные издержки перевозок были минимальными.
Для наглядности условия транспортной задачи представим в виде таблицы, которая называется транспортной или распределительной.
Здесь количество груза, перевозимого из i-го пункта отправления в j-тый пункт назначения, равно ,,. Запас груза в i-м пункте отправления определяется величиной ,, а в j-тый пункта в грузе ,. Матрица называется матрицей тарифов (издержек или транспортных расходов). Планом транспортной задачи называется матрица перевозок .

Если в плане перевозок переменная , то это значение записывают в соответствующую клетку (i,j) и считают загруженной (занятой) или базисной, если же , то клетку (i,j), как правило, оставляют свободной.
Составим математическую модель задачи транспортного типа. Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функцией
(3.1)
Переменные должны удовлетворять ограничениям по запасам (3.2), по потребностям (3.3) и условиям неотрицательности (3.4). В математической записи это можно представить так:
, (3.2)
, (3.3)
, , (3.4)
Таким образом, среди множества решений системы ограничений (3.2)-(3.3) требуется найти такое неотрицательное решение, которое минимизирует целевую функцию (3.1). Полученная задача является задачей ЛП. Решение ТЗ проводится проводится с помощью общего приема последовательного улучшения плана, который реализован в симплексном методе.
Этапы решения транспортной задачи
Определение исходного опорного плана.
Оценка этого плана.
Переход к следующему плану путем однократной замены одной из базисных переменных на свободную.
Условие баланса
Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы в пунктах отправления были равны потребностям в пунктах назначения, т.е. выполнялось равенство
.(3.5)
Если условие (3.5) выполнено, то модель ТЗ называется закрытой (сбалансированной). Задача с отсутствием баланса между ресурсами и потребностями называется открытой: .
Если , то в математическую модель вводится фиктивный (n+1)-й потребитель , для которого потребность равна разности между суммарной мощностью поставщиков и фактическим спросом потребителей, т.е. . Все тарифы на доставку груза с фиктивными потребностями считают равными нулю, т.е. , . Поэтому для новой задачи значение целевой функции не изменится. Иными словами, фиктивный потребитель не нарушит совместности системы ограничений. В транспортной таблице предусматривается дополнительный столбец.
Если , то в математическую модель вводится фиктивный (m+1)-й поcтавщик . Для этого в транспортную таблицу добавляется одна строка, запас груза для которой записывают равным , а стоимости перевозок полагают равными нулю, т.е. , . Поэтому в данном случае значение целевой функции не изменится, а система ограничений остается совместной.
Особенности системы ограничений
Система ограничений транспортной задачи (3.1)-(3.4) имеет ряд особенностей, что позволяет решить ее более рациональными способами.
Коэффициенты при неизвестных во всех ограничительных уравнениях равны единице.
Любая переменная встречается только в двух уравнений.
Система уравнений ТЗ симметрична относительно всех переменных.
Матрица системы ограничений состоит из 0 и 1, причем любой столбец содержит только два элемента, равных 1. А остальные – 0.
Система ограничений содержит уравнений с переменными. А так как , то ранг матрицы транспортной задачи на единицу меньше количества уравнений, т.е. , где m – число поставщиков, n – число потребителей. Следовательно, любое опорное решение системы ограничений задачи должно содержать базисных переменных и свободных переменных равных нулю.
Если все и - целые, то значения базисных переменных в допустимом базисном решении тоже целые. А так как это задача линейного программирования, то оптимальное решение является базисным допустимым решением и, следовательно, целым.
Пример 8. Урожай картофеля, собранный фермерами в количествах 60, 45 и 130 т соответственно, должен быть доставлен в четыре магазина . Спрос на картофель равен 50, 70, 60 и 80 т соответственно. Известна матрица транспортных расходов (в ден.ед.) на доставку 1 т картофеля:

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

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

или

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

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

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



Методы решения транспортной задачи
Построение начального опорного плана методом «минимального элемента»
План транспортной задачи называется опорным, если из заполненных им клеток нельзя образовать ни одного цикла. Циклом в транспортной таблице называется набор клеток матрицы перевозок, в котором две и только две соседние клетки расположены в одном столбце или одной строке, а последняя клетка набора лежит в той же строке или столбце, что и первая. Эту совокупность клеток можно представить так:
.
Графически цикл представляет собой замкнутую ломанную линию, звенья которой лежат только в строках или столбцах. При этом каждое звено соединяет только две клетки ряда. В цикле всегда четное число клеток. При правильном построении опорного плана для любой свободной клетки можно построить единственный цикл, содержащий данную клетку и некоторую часть незанятых клеток
Сущность метода «минимального элемента» заключается в том, что на каждом шаге осуществляется максимально возможное «перемещение» груза в клетку с минимальным тарифом . Заполнение таблицы начинают с клетки, которой соответствует наименьший элемент матрицы тарифов, причем выбирают только среди стоимостей реальных поставщиков и потребителей, а запасы фиктивного поставщика (или потребности фиктивного потребителя) распределяются в последнюю очередь.Пусть . Следовательно загружается клетка, т.е. . Если , то и из рассмотрения исключают столбец с номером k, соответствующий потребителю, спрос которого полностью удовлетворен. А новое значение . Если , то и из рассмотрения исключают строку с номером l, соответствующую поставщику, запасы которого израсходованы полностью. Новое значение . На некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-то одно). Тогда запасы соответствующего пункта отправления или потребности данного пункта назначения полагают равными нулю. Это нуль записывают в очередную заполняемую клетку. Опорный план называется невырожденным, если все его компоненты больше нуля, в противном случае он называется вырожденным.
Решение транспортной задачи методом потенциалов
Сравнивают общий запас груза с суммарным спросом и в случае нарушения баланса приводят задачу к закрытой модели.
Условие задачи записывают в форме транспортной таблицы.
Строят начальный опорный план перевозок.
Проверяют условие для базисных клеток (их должно быть ). Если это условие выполняется, то в одну из свободных клеток (как правило, в клетку с наименьшим тарифом) вписывают число 0, и такая клетка считается базисной. Однако число 0 записывают только в те клетки, которые не образуют циклы с ранее заданными клетками.
Вычисляют потенциалы и . Каждому поставщику (каждой строке) ставят в соответствие некоторое число , называемое потенциалом поставщика , , и записывают справа от таблицы, а каждому потребителю (или столбцу) – некоторое число , называемое потенциалом потребителя , , и записывают под таблицей. Числа и выбирают так, чтобы в любой базисной клетке их сумма равнялась тарифу. т.е. . Так как количество всех потенциалов и составляет , а занятых клеток , то для определения чисел и придется решать систему из уравнений с неизвестными. Поэтому одному из неизвестных потенциалов придают произвольное значение. Тогда остальные определяются однозначно.
Для проверки оптимальности плана просматривают свободные клетки, для которых определяют оценки . Экономически оценка показывает, на сколько денежных единиц изменятся транспортные издержки от загрузки данной клетки единицей груза. Если все оценки неотрицательные, т.е. , то план оптимальный и остается посчитать транспортные расходы. Иначе переходят к п. 7.
Из отрицательных оценок выбирают минимальную. Пусть это будет . Тогда клетку вводят в число базисных, т.е. строят цикл по загруженныс клеткам с началом в этой клетке и перераспределяют поставки так, чтобы баланс цикла сохранился. Для этого вершинам цикла приписывают чередующиеся знаки «+» и «-» (для «+»). В клетках с «-» отыскивают наименьший груз w, т.е. , который и перемещается по клеткам замкнутого цикла, т.е. прибавляется к перевозкам в клетках со знаком «+» (включая свободную) и вычитается из перевозок в клетках со знаком «-». Следовательно, клетка станет свободной и переменная уйдет из базиса. Значение остальных базисных переменных переписываются. Таким образом, получают новую транспортную таблицу с улучшенным планом, для которого транспортные издержки изменятся на величину . Далее переходят к пункту 4.
При сдвиге по циклу вместо одной может осободиться сразу несколько клеток (вырожденная задача). Свободной иставляют только одну (с наибольшим тарифом), а в остальные освободившиеся клетки вписывают нули и считают их загруженными.
Если все оценки , то оптимальный план единственный. Если существует хоты бы одна оценка , то задача имеет множество оптимальных планов, которое представляет собой выпуклую линейную комбинацию оптимальных решений. Другие оптимальные планы можно получить, загружая по очереди клетки с нулевыми оценками.
Пример 9. Решить задачу из примера 8 методом потенциалов.
Занесем исходные данные задачи в таблицу:
в столбец - запасы картофеля i-го фермера, ;в строку - потребности j-го магазина, ;в нижний правый угол каждой клетки, расположенной в i-строке и j-м столбце, стоимости перевозок , , .
Находим , тогда . Так как , то из рассмотрения исключим строку с номером 2 и .
Из оставшихся клеток находим и тогда. Так как , то из рассмотрения исключаем столбец с номером 3 и и т.д.
Проверяем условие для базисных клеток , что соответствует числу занятых клеток и, следовательно, базисный план построен верно.



Вычислим потенциалы фермеров и магазинов , используя уравнения для базисных (заполненных) клеток, при дополнительном условии :

Далее по формуле подсчитаем оценки небазисных (пустых) клеток и занесем их значения в левые нижние углы незаполненных клеток

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

Клетка (1,2) исключается из базового множества, а клетка (2,2) вводится вместо нее.

Подученный опорный план оптимален, так как среди его оценок нет отрицательных:

Оптимальный план не единственный, так как . Второе решение получим в новой транспортной таблице, загружая клетку (3,4).


Общее решение .

Приложенные файлы

  • docx 8981828
    Размер файла: 322 kB Загрузок: 0

Добавить комментарий