Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Решение транспортной задачи методом потенциалов.
Процедура перехода от одного опорного плана к другому алгоритмически выполняется таким образом. Пусть выбран некоторый небазисный элемент , который вводится в базис. Отметим его знаком «+». Дальше строится замкнутая цепочка, вершинами которой будут базисные элементы опорного плана. Вершины цепочки отражаются знаком «+» и «-» по очереди, соблюдая правило: каждая строка и столбец должны иметь столько элементов, отмеченных знаком «-», сколько и «+».Среди элементов, отмеченных знаком «-» выбирается минимальный элемент. Определим его через . добавляется к элементам, отмеченным знаком «+», и вычитается из элементов, отмеченных знаком «-». Оптимальность опорного плана проверяется согласно величине оценок , причем . Параметры вычислим, таким образом, для имеем систему уравнений вида . Таких уравнений есть , откуда можно определить компоненты Ui и Vj вектора, который вводится. Искомых величин есть , а уравнений на одно меньше. Для определенности предусматривается , что, а другие определяются из системы уравнений. Зная значение Ui и Vj, можно определить параметры
Другими словами, для вычисляются значения . Транспортная задача является задачей минимизации. Опорный план оптимальный, если все . Если план неоптимален, то среди положительных выбирается максимальный Элемент с номером подлежит введению в базис (он является первым элементом при построении цепочки). Метод решения задач транспортного типа называется методом потенциалов. Метод основан на идее нахождения потенциалов (величин Ui и Vj) и выборе компоненты, что вводится в базис, если опорный план неоптимальный. Алгоритм метода потенциалов представляет пошаговый процесс, который состоит из проверки на оптимальность опорного плана, вырожденности и переход на новый опорный план. Процесс руководствуется признаком оптимальности. Опишем этот процесс. Шаг 0. Возвести данные в таблицу и определить опорный план. Если план вырожден, то ввести нулевые базисные элементы. Шаг 1. Составить систему уравнений для и вычислить все потенциалы Ui и Vj. Шаг 2. Вычислить значение для небазисных компонент. Шаг 3. Если план неоптимален, то определить В другом случае перейти к шагу 6. Шаг 4. Построить цепочку, начиная с элемента и определить как минимальный элемент среди элементов, отмеченных знаком минус. Шаг 5. Определить новый опорный план; если имеет место вырожденность, то ввести нулевые базисные компоненты. Перейти к шагу 1. Шаг 6. Выписать базисные компоненты из последней таблицы и определить значение целевой функции
где - оптимальные значения перевозок.
Пример: Проверим оптимальность опорного плана, построенного методом северо-западного угла из предыдущей задачи.
Значение целевой функции для этого плана: План невырожден, т.к. в нем - 9, и = 4+6-1=9. Составим систему уравнений для и вычислим все потенциалы Ui и Vj.
Вычислим значение для небазисных компонент.()
Т.к. есть положительные то план не оптимален. Построим новый план. Найдем максимальную оценку больше нуля: =16. Значит вводить в план будем элемент . Начиная с этого элемента построим цепочку.
Найдем минимальный элемент в цепи, стоящий со знаком минус. . Построим план учитывая знаки цепи.
Посчитаем значение целевой функции для этого плана:
Значение целевой функции уменьшается, значит вычисление идет верно. Проверим полученный план на оптимальность. Для этого повторим процесс проверки как для плана . Процесс необходимо повторять до тех пор пока не получим план со всеми оценками больше или равными нулю.
Вопрос для самоподготовки 1. Суть способа перехода от одного опорного плана к другому. 2. Что определяется потенциалами в методе потенциалов? 3. Каким должны быть все в методе потенциалов, чтобы план был оптимальным?
ЛЕКЦИЯ 9.
Метод потенциалов для транспортной задачи с планом построенным
|