- •34. Первая теорема двойственности.
- •35. Вторая теорема двойственности и ее эконом.Интерпритация.
- •18.Третья теорема двойственности и ее эконом.Интерпритация.
- •36.Интервал устойчивости двойственных оценок.
- •20.Формулировка и математич.Модель трансп.Задачи(тз) по критерию стоимости. Особенности модели как злп.
- •21. Тз с открытой и закрытой моделью. Преобразование открытой модели в закрытую модель.
- •23. Теорема о ранге матрицы системы ограничительных уравнений тз и ее прикладное значение.
- •24. Циклы в транспортной таблице. Свойства циклов.
- •31. Алгоритм метода потенциалов.
- •25. Способы построения начального опорного плана тз (Наименьшего Эл-та, северо-западного угла, Фогеля)
- •29. Потенциалы поставщиков и потребителей, их вычисление и экономич.Смысл.
- •30.Связь между оценками св клеток и потенциалами.
- •26, 27, 28. Признак оптим-ти опорного плана. Оценка свободной клетки трансп.Таблицы. Процедура преобраз-я опорного плана тз в новый опорный план.
30.Связь между оценками св клеток и потенциалами.
Если в опт плане есть своб клетки с отриц оценками , то из них выбирается клетка с макс по модулю оценкой(перспективная) и загружается макс возможной поставкой. Чтобы загрузить перспективную клетку, нужно составить для нее цикл. Он существует, причем единственный. Вершины его отмечаются знаками + и – поочередно, начиная с перспективной клетки. Далее выбирается наименьшая загрузка клетки, отмеченной минусом. Это число(λ) добавляется к загрузке клеток, отмеченных +, и вычитается от тех, что отмечены -. Эта процедура называется сдвиг λ по циклу. В рез-те загружается 1 клетка, и должна освободиться 1 клетка. Если освобождается больше чем 1 клетка, то свободной нужно оставить только одну, ту, у которой тариф наибольший. В остальные освобождающиеся вписать нулевую загрузку.
26, 27, 28. Признак оптим-ти опорного плана. Оценка свободной клетки трансп.Таблицы. Процедура преобраз-я опорного плана тз в новый опорный план.
В соответствии с теорией двойственности, если xij*=0, то ui+vj<=cij, т.е.разность
- наз-ся оценкой свободной клетки и ее величина показ-т, как измен-ся общая ст-ть перевозок, если по маршруту (ij) провести единицу груза. Таким образом признаком оптимальности опорного плана ТЗ является неотрицательность оценок свобод.клеток. если среди оценок есть отриц-ые, то чтобы уменьшить общую ст-ть перевозов нужно загрузить первую очередь клетку с наибольшей по модулю отрицательной оценкой. Такую клетку наз-ют перспективной. Если в распределит-ой таблице, содержащей оптим.план, имеются свободные клетки с нулевыми оценками, то задача имеет не единственный оптим.план. Загружая свободную клетку с нулевой оценкой, можно найти еще один оптим.опорный план. И так для каждой свободной клетки с нулевой оценкой.
Чтобы осуществить переход от одного опорного плана к другому необходимо загрузить перспективную клетку. Для этой клетки составляется цикл. Нужно доказать, что для каждой свободной клетки трансп.таблицы, содержащей опорный план, сущ-ет цикл, причем только единственный. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки. Далее выбир-ся наименьшая из загрузок клеток, отмеченная «-». Она обозначается число λ добавляется к загрузке клеток, помеченных «+», и вычитается из загрузки клеток, отмеченных «-». Клетка по к-рой выбрано число λ освобождается. Если освобождается одновременно несколько клеток, то свободной остается та, в к-рой наибольший тариф. В остальные освободившиеся вписывается загрузка 0.