Метод минимального элемента.
В отличие от метода северо-западного угла, этот метод позволяет построить начальный опорный план, более близкий к оптимальному. Суть метода заключается в том, что в распределительной таблице находится клетка ( ) с наименьшей стоимостью перевозки . В эту клетку назначается максимально возможный объем перевозок и эта величина записывается в клетку ( ). При этом возможны три случая, описанные в методе сев-зап угла. В результате закрывается один ряд. В ставшейся части таблицы вновь находится клетка с минимальной стоимостью перевозок, назначаем максимально возможный объем перевозки и т.д. Через (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 некоторой другой базисной переменной строки , и т.д….
Если таким образом удается прийти к уменьшению некоторой базисной переменной столбца b, то действительно можно увеличить объем перевозки в клетке . Тем самым будут найдены объемы перевозок, увеличиваемые или уменьшаемые на величину Q. Если полученные клетки соединить прямыми линиями, то получается замкнутая линия, называемая циклом. Цикл обладает следующим свойством: линия начинается и кончается в небазисной клетке , остальные вершины ломаной принадлежат строкам и столбцам таблицы, на пересечении которых находятся базисные клетки, угол между двумя соседними сторонами равен 900. Такой цикл всегда существует для любой небазисной клетки и он единственный.
Пусть цикл, соответствующий клетке , построен. В клетке ставится знак «+», а далее поочередно в вершинах цикла ставятся «-», «+»… Объемы перевозок, отмеченные «+», увеличиваются, а «-» – уменьшаются на величину Q=min{ }. Таким образом, величина Q прибавляется ко всем объемам перевозок, отмеченных знаком «+», и вычитается от всех объемов перевозок, отмеченных знаком «-».

В результате получаем новый опорный план, в котором переменная становится новой базисной переменной, а одна из базисных переменных , значение которой стало =0, становится небазисной переменой (выводится из базиса). При этом значение целевой функции уменьшается на . Полученный новый опорный план записывается в новой распределительной таблице, и вновь проверяется на оптимальность и т.д. пока не получат оптимальный опорный план.
Примечание. Если в процессе построения начального опорного плана или в ходе решения получается вырожденный опорный план, то чтобы избежать зацикливаний, необходимо нулевым базисным переменным придать сколь угодно малое значение e> 0 и решить задачу как невырожденную. В оптимальном плане такой задачи необходимо считать e=0.
Пример:
| vj
|
|
|
|
|
|
| ui
| Аi Bj
|
|
|
|
|
| ai
|
|
| 4
| 5
| 9
| 3
| 6
|
|
|
| 11
| 9
| 11
| 7
| 10
|
|
|
| 7
| 9
| 17
| 16
| 21
|
|
|
| 13
| 6
| 15
| 16
| 22
|
|
|
| 21
| 25
| 26
| 15
| 12
|
|
| bj
|
|
|
|
|
|
|
Построение начального опорного плана методом минимального элемента.
| vj
|
|
|
|
|
|
| ui
| Аi Bj
|
|
|
|
|
| ai
|
|
| 5 4
| 5
| 9
| 10 3
| 6
|
|
|
| 11
| 5 9
| 11
| 7
| 15 10
|
|
|
| 20 7
| 9
| 0 17
| 16
| 21
|
|
|
| 13
| 25 6
| 15
| 16
| 22
|
|
|
| 21
| 25
| 10 26
| 15
| 0 12
|
|
| bj
|
|
|
|
|
|
| Проверка опорного плана на оптимальность.
а) Определение потенциалов.
u1=0
v1= u1+c11=0+4=4
v4=u1+c14=0+3=3
u3=v1- c31=4-7= -3
v3=u3+c33=-3+17=14
u5=v3- c53=14-26= -12
v5=u5+c55=-12+12=0
u2=v5- c25=0-10= -10
v2=u2+c22=-10+9= -1
u4=v2- c42 = -1-6= -7
| vj
|
| -1
|
|
|
|
| ui
| Аi Bj
|
|
|
|
|
| ai
|
|
| 5 4
| 5
| 9
| 10 3
| 6
|
| -10
|
| 11
| 5 9
| 11
| 7
| 15 10
|
| -3
|
| 20 7
| 9
| 0 17
| 16
| 21
|
| -7
|
| 13
| 25 6
| 15
| 16
| 22
|
| -12
|
| 21
| 25
| 10 26
| 15
| 0 12
|
|
| bj
|
|
|
|
|
|
|
б) Определение значений D (только для небазисных клеток!).
D12=V2-U1-C12=-1-0-5=-6< 0
D13=V3-U1-C13=14-0-9 = 5> 0!!!!!! – План неоптимален!!!
.................
Наибольшее значение D23=V3-U2-C23=14-(-10)-11 = 13> 0!!!!!!!
Улучшение опорного плана.
Вводим в базис клетку (2, 3).
| vj
|
| -1
|
|
|
|
| ui
| Аi Bj
|
|
|
|
|
| ai
|
|
| 5 4
| 5
| 9
| 10 3
| 6
|
| -10
|
| 11
| 5 9
| + 11
| 7
| -15 10
|
| -3
|
| 20 7
| 9
| 0 17
| 16
| 21
|
| -7
|
| 13
| 25 6
| 15
| 16
| 22
|
| -12
|
| 21
| 25
| -10 26
| 15
| + 0 12
|
|
| bj
|
|
|
|
|
|
|
Q=min{x25, x53}=min{15, 10}=10 Клетка (5, 3) выводится из базиса.
Получили новый опорный план:
| vj
|
| -1
|
|
|
|
| ui
| Аi Bj
|
|
|
|
|
| ai
|
|
| 5 4
| 5
| 9
| 10 3
| 6
|
| -10
|
| 11
| 5 9
| 10 11
| 7
| 5 10
|
| -3
|
| 20 7
| 9
| 0 17
| 16
| 21
|
| -7
|
| 13
| 25 6
| 15
| 16
| 22
|
| -12
|
| 21
| 25
| 26
| 15
| 10 12
|
|
| bj
|
|
|
|
|
|
|
И так далее.
|