5.1.2. Метод наименьшей стоимости
Вычисления производятся следующим образом.
Шаг 1. Выбирается переменная, которой соответствует наименьшая стоимость во всей таблице, и ей придается возможно большее значение. (Если таких переменных несколько, то берется любая из них.)
Шаг 2. Вычеркивается соответствующий столбец или строка (т.к. данное ограничение задачи выполнено). Если ограничения по столбцу и строке выполняются одновременно, то, как и в методе северо-западного угла, вычеркивается либо столбец, либо строка.
Шаг 3. Вычисляется новое значение спроса или объема производства для невычеркнутой строки или столбца.
Шаг 4.
Далее процесс повторяется при возможно большем значении той переменной, которой соответствует минимальная стоимость среди невычеркнутых (это значение может оказаться и нулевым). Процедура завершается, когда остается одна строка и один столбец.
Можно показать, что теорема 5 остается в силе и при таком способе построения начального решения.
самостоятельно №3. Доказать, что Метод Наименьшей Стоимости всегда приводит к ДБР.
5.1.3. Приближенный метод Фогеля (пмф)
Этот метод является эвристическим и обычно приводит к лучшему начальному решению, чем два описанных выше. На самом деле ПМФ часто дает оптимальное или близкое к оптимальному начальное решение. Алгоритм состоит из следующих шагов.
Шаг 1. Вычислить штраф для каждой строки (столбца), вычитая наименьший элемент этой строки (столбца) из следующего за ним по величине элемента той же строки (столбца)
шаг 2. Отметить строку или столбец с самым большим штрафом, а если таких несколько, выбрать среди них любую строку или любой столбец. В отмеченной строке или столбце выбрать переменную с самой низкой стоимостью и придать ей наибольшее возможное значение. Скорректировать объем производства и спрос и вычеркнуть строку или столбец, соответствующие выполненному ограничению. Если ограничения по строке или столбцу выполняются одновременно, то вычеркнуть либо строку, либо столбец, а оставшемуся столбцу (строке) приписать нулевой спрос (объем производства). Строка (или столбец) с нулевым объемом производства (или спроса) не учитываются в дальнейших вычислениях (на шаге 3).
Шаг 3.
(А) Если невычеркнутой остается в точности одна строка или один столбец, то закончить вычисления.
(Б) Если остается невычеркнутой только одна строка (столбец) с положительным объемом производства (спросом), найти базисные переменные в этой строке (столбце), используя метод наименьшей стоимости.
(В) если всем невычеркнутым строкам и столбцам соответствуют нулевые объемы производства и величины спроса, найти нулевые базисные переменные, используя метод наименьшей стоимости.
(Г) В других случаях вычислить новые значения штрафов для невычеркнутых строк и столбцов и перейти к шагу 2. (Отметим, что строки и столбцы с нулевыми значениями объема производства и спроса не должны использоваться при вычислении этих штрафов).
самостоятельно №4. Объяснить смысл производимых действий. Придумать «яркий» пример….
5.2. Вырожденность тзлп
Напомним, что ЗЛП называется вырожденной, если у нее существует хотя бы одно вырожденное ДБР. Для ТЗ выяснить, является ли она вырожденной, достаточно просто.
Теорема 6.
Транспортная
задача является вырожденной тогда и
только тогда, когда суммарный обьем
производимой продукции в нескольких
(не всех) пунктах производства равен
суммарной потребности в нескольких (не
всех) пунктах назначения, т.е. существуют
подмножества
М'M={1,2,...,m},
N'N={1,2,...,n},
для
которых
самостоятельно №5 Доказать теорему. Сконструировать две ТЗ, для которых после применения МС-ЗУ и МНС получается вырожденные ДБР.