Математические методы в экономике
Главная | Первоначальный план перевозок | Регистрация | Вход
 
Пятница, 29.03.2024, 09:25
Приветствую Вас Гость
Главное меню
Статистика
Форма входа

Первоначальный план

Транспортная задача относится к задачам линейного программирования, и ее можно было бы решить симплекс-методом. Но поскольку система ограничений транспортной задачи проще, чем система ограничений ОЗЛП, то это дает возможность вместо использования объемных симплекс-таблиц применить более удобный метод, который состоит из следующих этапов:

1. Составление первоначального плана перевозок;

2. Последовательные улучшения плана перевозок (перераспределение поставок) до тех пор, пока план перевозок не станет оптимальным.

Решение ОЗЛП начинается с нахождения опорного плана. Для транспортной задачи такой план всегда существует. Опишем два метода составления опорного плана (первоначального плана перевозок).

Составление первоначального плана перевозок с помощью метода северо-западного угла

Составление первоначального плана перевозок начнем с перевозки запасов поставщика A1. Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя B1, затем B1 и так далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1,1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика A1 не окажется меньше заказа очередного потребителя. Для выполнения этого заказа используем остатки запаса первого поставщика, а недостающую часть добавим из запасов поставщика A1, то есть переместимся на следующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика A1, затем A1 и так далее.

Проиллюстрируем это на следующем примере:

Распределяя запасы поставщика A1 сначала потребителю B1 , а затем B2, получаем: x11 = 100, x12 = 40. После этого у поставщика A1 остается еще 20 единиц груза, а потребителю B1 нужно 80 единиц. Удовлетворим спрос потребителя B3, отправив ему 20 единиц груза, оставшихся у поставщика A1, 30 единиц груза от поставщика A2 и 30 единиц груза от A3. Следовательно,

x13 = 20 , x23 = 30 и x33 = 30,

причем у поставщика A3 остается 60 последних единиц груза. Этот груз и отправим потребителю B4. Таким образом x34 = 60, все запасы груза вывезены и все потребители удовлетворены.

Теперь мы можем подсчитать общую стоимость всех перевозок по данному плану:

z = 4 × 100 + 8 × 40 + 10 × 20 + 2 × 30 + 6 × 30 + 5 × 60 = 1460

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

Составление первоначального плана перевозок с помощью метода наименьшей стоимости

Построение плана начнем с клетки с наименьшим тарифом перевозок. При наличии нескольких клеток с одинаковыми тарифами выберем любую из них. Пусть это будет клетка (i, j). Запишем в эту клетку элемент xij = min(ai,bj). Если ai < bj, то запасы поставщика Ai исчерпаны, а потребителю Bj требуется еще b'j = bj - ai единиц груза. Поэтому, не принимая более во внимание i-ю строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. В случае ai > bj из рассмотрения исключается j-й столбец, а запасы Ai полагаются равными a'i = ai - bj. Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности удовлетворены.

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

Сформируем теперь первоначальный план по методу наименьшей стоимости для рассмотренного в предыдущем методе примера и сравним результаты. Поскольку наименьший тариф (число 2) стоит в клетке (2,3), то запишем в эту клетку элемент x23 = 30 . Тогда b'3 = 50, а 2-ю строку таблицы можно больше не учитывать. Среди оставшихся клеток имеются три клетки с наименьшим тарифом перевозок, равным 4: (1,1); (3,1) и (3,2). Выберем, например, клетку (1,1) и запишем в нее число x11 = 100. Получаем, что a'1 = 60, а 1-й столбец таблицы больше не рассматриваем. Теперь наименьший тариф, равный 4, проставлен в клетке (3,2), поэтому x32 = 40, b'3 = 50 и 2-й столбец больше не нужен. Далее выбираем клетку (1,4) с тарифом 5 и пишем в нее x14 = 60. Исключив из рассмотрения сразу 1-ю строку и 4-ый столбец (поскольку a'1 = b4 = 60), переходим к последней клетке (3,3), в которую записываем перевозку x33 = 50.

Найдем суммарную стоимость перевозок по этому плану:

z = 4 × 100 + 5 × 60 + 2 × 30 + 4 × 40 + 6 × 50 = 1220

Сравнивая это значение со стоимостью плана, полученного по методу северо-западного угла, видим, что 1220 < 1460, то есть мы получили более выгодный план перевозок.


Copyright MyCorp © 2024Бесплатный конструктор сайтов - uCoz