Курсовая. Матем-ка в эк-ке Цвиль М.М (1). Математика в экономике
![]()
|
5.4. Переход от одного опорного решения к другому. В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок (осуществляется сдвиг по циклу). Перевозка «загружается» в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение. Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением. Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-». Такой цикл называется означенным (рис. 5.6). ![]() Рис 5.6.Означенный цикл. Сдвигом по циклу на величину λ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», и уменьшение объемов перевозок на ту же величину λ во всех четных клетках, отмеченных знаком «-». 5.5. Метод потенциалов Широко распространенным методом решения транспортных задач является метод потенциалов. Если допустимое решение ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа равенств (5.6) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных ![]() ![]() ![]() ![]() ![]() Числа ![]() ![]() ![]() ![]() ![]() Алгоритм решения транспортных задач методом потенциалов: 1. Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок. 2. Построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом). проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используя метод вычеркивания). 3. Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений ![]() которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому. которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще ноль). Остальные потенциалы однозначно определяются по формулам ![]() если известен потенциал ![]() ![]() если известен потенциал ![]() 4. Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам ![]() и те из них, которые больше нуля, записывают в левые нижние углы клеток. Если для всех свободных клеток ![]() 5. Перейти к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка ![]() Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину ![]() ![]() Пример 3. Решить ТЗ, исходные данные которой заданы в таблице 5.9. Таблица 5.9
Решение: 1. Проверяем необходимое и достаточное условие разрешимости задачи. Находим суммарные запасы поставщиков: ![]() ![]() 2. Находим начальное опорное решение методом минимальной стоимости (таблица 5.10). Таблица 5.10
|