Метод северо-западного угла.
Решение КТЗ методом потенциалов.
Метод потенциалов является модификацией метода последовательного улучшения плана в ЗЛП. Решение задачи включает в себя следующие этапы:
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 и не записываются, чтобы не спутать с базисными нулями вырожденного опорного плана.
Дата добавления: 2022-04-12; просмотров: 142;