Составить опорный план методом северо западного угла. Метод минимальной стоимости

С помощью этого метода получается первоначальный план поставок.

> ПРИМЕР 3.1. У поставщиков А и А 2 , А 3 сосредоточено соответственно 30, 190 и 250 единиц некоторого однородного груза, который необходимо доставить потребителям В, В 2 , B 2 , В 4 в количестве 70, 120, 150 и 130 единиц. Стоимость перевозок единицы груза от поставщиков к потребителям задается матрицей

Элемент в 1-й строке и 3-м столбце равен 2, т. е. стоимость перевозки единицы груза от поставщика^ к потребителю В ъ равна 2, и т. д.

Построим первоначальный план поставок методом северо- западного угла.

Суммарная мощность поставщиков равна: 30 + 190 + 250 = 470.

Суммарный спрос потребителей равен: 70 + 120 + 150 + 130 = 470.

Это закрытая модель. Запишем наши данные в виде специальной таблицы.

В первом столбце указаны мощности поставщиков, в первой строке - спрос потребителей. Числа в левом верхнем углу клетки - это стоимость перевозок единицы груза от соответствующего поставщика соответствующему потребителю, т. е. значения из данной в условии матрицы.

План перевозок будет задан, если мы укажем, сколько единиц груза должен получить каждый потребитель от каждого поставщика, т. е. если пустая таблица из трех строк и четырех столбцов будет заполнена.

Северо-западный угол таблицы - это ее левый верхний угол, т. е. клетка в 1-й строке и 1-м столбце - клетка (1, 1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А есть 30 единиц груза, а потребителю В нужно 70 единиц. Находим минимум из этих двух чисел: min (30, 70) = 30. Клетка (1,1) перечеркивается по диагонали сплошной чертой (-), в правом нижнем углу пишется найденный минимум 30. Это означает, что поставщик А должен доставить потребителю В 30 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.

Так как поставщик А израсходовал все свои 30 единиц груза, то исключаем его из рассмотрения. Поэтому все остальные клетки

1-й строки перечеркнем по диагонали пунктиром (----). Такие

клетки в дальнейшем из рассмотрения исключаем и будем называть пустыми.

После первого шага наша таблица примет следующий вид:

Первая строка в дальнейшем не рассматривается. Северо-западный угол этой таблицы - это клетка (2, 1). Поэтому рассмотрим 2-го поставщика и 1-го потребителя. Мощность поставщика А 2 равна 190 единиц. Спрос потребителя В - 70 единиц груза. Но 30 единиц груза он получил от поставщика А (об этом говорит отмеченная клетка (1, 1). Поэтому непокрытый спрос потребителя В равен 70 - 30 = 40. Находим минимум min (190, 70 - 30) = 40. Клетка (2, 1) становится отмеченной. Запишем там этот минимум 40.

Поставщики А (30 единиц) и А 2 (40 единиц) полностью покрывают спрос потребителя В (70 единиц). Поэтому остальные клетки 1-го столбца объявим пустыми и в дальнейшем исключим из рассмотрения.

После второго шага таблица примет следующий вид:

Северо-западный угол этой таблицы - это клетка (2, 2). Min (190-40, 120)= 120.

Получаем следующую таблицу:

Северо-западный угол этой таблицы - это клетка (2, 3). Min (190-40- 120, 150) = 30. Получаем следующую таблицу:

Северо-западный угол этой таблицы - это клетка (3, 3). Min (250, 150 - 30) = 120. Получаем следующую таблицу:

Осталась одна незаполненная клетка - это клетка (3, 4). Min (250 - 120, 130) = 130. Получаем следующую таблицу:

После выполнения очередного шага мы исключали из рассмотрения либо строку, либо столбец. Только на последнем шаге отпали и строка, и столбец. Поэтому для полностью заполненной таблицы должно соблюдаться следующее соотношение: число отмеченных клеток = число строк + число столбцов - 1. В нашем случае это так: 6 = 34-4-1.

Если это соотношение не выполняется, то возникает так называемый особый случай. Как в этом случае поступать, будет рассказано дальше.

Посчитаем суммарные затраты. Для этого надо в каждой отмеченной клетке перемножить ее числа и результаты сложить: 4 х 30 + 3 х 40 + 1 х 120 + 2 х 30 + 3 х 120 + 7 х 130 = 1690.

Задача 3.1. Найти первоначальный план поставок северо- западного угла.

Заполнение распределительной таблицы начинают с клетки (1;1), при этом . Далее смещаются или по строке вправо или по столбцу вниз до клетки . Заполненные клетки должны распространяться так, чтобы их можно было соединить ломаной линией, звенья которой взаимно перпендикулярны.

Пример. Построить методом северо-западного угла начальный опорный план для транспортной задачи: поставщики а

Найти стоимость перевозок.

Решение. Строим распределительную таблицу и находим груз х 11 = min (20; 15) = 15. По первому столбцу не перемещаемся, так как спрос І потребителя удовлетворен. Перемещаемся по І строке в клетку (1; 2):

х 12 = min (а 1 – х 11 ; b 2) = min (5; 35) = 5.

Теперь переходим по ІІ столбцу в клетку (2; 2):

х 22 = min (30;b 2 – х 12) = min (30; 30) = 30.

Так как спрос ІІ потребителя удовлетворен и у ІІ поставщика продукция уже выбрана, то переходим к клетке (3; 3):

х 33 = min (40; 20) = 20.

х 34 = min (а 3 – х 33 ; b 4) = min (20; 20) = 20.

Таким образом, получен план перевозок:

Для подсчета стоимости перевозок нужно количество груза в каждой заполненной клетке умножить на соответствующий тариф в этой клетке и результаты сложить.

Б) Метод минимального элемента (наименьшей стоимости).

Строим распределительную таблицу и начинаем ее заполнять с той клетки, в которой наименьший тариф.

Пример. Построить начальный опорный план методом минимальной стоимости и найти транспортные расходы для транспортной задачи: поставщики а = (20; 30; 40); потребители = (15; 35; 20; 20); тарифы перевозок

Решение. Строим распределительную таблицу и начинаем ее заполнять с клетки (2; 1), т.к. в ней наименьший тариф х 21 = min (30; 15) = 15.

Потом заполняем клетку (3; 2) с тарифом с 32 = 3;

х 32 = min (40; 35) = 35.

х 14 = min (20; 20) = 20;

х 23 = min (а 2 – х 21 ; b 3 – х 33) = min (15; 15) = 15.

Сравнивая значение Z в а) и б), видим, что учитывая стоимости перевозок, затраты при втором методе значительно меньше.

Рангом матрицы системы (2) называют число , т.е. количество строк плюс количество столбцов и минус единица. Если число заполненных клеток в распределительной таблице равно рангу матрицы, то полученный план называется не вырожденным . В противоположном случае – вырожденным .

В пунктах а) и б) , а число заполненных клеток 5. Следовательно, полученные планы – вырожденные.

Метод потенциалов. Признак оптимальности опорного плана.

Допустимое решение транспортной задачи является оптимальным тогда и только тогда, когда можно найти такие числа – потенциалы , и , , которые удовлетворяют следующим условиям:

I. для всех заполненных клеток; (5)

II. для всех пустых клеток. (6)

На основании первого условия оптимальности потенциалы находят из условий и один, произвольно выбранный, потенциал приравнивают к нулю, например .

Если при проверке
второго условия оптимальности окажется, что для всех незаполненных клеток, то опорный план оптимален и соответствующее значение целевой функции Z определяет минимальные расходы.

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

Если же найдется хотя бы одна клетка, для которой , то план не оптимальный и можно перейти к нехудшему опорному плану.

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

Переход к не худшему опорному плану осуществляют при помощи цикла перераспределения груза. Цикл представляет собой замкнутую ломаную, звенья которой взаимно перпендикулярны и вершины цикла, кроме одной, находятся в заполненных клетках.

Приведем примеры разновидностей форм циклов:

В каждом случае только одна вершина цикла находится в незаполненной клетке. Ее называют началом цикла и определяют по наибольшему нарушению условия оптимальности (6), т.е. по максимальной оценке . Клетке начала цикла присваивают знак «+», во всех остальных вершинах цикла знаки чередуют «–»,«+» и т.д. Из клеток цикла со знаками «–» выбирают ту, в которой находится минимальный груз. Это и будет то количество груза, которое нужно перераспределить по циклу, т.е. в клетке со знаком «+» это количество груза прибавляется, а со знаком «–» – вычитается. Клетки, которые не задействованы в цикле, остаются неизменными.

Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Z min .

⇐ Предыдущая12345678Следующая ⇒

Похожая информация:

Поиск на сайте:

Методов формирования опорного плана в транспортной задаче придумано немало, но, пожалуй, самый простой из них – это метод Северо-Западного угла . Алгоритм заполнения клеток транспортной таблицы в его случае сводится к следующему: сначала заполняется клетка в верхнем левом угле («северо-западном» углу), затем следующая клетка справа и т.д., пока не заполнится вся строка.

