Постановка задачи - раздел Образование, Конспект лекций МЕТОДЫ ОПТИМИЗАЦИИ Классическая Транспортная Задача Лп Формулируется Следующим Образом. Имеется ...
Классическая транспортная задача ЛП формулируется следующим образом. Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины:
- объем производства (запас) i-го поставщика,;
- объем потребления (спрос) j-го потребителя,
- стоимость перевозки (транспортные затраты) единицы продукции от i-го поставщика к j-му потребителю.
Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен, и при этом общая стоимость всех перевозок была бы минимальна [1,3].
Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае – открытой. Открытая модель решается приведением к закрытой модели.
Математическая закрытая модель транспортной задачи имеет вид
В случае, когда суммарные запасы превышают суммарные потребности, то есть , вводится фиктивный n+1 потребитель, потребности которого .
В случае, когда суммарные потребности превышают суммарные запасы, то есть , вводится фиктивный m+1 поставщик, запасы которого .
Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к закрытой модели.
Государственное образовательное учреждение высшего профессионального образования... Омский государственный технический университет...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Постановка задачи
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Омск 2007
УДК 007(075)
ББК 32.81я73
З-96
Рецензенты:
О.В. Кириченова, канд. физ.-мат. наук, доц. ОмГПУ;
О.П. Диденко, канд. пед. н
Общие рекомендации к графическому решению задач ЛП
1. Графически могут решаться [1]:
a) задачи, заданные в произвольной форме, содержащие не более двух переменных;
b) задачи, заданные в канонической форме, с числом свободных перем
Симплекс-метод
Рассмотрим задачу ЛП в канонической форме:
(12)
……………
Алгоритм симплекс-метода для задачи на минимум
Шаг 0. Подготовительный этап.
Приводим задачу ЛП к специальной форме (15).
Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме:
Метод искусственного базиса
Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:
(16)
Характерная особенность задачи
Двойственный симплекс-метод
Метод работает с теми же симплексными таблицами, что и прямой симплекс-метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная,
Теоремы двойственности
Двойственность является одним из фундаментальных понятий в теории ЛП. Исключительно важную роль играют следующие утверждения, получившие названия теорем двойственности [1,3].
Первая тео
Постановка задачи ЦЛП
Задача целочисленного программирования (ЦЛП) формулируется так же, как и задача ЛП, но включается дополнительное требование, состоящее в том, что значения переменных, составляющих оптимальное решен
Алгоритм метода Гомори
Шаг 1. Симплекс-методом находим оптимальное решение задачи (22) без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В этом случае алгоритм
Метод северо-западного угла
Рассмотрим «северо-западный угол» незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю.
Возможны три случая:
Если
Метод потенциалов
Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке цикла совершает поворот на
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов