Первым шагом при решении транспортной задачи является получение допустимого решения, которое называют исходный опорный план. Исходный план можно легко получить, используя простой алгоритм, разработанный Данцигом и названный Чарнсом и Купером “правилом северо-западного угла”, хотя исходный план, полученный этим способом, как правило, весьма далек от оптимального. “Правило северо-западного угла” формулируется следующим образом: 1. Начать с северо-западного угла исходной таблицы – клетки (1,1), куда дать максимально возможную поставку:
х 11 =min⎨А1,В1⎬. 2. Следующую максимально возможную поставку дать либо в клетку (1,2), либо в клетку (2,1), в зависимости от результата первого шага. 3. Продолжить этот процесс шаг за шагом от северо-западного до юго-восточного угла таблицы. Таким образом, в нашем примере (см. табл. 2.3.3) процесс определения исходного плана происходит следующим образом: В клетку (1,1) даем максимально возможную поставку: х 11 =min⎨50,40⎬=40. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы выпадает из последующего рассмотрения. Переходим к клетке (1,2) и даем в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 40 единиц своей продукции и у него осталось только 50 – 40 = 10 единиц, получим х 12=min⎨10,85⎬=10. После этого объемы 1-го производителя
126 полностью реализованы и из рассмотрения выпадает первая строка таблицы. В оставшейся таблице снова находим «северо-западный угол» и т.д. В результате получаем исходное распределение поставок (см. табл. 2.3.3). Число заполненных клеток в полученном распределении оказалось равным m+n–1=3+3–1 = 5. Это не случайно. Действительно, на каждом шаге (кроме последнего) из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец и строка. Поэтому число заполненных клеток на единицу меньше, чем сумма числа строк и столбцов, т.е. равно m+n–1. Справедлива теорема (которую мы примем без доказательств) утверждающая, что в оптимальном решении число заполненных клеток (т.е. основных, так называемых базисных переменных) должно быть равно m+n–1. Существенный недостаток метода “северо-западного угла” состоит в том, что он построен без учета значений транспортных издержек. Можно модифицировать данный метод, избавившись от этого недостатка: на каждом шаге максимально возможную поставку следует давать не в “северо-западную” клетку оставшейся таблицы, а в клетку с наименьшим значением транспортных издержек. При этом распределение поставок оказывается, вообще говоря, ближе к оптимуму, чем распределение, полученное методом “северо-западного угла”. Такой метод получения исходного плана называется методом наименьших затрат. Исходный план, полученный данным методом, приведен в табл. 2.3.4.
Ви переглядаєте статтю (реферат): «Исходный опорный план» з дисципліни «Математична економіка»
