![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Транспортная задача линейного программирования
4.1. Постановки задачи 4.1.1. Закрытая транспортная модель Некоторый однородный продукт, сосредоточенный у m поставщиков Аi в количестве ai (i = 1,..., m) единиц соответственно, необходимо доставить n потребителям Вj в количестве bj (j = 1,..., n) единиц. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.
Обозначим через хij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке хij единиц груза, то стоимость перевозки составит сijxij. Стоимость всего плана перевозок выразится двойной суммой:
Систему ограничений получаем из следующих условий задачи: а) все грузы должны быть вывезены, т.е. б) все потребности должны быть удовлетворены, т.е.
Таким образом, математическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции
при ограничениях
xij ³ 0, i = 1, …, m; j = 1, …, n. (4.4)
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.
Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (4.5), называется закрытой моделью; в противном случае – открытой, а условие (4.5) – условием баланса. Пример 4.1. Таблица 4.1.
4.1.2. Открытая транспортная модель Для открытой модели может быть два случая: а) суммарные запасы превышают суммарные потребности б) суммарные потребности превышают суммарные запасы Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений. Найти минимальное значение линейной функции: при ограничениях
Открытая модель решается приведением к закрытой модели. В случае «а», когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вn + 1, потребность которого:
В случае «б», когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аm + 1, запасы которого: Стоимость перевозки единицы груза до фиктивного потребителя полагаем равной: 0, если безразлично у какого из поставщиков останется излишек груза М, если существует запрет на невывоз груза у i-го поставщика
От фиктивного поставщика: 0, если безразлично, какой потребитель недополучит заявленного количества груза
М, при невозможности недопоставки j-му потребителю. 4.1.3. Транспортная задача с запрещенными перевозками. Если от поставщика i потребителю j перевозка запрещена, то стоимость перевозки 4.1.4. Транспортная задача с ограничением на пропускную способность канала. В этом случае, модель транспортной задачи имеет следующий вид:
при ограничениях
|