|
Нахождение первоначального базисного распределенияПоставок Этап 1. Одним из возможных методов нахождения первоначального базисного распределения поставок являетсяметод"северо-западного угла", иллюстрируемый следующим примером. Задача 5.3. Найти первоначальное базисное распределение поставок для транспортной задачи 5.1. Решение. Дадим переменной x11 максимально возможное значение или, иными словами, максимально возможную поставку в клетку В результате получаем следующее исходное определение поставок (таблице 5.5.2).
Таблица 5.5.2
Число заполненных клеток в полученном распределении оказалось равным m + n – 1= 3 + 4 – 1=6, т.е. числу основных (базисных) переменных. Это, конечно, не случайно. Действительно, на каждом шаге (кроме последнего) данного метода из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец, и строка. Поэтому число заполненных клеток (число шагов) на единицу меньше, чем сумма числа строк и столбцов таблицы поставок, т.е. равно m + n – 1. Оказывается, что эта особенность шагов метода "северо-западного угла" служит причиной того, что полученное распределение является базисным. Существенный недостаток метода "северо-западного угла" состоит в том, что он построен без учета значений коэффициентов затрат задачи. С другой стороны, данный метод допускает модификацию, лишенную этого недостатка: на каждом шаге максимально возможную поставку следует давать не в "северо-западную" клетку оставшейся таблицы, а в клетку с наименьшим коэффициентом затрат. При этом распределение поставок оказывается, вообще говоря, ближе к оптимуму, чем распределение, полученное методом "северо-западного угла". Такой метод получения опорного плана называется методом наименьших затрат, или методом минимального элемента. Рассмотрим его на следующем примере. Задача 54. Найти методом наименьших затрат первоначальное распределение поставок в задаче 5.2. Решение. Находим в таблице поставок (табл. 5.1) клетки с наименьшим коэффициентом затрат. Таких клеток две – (1;1) и (2;1) с коэффициентами затрат, равными 1. Сравним максимально возможные поставки для этих клеток: для клетки (1;1) x11 = min {60,20} = 20, для клетки (2;1) x2 =min {120,20} = 20. Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам, в клетку (2;1). В результате спрос первого потребителя удовлетворён, и первый столбец таблицы поставок выпадает из последующего рассмотрения (таблице 5.5.3).
Таблица 5.5.3
В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с12 = с24 = 2. Сравним максимально возможные поставки для этих клеток: для клетки (1;2) х12 = min {60,110} = 60; для клетки (2;4) х24 = min {120-20,110} = 100. Даем поставку в клетку (2;4), для которой максимально возможная поставка оказалась больше Х24 = 100. При этом из рассмотрения выпадает вторая строка таблицы поставок (таблице5.5.4). Таблица 5.5.4
Аналогично продолжая заполнение таблицы поставок шаг за шагом получаем х12 = min {60, 100} = 60, x32 = min {100, 110-60} = 50, x34 = min{100–50, 110-100} = 10, x33 = min {100-60, 40} = 40 (таблице 5.5.5).
Таблица 5.5.5
Сравним найденное распределение поставок с распределением, полученным для той же задачи по методу «северо-западного угла» (см. задачу 5.3, таблице 5.5.2). Вычислим для каждого из этих распределений суммарные затраты в денежных единицах В задаче 5.3: В задаче 5.4: Как и ожидалось, при использовании метода "северо-западного угла" суммарные затраты больше, чем при применении метода наименьших затрат. Таким образом, во втором случае мы находимся ближе (по числу необходимых шагов) к оптимуму, чем в первом. Перейдем к следующему этапу: поиску оптимального решения.
Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|