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

Составить экономико-математическую модель и решить задачу с помощью надстройки «Поиск решения».

Решение:

Экономико-математическая модель:

Целевая функция:

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

Ограничения:

x ij – равное 1 показывает, что i-го работника необходимо назначить на выполнение j-ой работы.

Экономико-математическая модель задачи составлена. Решим эту задачу с использованием надстройки Excel «Поиск решения».

На рисунке 1 представлен ход работы утилиты «Поиск решения».

Рисунок 1 – Ход работы утилиты Поиск решения

На рисунке 2 представлен результат решения задачи.

Рисунок 2 – Результат решения задачи

Вывод: из рисунка 2 следует, что для того, чтобы общая величина затрат была минимальной необходимо для выполнения работы А1 назначить работника В4, А2 – В3, А3 – В5, А4 – В1, А5 – В2, при этом суммарные затраты будут минимальны и составят 25 ед.

Задача 2 Транспортная задача

Исходная информация транспортной задачи представлена в таблице 2.

Таблица 2 – Исходные данные

Определить:

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

2. приближенный план, схему перевозок, а также его стоимость методом минимального элемента;

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

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

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

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 3 (120-117). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу 3.

Таблица 3 – Распределительная таблица

Первый опорный план начинается заполняться с верхнего левого угла (таблица 4).

Таблица 4 – Опорный план 1

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

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

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

F(x) = 3*30 + 6*10 + 4*17 + 8*23 + 6*7 + 1*30 + 0*3 = 474

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

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

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

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

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

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

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

(1;3): 0 + 10 > 5; ∆ 13 = 0 + 10 - 5 = 5

(1;4): 0 + 5 > 2; ∆ 14 = 0 + 5 - 2 = 3

(1;5): 0 + 4 > 0; ∆ 15 = 0 + 4 - 0 = 4

(2;5): -2 + 4 > 0; ∆ 25 = -2 + 4 - 0 = 2

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

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

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

Таблица 5 – Цикл 1

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

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

Таблица 6 – Опорный план 2

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

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

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

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

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

(2;1): 3 + 3 > 3; ∆ 21 = 3 + 3 - 3 = 3

(2;5): 3 -1 > 0; ∆ 25 = 3 -1 - 0 = 2

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

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

Таблица 7 – Цикл 2

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

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

Таблица 8 – Опорный план 3

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

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

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

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

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

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

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

(3;2): 1 + 4 > 3; ∆ 32 = 1 + 4 - 3 = 2

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

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

Таблица 9 – Цикл 3

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

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

Таблица 10 – Опорный план 4

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

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

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

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

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

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

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

(1;5): 0 + 1 > 0; ∆ 15 = 0 + 1 - 0 = 1

(2;5): 0 + 1 > 0; ∆ 25 = 0 + 1 - 0 = 1

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

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

Таблица 11 – Цикл 4

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

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

Таблица 12 – Опорный план 5

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

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

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

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

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

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

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

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

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

Минимальные затраты составят:

F(x) = 3*7 + 5*30 + 0*3 + 3*23 + 4*17 + 3*10 + 1*30 = 368

Схема перевозок:

из 1-го склада необходимо груз направить 1-му потребителю в количестве 7 ед., 3-му потребителю в количестве 30 ед.;

из 2-го склада необходимо груз направить 1-му потребителю – 23 ед., 2-му потребителю – 17ед.;

из 3-го склада необходимо груз направить второму потребителю – 10 ед., 4-му – 30 ед.

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

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

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-08-26

Заполнение распределительной таблицы начинают с клетки (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 . Такой план называется вырожденным. В этом случае недостающее их число заполняется клетками с нулевыми поставками такие клетки называют условно занятыми .

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

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

> ПРИМЕР 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. Найти первоначальный план поставок северо- западного угла.

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

Лекция №3.

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

1. Медиатор. Виды медиаторов. Свойства медиаторов.

2. Электрические и тормозные синапсы. Особенности передачи сигнала.

3. Пути фармакологической регуляции синаптической передачи возбуждения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этап 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.