Транспортная задача линейного программирования
Категория реферата: Рефераты по математике
Теги реферата: сочинение описание, курсовики скачать бесплатно
Добавил(а) на сайт: Эсмеральда.
Предыдущая страница реферата | 12 13 14 15 16 17 18 19 20 21 22 | Следующая страница реферата
В то же время каждому ограничению из (6.1)
сопоставляется определенная неизвестная в двойственной задаче. Тем самым
устанавливается соответствие между всеми пунктами 
и 
и всеми неизвестными
двойственной задачи.
Обозначим неизвестную в двойственной задаче, отвечающую
пункту отправления , через 
, а пункту назначения – через 
.
Каждому неизвестному в транспортной задаче соответствует
ограничение, связывающее неизвестные в двойственной задаче. Неизвестное 
входит ровно в два
ограничения системы (6.1): одно из них отвечает пункту , а другое – пункту . В обоих этих уравнениях коэффициент при равен 1. Поэтому
соответствующее ограничение в двойственной
задаче имеет вид
|
(6.2) |
.
Правая часть неравенства (6.2) равна 
, потому что именно с этим коэффициентом неизвестная входит в минимизируемую
формулу (2.4).
Оптимизируемая форма двойственной задачи имеет вид
|
(6.3) |
Таким образом, задача двойственная к транспортной
формулируется следующим образом. При ограничениях (6.2) максимизировать
формулу (6.3). Подчеркнем, что знак значений неизвестных и может быть
произвольным.
Предположим, что нам известно некоторое допустимое
базисное решение транспортной задачи, в котором все базисные неизвестные
строго положительны. Это решение оптимально лишь в том случае, когда
соответствующая ей система оказывается совместной. Эта система возникает из
системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным 
заменить точными
равенствами.
В итоге приходим к соотношению:
|
(6.4) |
(для всех свободных
неизвестных )
Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточным условием оптимальности.
7.Пример решения транспортной задачи.
В городе N имеется 4 склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.
|
Склад |
B1 (b1=40) |
B2 (b2=50) |
B3 (b3=15) Рекомендуем скачать другие рефераты по теме: сайт рефератов, контрольная работа 7. Предыдущая страница реферата | 12 13 14 15 16 17 18 19 20 21 22 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |
Магазины