Транспортная задача: метод Северо-Западного угла

Затем мы переходим ко второй строке и снова заполняем ее слева направо. И так далее.

Метод Северо-Западного угла, в самом деле, прост и понятен, но его недостаток – низкая эффективность. Сформированный с его помощью план в большинстве случаев не является оптимальным.

Формирование опорного плана методом Северо-Западного угла

Итак, у нас имеется транспортная таблица с исходными данными.

Формирование опорного плана начинаем с внесения в верхнюю левую клетку максимально возможного объема перевозки.

Запасы на складе A 1 закончились, поэтому в оставшиеся ячейки данной строки ставим прочерки. Затем переходим к следующей строке и заполняем ее ячейки слева направо.

Переходим к третьей строке и тоже заполняем ее слева направо.

Все, нами получен опорный план. Еще раз отмечу, что при методе «Северо-Западного угла» транспортная таблица просто заполняется в направлении сверху вниз и слева-направо.

Галяутдинов Р.Р.

© Копирование материала допустимо только при указании прямой гиперссылки на источник: Галяутдинов Р.Р.

ЗАКРЫТАЯ ТРАНСПОРТНАЯ ЗАДАЧА

Рассмотрим закрытую транспортную задачу. Обозначим через x ij – количество груза, перевозимого из пункта A i в пункт B j . Условия закрытой транспортной задачи запишем в распределительную таблицу, которую будем использовать для нахождения решения.

Математическая модель закрытой транспортной задачи имеет вид

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

Оптимальным решением задачи является матрица

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

Рассмотрим каждый из приведенных выше этапов.

Условия задачи и ее исходное опорное решение будем записывать в распределительную таблицу. Клетки, в которых поместим грузы, называются занятыми, им соответствуют базисные переменные опорного плана. Остальные клетки – незанятые , или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы . Существует несколько способов нахождения опорного плана:

· метод северо-западного угла;

· метод минимальной стоимости;

· метод двойного предпочтения и т.д.

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

Метод северо-западного угла . В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки х 11 («северо-западная» часть таблицы), продолжается вниз и вправо (по диагонали) и заканчивается в клетке неизвестного x mn .

Метод минимальной (наименьшей) стоимости (минимального тарифа, минимального элемента).

Исходный опорный план, построенный методом северо-западного угла, как правило, оказывается весьма далеким от оптимального, так как при его определении совершенно игнорируется величины затрат c ij . Поэтому требуются в дальнейших расчетах много итераций для достижения оптимального плана. Число итераций можно сократить, если исходный план строить по более рациональному правилу «минимального элемента». Сущность его состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной c ij .

Решение транспортной задачи методом северо-западного угла

Если такая клетка не единственная, то лучше заполнять ту, по вертикали или по горизонтали которой встречаются большие c ij , а в принципе заполняется любая из них.

Пусть это будет клетка (i, j). Запишем в эту клетку x ij = min(a i , b j ). Если a i < b j , то запасы поставщика A i исчерпаны, а потребность B j стала Поэтому, не принимая более во внимание i-ю сроку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. Для случая a i > b j из рассмотрения исключается j-й столбец, а запасы A i полагаются равными Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности – удовлетворены. Необходимо отметить, что при наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными, однако они, несомненно, ближе к оптимальному, чем план, составленный по методу северо-западного угла.

Метод двойного предпочтения. В модификации метода минимальной стоимости «двойного предпочтения» отмечают клетки с наименьшими стоимостями перевозок сначала по каждой строке, а затем по каждому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотмеченные клетки с наименьшими стоимостями. При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок.

Пример составления начального распределения методом северо-западного угла показан в табл. 3.1.

Таблица 3.1

Порядок заполнения клеток: (А 1 ;В 1), (А 1 ;В 2), (А 2 ;В 2), (А 2 ;В 3), (А 3 ;В 3), (А 3 ;В 4). Число занятых клеток равно m + n – 1 = 3 + 4 – 1 = 6. Суммарные затраты на реализацию данного плана перевозок составят

Z опт = 4·30 + 5·30 + 3·70 + 6·30 + 7·10 + 4·110 = 1170.

Пример начального распределения методом наименьших стоимостей для тех же исходных данных, что и ранее, представлен в табл.

Таблица 3.2

Порядок заполнения клеток: (А 2 ;В 1), (А 3 ;В 2), (А 2 ;В 4), (А 1 ;В 3), (А 1 ;В 4), (А 3 ;В 4). Суммарные затраты на реализацию данного плана перевозок составляют

Z опт = 1·30 + 2·100 + 2·70 + 2·40 + 3·20 + 4·20 = 590.

Пример начального распределения методом двойного предпочтения для тех же исходных данных, что и ранее, представлен в табл. 3.3.

Таблица 3.3

Порядок заполнения клеток: (А 2 ;В 1), (А 3 ;В 2), (А 1 ;В 3), (А 2 ;В 4), (А 1 ;В 4), (А 3 ;В 4). Суммарные затраты на перевозки, представленные в табл. 3.3, составляют

Z опт = 1·30 + 2·100 + 2·40 + 2·70 + 3·20 + 4·20 = 590.

Следовательно, опорные планы, построенные методами наименьших стоимостей, значительно ближе к оптимальному плану, чем план, составленный по методу северо-западного угла.

При распределении грузов может оказаться, что количество занятых клеток меньше, чем m + n – 1 . Такой план называется вырожденным. В этом случае недостающее их число заполняется клетками с нулевыми поставками такие клетки называют условно занятыми .

Нулевые поставки помещают в незанятые клетки с учетом наименьшего тарифа таким образом, чтобы в каждых строке и столбце было не менее чем по одной занятой клетке.

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (i,j), подлежащую заполнению, т.е. в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.

Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6

Таблица 6

Распределяем запасы первого поставщика. Так как его запасы меньше запросов первого потребителя, то в клетку (1,1) записываем перевозку и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя.

Распределяем запасы второго поставщика. Так как его запасы, меньше запросов первого потребителя, то записываем в клетку (2,1) перевозку и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя.

Распределяем запасы третьего поставщика. Так как его запасы больше запросов первого потребителя, то записываем в клетку (3,1) перевозку и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика.

Распределяем запасы третьего поставщика. Так как его запасы меньше запросов второго потребителя, то в клетку (3,2) записываем перевозку и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя.

Распределяем запасы четвертого поставщика. Так как его запасы больше запросов второго потребителя, то записываем в клетку (4,2) перевозку и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика.

Распределяем запасы четвертого поставщика. Так как его запасы меньше запросов третьего потребителя, то в клетку (4,3) записываем перевозку и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов третьего потребителя, то в клетку (5,3) записываем перевозку и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов четвертого потребителя, то в клетку (5,4) записываем перевозку и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы равны запросам пятого потребителя, то в клетку (5,5) записываем перевозку и исключаем из рассмотрения пятого поставщика и пятого потребителя.

Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены.

Результаты построения опорного решения приведены в таблице 7.

БЛОК-СХЕМА (АЛГОРИТМ РЕШЕНИЯ)

Западного

Этап I. Поиск первого опорного плана .

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен c 11 =7. Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

x 11 = min(20,25) = 20.

Искомый элемент равен c 22 =7. Для этого элемента запасы равны 55, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x 22 = min(55,40) = 40.

Искомый элемент равен c 23 =0. Для этого элемента запасы равны 15, потребности 50. Поскольку минимальным является 15, то вычитаем его.

x 23 = min(15,50) = 15.

Искомый элемент равен c 33 =10. Для этого элемента запасы равны 45, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x 33 = min(45,35) = 35.

Искомый элемент равен c 34 =2. Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его.

x 34 = min(10,30) = 10.

Искомый элемент равен c 44 =7. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x 44 = min(70,20) = 20.

Искомый элемент равен c 45 =8. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его.

x 45 = min(50,45) = 45.

Потребности

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 7*20 + 5*5 + 7*40 + 0*15 + 10*35 + 2*10 + 7*20 + 8*45 + 0*5 = 1315

Этап II. Улучшение опорного плана .

предварительные потенциалы

u 4 + v 4 = 7; -6 + u 4 = 7; u 4 = 13

u 4 + v 5 = 8; 13 + v 5 = 8; v 5 = -5

u 4 + v 6 = 0; 13 + v 6 = 0; v 6 = -13

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
• (3;1): 8 + 7 > 1; ? 31 = 8 + 7 - 1 = 14
• (3;2): 8 + 9 > 4; ? 32 = 8 + 9 - 4 = 13
• (4;1): 13 + 7 > 3; ? 41 = 13 + 7 - 3 = 17
• (4;2): 13 + 9 > 4; ? 42 = 13 + 9 - 4 = 18
• (4;3): 13 + 2 > 2; ? 43 = 13 + 2 - 2 = 13

