Компоненты вектора yне ограничены по знаку, потому что прямая задача (1.21) каноническая. Неравенства двойственной задачи становятся нагляднее, если представить двойственный вектор yв виде , где первые m компоненты ui соответствуют строчным уравнениям (15), последующие n компонент uj – столбцовым уравнениям (16). Число ui принято называть потенциалом поставщика I, число uj – потенциалом потребителя j. Если в задаче (22) записать векторы y, b, c и матрицу А покомпонентно, то с учетом того, что каждый столбец матрицы А содержит всего две единицы, одна из которых соответствует строчному, другая – столбцовому уравнению прямой задачи, получим двойственную задачу в виде
; (23)
,
,
. (24)
Из постановки двойственной задачи (23), (24) видно, что увеличение потенциалов ui и uj приводит к возрастанию целевой функции (23), так как по предположению ai>0, bj>0 для всех I, j. Однако неравенства (24) ограничивают рост целевой функции. Согласно им, сумма потенциалов поставщика и потребителя не должна превышать расходы на перевозку между ними единицы продукта. Более строго, из второй теоремы двойственности следует, что оптимальный план прямой задачи может включать ненулевое значение перевозки xij только в том случае, если сумма потенциалов поставщика I и потребителя j равна величине расходов на перевозку между ними единицы продукта. Применяя этот результат к паре задач (14) – (17) и (23), (24), получаем следующий признак оптимальности плана транспортной задачи: если план оптимален, то ему соответствует система
чисел ui и uj, удовлетворяющих условиям:
для
; (25)
для
. (26)
Введем для переменных xij оценки
, (27)
которые являются приведенными коэффициентами целевой функции, эквивалентными оценками симплекс метода. Тогда из (25), (26) получаем признак оптимальности в следующем виде: план
оптимален, если все его оценки
вида (27) неположительны.
Разновидностями транспортной задачи являются задача о максимальном потоке, задача о назначениях и т. д. При этом каждая разновидность транспортной задачи может решаться различными методами. Например, задача о назначениях кроме классического метода решения имеет так называемый венгерский метод.
При диспетчировании перевозок грузов в конкретном транспортном хозяйстве конкретного предприятия диспетчеру всегда приходится решать транспортную задачу, т. е. составлять план (расписание) перевозок грузов при минимальных затратах на их перевозку. Естественно, диспетчер составляет не всегда оптимальный план. Для реальной минимизации затрат на перевозку грузов необходимо использовать ЭВМ.
Технологический процесс изготовления изделий на предприятиях микроэлектроники является очень трудоемким, а организация производственного процесса требует большое и разнообразное количество сырья и материалов, поэтому для обеспечения бесперебойного и эффективного функционирования производства на предприятии необходимо наличие развитой структуры транспортного хозяйства, которое позволяет выполнять все необходимые перевозки грузов. Неоптимальное распределение грузовых потоков может привести к росту себестоимости конечной продукции, а, следовательно, и к ее неконкурентоспособности. Ввиду этого рациональное планирование грузовых перевозок играет немаловажную роль в эффективности работы всего предприятия. Организацией транспортных потоков на предприятиях занимается диспетчерская служба или диспетчер, а так как работа людей является субъективной и основывается на опыте и профессионализме человека (группы людей), то схема распределения грузовых потоков часто является неоптимальной. Поэтому при диспетчировании целесообразнее было бы использовать программный комплекс, работающий на алгоритме решения транспортных задач со многими неизвестными и возможностью включения новых пунктов сырья, материалов, потребителей и автомобилей.
Другое по теме:
Технико-экономическая эксплуатация транспорта
Управление транспортом в процессе физического движения
товаров на пути от производителя к потребителям через сформированные
логистические каналы распределения состоит в последовательном решении следующих
задач:
1. Выбор вида транспорта и определение мест и способов
перевалки грузов с ...
Разработка оборудования для вырезки балласта на базе машины ЩОМ-Д
Балластная призма, на которую уложена рельсошпальная
решетка, может состоять из щебня, гравия, ракушечника и песка. На линиях с
большой грузонапряженностью и высокими скоростями движения поездов балластная
призма устраивается из щебня и отходов асбестовой промышленности. Толщина
балластн ...
Инвестиции в развитие железнодорожного транспорта
Ресурсы Земли истощаются,
а потребности землян растут, что побуждает к поиску новых возможностей
жизнеобеспечения. Это обстоятельство в значительной степени обусловило ход
интеграционных процессов в мире: на Американском континенте, в Азиатско-Тихоокеанском,
Центрально-азиатском реги ...