Компоненты вектора 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 2 3 4 5 

Другое по теме:

Организация работы района управления в дорожном центре управления перевозками
В настоящее время в организационной структуре хозяйства перевозок ОАО "РЖД" выделено четыре иерархических уровня: сетевой, дорожный, станционный. Между диспетчерами разных уровней существует иерархия, которая проявляется при необходимости принимать решение. Кроме того в центре каждого уров ...

Расчет локомотивной откатки в горно-геологических условиях залегания и горно-технологических условиях отработки месторождений полезного ископаемого
Чтобы осуществить процесс материального производства, нам необходимо собрать его различные виды в одной точке пространства, т.е. сосредоточить их вместе. Процесс сбора вещества в одно и тоже время должен представлять процесс перемещения – транспортирование. Рудничный транспорт являет ...

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