max(6,14,13,17,18,13) = 18

Выбираем максимальную оценку свободной клетки (4;2): 4

Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (4,2 > 4,4 > 3,4 > 3,3 > 2,3 > 2,2).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 2 + v 1 = 5; 7 + u 2 = 5; u 2 = -2

u 2 + v 2 = 7; -2 + v 2 = 7; v 2 = 9

u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2

u 3 + v 3 = 10; 2 + u 3 = 10; u 3 = 8

u 3 + v 4 = 2; 8 + v 4 = 2; v 4 = -6

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
• (1;5): 0 + 13 > 6; ? 15 = 0 + 13 - 6 = 7
• (1;6): 0 + 5 > 0; ? 16 = 0 + 5 - 0 = 5
• (2;5): -2 + 13 > 3; ? 25 = -2 + 13 - 3 = 8
• (2;6): -2 + 5 > 0; ? 26 = -2 + 5 - 0 = 3
• (3;1): 8 + 7 > 1; ? 31 = 8 + 7 - 1 = 14
• (3;2): 8 + 9 > 4; ? 32 = 8 + 9 - 4 = 13
• (3;5): 8 + 13 > 6; ? 35 = 8 + 13 - 6 = 15
• (3;6): 8 + 5 > 0; ? 36 = 8 + 5 - 0 = 13

max(6,7,5,8,3,14,13,15,13) = 15

Выбираем максимальную оценку свободной клетки (3;5): 6

Для этого в перспективную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (3,5 > 3,3 > 2,3 > 2,2 > 4,2 > 4,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 2 + v 1 = 5; 7 + u 2 = 5; u 2 = -2

u 2 + v 2 = 7; -2 + v 2 = 7; v 2 = 9

u 4 + v 2 = 4; 9 + u 4 = 4; u 4 = -5

u 4 + v 5 = 8; -5 + v 5 = 8; v 5 = 13

u 3 + v 5 = 6; 13 + u 3 = 6; u 3 = -7

u 3 + v 4 = 2; -7 + v 4 = 2; v 4 = 9

u 4 + v 6 = 0; -5 + v 6 = 0; v 6 = 5

u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
• (1;4): 0 + 9 > 8; ? 14 = 0 + 9 - 8 = 1
• (1;5): 0 + 13 > 6; ? 15 = 0 + 13 - 6 = 7
• (1;6): 0 + 5 > 0; ? 16 = 0 + 5 - 0 = 5
• (2;4): -2 + 9 > 2; ? 24 = -2 + 9 - 2 = 5
• (2;5): -2 + 13 > 3; ? 25 = -2 + 13 - 3 = 8
• (2;6): -2 + 5 > 0; ? 26 = -2 + 5 - 0 = 3

max(6,1,7,5,5,8,3) = 8

Выбираем максимальную оценку свободной клетки (2;5): 3

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (2,5 > 2,2 > 4,2 > 4,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 2 + v 1 = 5; 7 + u 2 = 5; u 2 = -2

u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2

u 2 + v 5 = 3; -2 + v 5 = 3; v 5 = 5

u 3 + v 5 = 6; 5 + u 3 = 6; u 3 = 1

u 3 + v 4 = 2; 1 + v 4 = 2; v 4 = 1

u 4 + v 5 = 8; 5 + u 4 = 8; u 4 = 3

u 4 + v 2 = 4; 3 + v 2 = 4; v 2 = 1

u 4 + v 6 = 0; 3 + v 6 = 0; v 6 = -3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (3;1): 1 + 7 > 1; ? 31 = 1 + 7 - 1 = 7
• (4;1): 3 + 7 > 3; ? 41 = 3 + 7 - 3 = 7
• (4;3): 3 + 2 > 2; ? 43 = 3 + 2 - 2 = 3

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 3 + v 5 = 6; -6 + v 5 = 6; v 5 = 12

u 2 + v 5 = 3; 12 + u 2 = 3; u 2 = -9

u 2 + v 3 = 0; -9 + v 3 = 0; v 3 = 9

u 4 + v 5 = 8; 12 + u 4 = 8; u 4 = -4

u 4 + v 2 = 4; -4 + v 2 = 4; v 2 = 8

u 4 + v 6 = 0; -4 + v 6 = 0; v 6 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (1;2): 0 + 8 > 3; ? 12 = 0 + 8 - 3 = 5
• (1;3): 0 + 9 > 4; ? 13 = 0 + 9 - 4 = 5
• (1;5): 0 + 12 > 6; ? 15 = 0 + 12 - 6 = 6
• (1;6): 0 + 4 > 0; ? 16 = 0 + 4 - 0 = 4
• (4;3): -4 + 9 > 2; ? 43 = -4 + 9 - 2 = 3

max(5,5,6,4,3) = 6

Выбираем максимальную оценку свободной клетки (1;5): 6

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (1,5 > 1,1 > 3,1 > 3,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7

u 3 + v 1 = 1; 7 + u 3 = 1; u 3 = -6

u 3 + v 4 = 2; -6 + v 4 = 2; v 4 = 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (2;4): -3 + 8 > 2; ? 24 = -3 + 8 - 2 = 3
• (4;1): 2 + 7 > 3; ? 41 = 2 + 7 - 3 = 6
• (4;3): 2 + 3 > 2; ? 43 = 2 + 3 - 2 = 3
• (4;4): 2 + 8 > 7; ? 44 = 2 + 8 - 7 = 3

max(3,6,3,3) = 6

Выбираем максимальную оценку свободной клетки (4;1): 3

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (4,1 > 4,5 > 1,5 > 1,1).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 5 = 6; 0 + v 5 = 6; v 5 = 6

u 2 + v 5 = 3; 6 + u 2 = 3; u 2 = -3

u 2 + v 3 = 0; -3 + v 3 = 0; v 3 = 3

u 4 + v 5 = 8; 6 + u 4 = 8; u 4 = 2

u 4 + v 1 = 3; 2 + v 1 = 3; v 1 = 1

u 3 + v 1 = 1; 1 + u 3 = 1; u 3 = 0

u 3 + v 4 = 2; 0 + v 4 = 2; v 4 = 2

u 4 + v 2 = 4; 2 + v 2 = 4; v 2 = 2

u 4 + v 6 = 0; 2 + v 6 = 0; v 6 = -2

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(4;3): 2 + 3 > 2; ? 43 = 2 + 3 - 2 = 3

Выбираем максимальную оценку свободной клетки (4;3): 2

Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (4,3 > 4,5 > 2,5 > 2,3).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 5 = 6; 0 + v 5 = 6; v 5 = 6

u 2 + v 5 = 3; 6 + u 2 = 3; u 2 = -3

u 2 + v 3 = 0; -3 + v 3 = 0; v 3 = 3

u 4 + v 3 = 2; 3 + u 4 = 2; u 4 = -1

u 4 + v 1 = 3; -1 + v 1 = 3; v 1 = 4

u 3 + v 1 = 1; 4 + u 3 = 1; u 3 = -3

u 3 + v 4 = 2; -3 + v 4 = 2; v 4 = 5

u 4 + v 2 = 4; -1 + v 2 = 4; v 2 = 5

u 4 + v 6 = 0; -1 + v 6 = 0; v 6 = 1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

• (1;2): 0 + 5 > 3; ? 12 = 0 + 5 - 3 = 2
• (1;6): 0 + 1 > 0; ? 16 = 0 + 1 - 0 = 1

Выбираем максимальную оценку свободной клетки (1;2): 3

Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Потребности

Цикл приведен в таблице (1,2 > 1,5 > 2,5 > 2,3 > 4,3 > 4,2).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 5) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.

Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 2 = 3; 0 + v 2 = 3; v 2 = 3

u 4 + v 2 = 4; 3 + u 4 = 4; u 4 = 1

u 4 + v 1 = 3; 1 + v 1 = 3; v 1 = 2

u 3 + v 1 = 1; 2 + u 3 = 1; u 3 = -1

u 3 + v 4 = 2; -1 + v 4 = 2; v 4 = 3

u 4 + v 3 = 2; 1 + v 3 = 2; v 3 = 1

u 2 + v 3 = 0; 1 + u 2 = 0; u 2 = -1

u 2 + v 5 = 3; -1 + v 5 = 3; v 5 = 4

u 4 + v 6 = 0; 1 + v 6 = 0; v 6 = -1

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u i + v j ? c ij .

Минимальные затраты составят: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450

Анализ оптимального плана .

Из 2-го склада необходимо груз направить в 3-й магазин (15), в 5-й магазин (45)

Из 3-го склада необходимо груз направить в 1-й магазин (15), в 4-й магазин (30)

Из 4-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин (35)

На 4-ом складе остался невостребованным груз в количестве 5 ед.

Оптимальный план является вырожденным, так как базисная переменная x 46 =0.