Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по ТПР - файл Лекция№03-тпр.doc


Загрузка...
Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№03-тпр.doc

Реклама MarketGid:
Загрузка...
Лекция №3.

Решение КТЗ методом потенциалов.

Метод потенциалов является модификацией метода последовательного улучшения плана в ЗЛП. Решение задачи включает в себя следующие этапы:

  1. Построение начального опорного плана.

  2. Проверка опорного плана на оптимальность.

  3. Переход в случае необходимости к лучшему опорному плану.

Сначала исходные данные записываются в распределительную таблицу, которая имеет следующий вид:








v1



vj



vn







Аi Bj

B1



Bj



Bn

ai

u1

A1

C11




C1j




C1n

a1





















ui

Ai

Ci1




Cij




Cin

ai





















um

Am

Cm1




Cmj




Cmn

am




bj

b1



bj



bn




Затем необходимо построить начальный опорный план.

1.Построение начального опорного плана.

Всего существует три метода отыскания начального ОП:

    1. Метод северо-западного угла,

    2. Метод минимального элемента,

    3. Метод Фогеля.

Рассмотрим 2 первых метода.

Метод северо-западного угла.

Построение нач. ОП начинается с левой верхней клетки, которая заполняется элементом . Для этого между пунктами А1 и В1 назначается максимально возможный объем перевозки, определяемый как . При этом возможны три случая:

а) . При этом , а все остальные перевозки из пункта производства А1 . Это означает, что из пункта А1 вывозится вся произведенная продукция в пункт потребления В1, поэтому объем перевозок из А1 другие пункты потребления равен 0 (нули в таблицу не записываются). Т.К. Из А1 больше вывозить нечего, то первая строка таблицы вычеркивается, а потребность пункта В1 уменьшается на величину , т.е. .

б) . При этом , а . Ресурс в А1 уменьшается на величину , т.е. , а столбец В1 вычеркивается, т.к. потребность пункта В1 полностью удовлетворена.

в) . Тогда . В этом случае вычеркивается либо строка, либо столбец (но не оба сразу!). В этом случае опорный план будет являться вырожденным, и чтобы найти нулевые базисные переменные либо строка, либо столбец в таблице остаются. Если вычеркивается строка, то считаем, что в пункте потребления В1 остается потребность, равная 0, которая в дальнейшем д.б. удовлетворена. Если же вычеркиваем столбец, то считаем, что в пункте производства А1 остался запас, равный 0, который в дальнейшем д.б. вывезен.

В таблицу заносятся нулевые базисные переменные, но небазисные нули не заносятся, чтобы не спутать их с нулевыми базисными переменными.

Пусть теперь назначен, и один ряд таблицы (строка или столбец) вычеркнуты (закрыты). В оставшейся части таблицы вновь берем левую верхнюю клетку и в ней назначаем максимально возможный объем перевозки с учетом ранее назначенных. В результате закрывается еще один ряд. После назначения в (n+m-1) клетках объемов перевозок получится некоторый опорный план перевозок. В заполненных клетках будут записаны базисные переменные, а переменные в незаполненных клетках будут соответствовать небазисным, которые равны 0 и не записываются, чтобы не спутать с базисными нулями вырожденного опорного плана.

Метод минимального элемента.

В отличие от метода северо-западного угла, этот метод позволяет построить начальный опорный план, более близкий к оптимальному. Суть метода заключается в том, что в распределительной таблице находится клетка () с наименьшей стоимостью перевозки . В эту клетку назначается максимально возможный объем перевозок и эта величина записывается в клетку (). При этом возможны три случая, описанные в методе сев-зап угла. В результате закрывается один ряд . В ставшейся части таблицы вновь находится клетка с минимальной стоимостью перевозок, назначаем максимально возможный объем перевозки и т.д. Через (n+m-1) шагов получается опорный план. Базисные переменные (включая нулевые) будут записаны в клетках, а небазисные равны 0 и не записаны.

2.Проверка опорного плана на оптимальность.

Запишем исходную модель КТЗ в векторной форме:

(5)

(6)

(7)

Здесь - вектор условия,

G= - вектор ресурсов.

Известно, что каждой ЗЛП соответствует двойственная задача. В двойственной задаче столько же переменных, сколько ограничений в исходной, и столько же ограничений, сколько в исходной задаче переменных.

Пусть - двойственная переменная, соответствующая i-тым ограничениям (2) (потенциал пункта Аi), - двойственная переменная, соответствующая j-тому ограничению (3) (потенциал пункта Вj). Тогда вектор двойственных переменных будет иметь вид: , а сама двойственная задача запишется в виде:

(8)

(9)

В скалярной форме эта задача запишется:

(10)

(11)

Существует теорема (без доказательства):

Для оптимальности опорного плана КТЗ (1)-(4) необходимо и достаточно существование вектора двойственных переменных, компоненты которого удовлетворяют условию:

(12)

Причем , если - базисная переменная, и , если - небазисная переменная.

Т.о. из теоремы следует, что если хотя бы для одной небазисной переменной , то опорный план неоптимален и его требуется улучшить.

Т.о., для проверки опорного плана на оптимальность необходимо определить потенциалы , всех пунктов Аi и Вj. Для этого используют условие (12) для базисных переменных:

(13)

Для отыскания потенциалов , необходимо решить данную систему линейных уравнений. Уравнений в системе (13) будет (m+n-1), а кол-во неизвестных (m+n). Поэтому любой одной переменной можно придать любое значение, в том числе и нулевое. На распределительной таблице построение потенциалов производится следующим образом: полагаем для какой-либо строки i1, содержащей базисные переменные, потенциал =0. Просматривается эта строка, и находятся базисные клетки . Для всех таких клеток из (13) можно определить потенциалы столбцов Вj :. Далее по известным потенциалам столбцов можно определить потенциалы некоторых строк. Пусть потенциал известен. Тогда просматривается столбец с номером и находятся клетки (), содержащие базисные переменные. Для всех этих клеток из (13) можно найти потенциалы строк Аi: . Продолжая этот процесс, найдутся потенциалы строк всех пунктов производства и потенциалы столбцов всех пунктов потребления.

Далее для всех клеток (i,j) содержащих небазисные переменные, вычисляются оценки . Если все , то рассматриваемый план КТЗ является оптимальным. Если хотя бы для одной клетки (k,l) справедливо , то опорный план неоптимален и необходимо перейти к лучшему опорному плану.

3.Переход к лучшему опорному плану.

Пусть рассматриваемый опорный план не оптимален. Для перехода к плану с меньшим значением целевой функции необходимо увеличить на максимально возможную величину объем перевозки в любой небазисной клетке (i,j) с . Обычно решение отыскивается быстрее, если выбрана клетка с наибольшим значением .

Пусть выбрана клетка с . Соответствующая небазисная переменная =0. Объем перевозки увеличиваем пока на неизвестную величину Q.Тогда для того, чтобы не нарушить баланс строки a, необходимо в строке a уменьшить объем перевозки некоторой базисной переменной на эту же величину Q. Но, уменьшив ее, мы нарушаем баланс столбца , который может быть восстановлен добавлением Q к некоторой базисной переменной столбца . Нарушенный баланс строки восстанавливается уменьшением на Q некоторой другой базисной переменной строки , и т.д….

Если таким образом удается прийти к уменьшению некоторой базисной переменной столбца , то действительно можно увеличить объем перевозки в клетке . Тем самым будут найдены объемы перевозок, увеличиваемые или уменьшаемые на величину Q. Если полученные клетки соединить прямыми линиями, то получается замкнутая линия, называемая циклом. Цикл обладает следующим свойством: линия начинается и кончается в небазисной клетке , остальные вершины ломаной принадлежат строкам и столбцам таблицы, на пересечении которых находятся базисные клетки, угол между двумя соседними сторонами равен 900. Такой цикл всегда существует для любой небазисной клетки и он единственный.

Пусть цикл, соответствующий клетке , построен. В клетке ставится знак «+», а далее поочередно в вершинах цикла ставятся «-», «+»… Объемы перевозок, отмеченные «+», увеличиваются, а «-» – уменьшаются на величину Q=min{}. Таким образом, величина Q прибавляется ко всем объемам перевозок, отмеченных знаком «+», и вычитается от всех объемов перевозок, отмеченных знаком «-».





В результате получаем новый опорный план , в котором переменная становится новой базисной переменной, а одна из базисных переменных , значение которой стало =0, становится небазисной переменой (выводится из базиса). При этом значение целевой функции уменьшается на . Полученный новый опорный план записывается в новой распределительной таблице, и вновь проверяется на оптимальность и т.д. пока не получат оптимальный опорный план.

Примечание. Если в процессе построения начального опорного плана или в ходе решения получается вырожденный опорный план, то чтобы избежать зацикливаний, необходимо нулевым базисным переменным придать сколь угодно малое значение >0 и решить задачу как невырожденную. В оптимальном плане такой задачи необходимо считать =0.


Скачать файл (681.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru