Экономико-математическая модель транспортной задачи

Лабораторное занятие 9

Тема: Получение первоначального опорного плана в транспортных задачах

Время 4 часа

Вопросы для контроля:

1. Подклассом, какого класса задач являются транспортные задачи?

2. В чем заключаются особенности транспортных задач как задач линейного программирования?

3. Сколько базисных переменных должно быть в первоначальном опорном плане?

4. Какие методы существуют для получения первоначального опорного плана?

5. Какое название имеет симплекс-метод для транспортных задач?

6. В чем заключается существо метода «северо-западного угла»? В чем его достоинства и недостатки?

7. В чем заключается существо метода «наименьших затрат»? В чем его достоинства и недостатки?

8. В чем заключается существо метода Фогеля? В чем его достоинства и недостатки?

9. Какая транспортная задача называется закрытой, открытой?

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

Теоретическая часть

Экономико-математическая модель транспортной задачи

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

Задача 13.1. Построить экономико-математическую модель следующей задачи. Имеются три поставщика А₁, А₂, А3 и четыре потребителя В₁, В₂, В₃, В₄. Возможности поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик – потребитель» сведены в таблицу поставок (таблица 13.1).

Таблица 13.1- Исходные данные к задаче 13.1

В левом верхнем углу произвольной (i, j)-клетки (i - номер строки, j- номер столбца) записывается, так называемый, коэффициент затрат - затраты на перевозку единицы груза от i-гo поставщика к j-мy потребителю, Например, в левом верхнем углу клетки (1, 4) записано число 3, следовательно, перевозка единицы груза от l-ro поставщика к 4-му потребителю обойдется в 3 условных денеж­ных единицы и т. д.

Задача ставится следующим образом.

Вычислить объемы перевозок для каждой пары «поставщик – потребитель» (x_ij) так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

З) суммарные затраты на перевозку были бы минимальны.

Решение. Построим математическую модель данной задачи.

Вычисляемый объем перевозки от i-ro поставщика к j-мy потребителю обозначим через x _ij и назовем поставкой клетки (i, j). Например, x_I2 - вычисляемый объем перевозки от 1­ - го поставщика ко 2-му потребителю или поставка клетки (1, 2) и т. д.

Заданные возможности поставщиков и спросы потребите­лей накладывают ограничения на значения вычисляемых неизвестных x_ij. Так; например, объем груза, забираемого от l-го поставщика, должен быть равен мощности этого поставщика - 60 едини­цам, т.е. x₁₁ + x_I2 + x_I3 + x ₁₄ = 60 (уравнение баланса по пер­вой строке).

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

x₁₁ + x_I2 + x₁₃ + x_I4 = 60,

x₂₁ + x₂₂ + x_2З + x₂₄ = 120,

x_3I + x₃₂ + x₃₃ + x₃₄ = 100. (13.1)

Аналогично, чтобы спрос каждого из потребителей был удов­летворен, подобные уравнения баланса составляем для каждого столбца таблицы поставок. Они составят систему линейных ограничений –равенств по потребностям: ­

x₁₁ + x₂₁ + x_ЗI= 20,

x_I2 + x₂₂ + x_З2 = 110,

x₁₃ + x_2З + x₃₃ = 40,

. x_I4 + x₂₄ + x_З4 = 110. (13.2)

Очевидно, что объем перевозимого груза не может быть отри­цательным, поэтому следует дополнительно предположить, что

x_ij ≥ 0 (i= 1, 2, 3; j= 1, 2, 3, 4). (13.3)

Суммарные затраты F на перевозку выражаются через коэффициенты затрат и поставки, образуя линейную форму:

F =1x₁₁ +2x₁₂ + 5x₁₃ + 3x₁₄ + 1x₂₁ + 6x₂₂ + 5x_2З + 2x₂₄ + 6x_З1 + 3x_З2 + 7x₃₃ + 4x_З4

(13.4)

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному смыслу). На множестве неотрuцательных решений систем ограничений (13.1) и (13.2) получить такое решение Х* = (x*₁₁, x*₁₂,..., x*₃₃, x* _З4), при котором линейная функция (13.4) принимает минимальное значение.

Особенности математической модели транс­портной задачи:.

- системы ограничений есть системы - уравнений (т.е. транспорт­ная задача задана в канонической форме);.

- коэффициенты при переменных системы ограничений равны единице или нулю;

- каждая переменная входит в систему ограничений два раза: один раз - в систему (13.1) и один раз - в систему '(13.2).

Для математической формулировки транспортной задачи в общей постановке обозначим через c_ij коэффициенты затрат, че­рез М_i; - мощности поставщиков, через N_j - мощности потре­бителей, где i = 1, 2,..., т; j = 1, 2,..., п; т - число поставщиков, п - число потребителей.

Тогда система ограничений примет вид

, (13.5)

. (13.6)

Система (13.5) включает в себя уравнение баланса по строкам, а система (13.6) - по столбцам таблицы поставок. Линейная функ­ция в данном случае

. (13.7)

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (13.5), (13.6) вычислить такое решение

X* = (x*₁₁, x*₁₂,..., x*_ij, …, x* _mn), при котором значение линейной функции (13.7) минимально.

Произвольное допустимое решение X =(x₁₁, x₁₂,..., x_ij, …, x _mn) системы ограничений (13.5), (13.6) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной x _ij и содержимое соответствующей клетки таблицы поставок будут отождествляться.

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

. (13.8)

Такие транспортные задачи называются закрытыми (говорят также, что транспортная задача в этом случае имеет закрытую модель). В противном случае транспортная задача называется открытой (открытая модель транспортной задачи).

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

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

Число r основных переменных транспортной задачи равно рангу системы линейных уравнений (максимальному числу ли­нейно независимых уравнений в системе ограничений).

Теорема 131. Ранг r системы уравнений (13.5, 13.6) при условии (13.8) равен т+п -1.

Прежде всего заметим, что уравнения системы (13.5, 13.6) при условии(13.8)линейно зависимы и, следовательно, ранг системы, не больше, чем m + n - 1.

Действительно, сравним сумму

(13.9)

первых т уравнений системы (сумму уравнений системы (13.5) с суммой

(13.10)

оставшихся п уравнений (суммой уравнений системы (13.6).

Согласно условию (13.8) правые части уравнений (13, 9, 13.10) совпадают. Левые части (13, 9, 13.10), являющиеся суммами все­возможных переменных x _ij данной задачи, также совпадают. Сле­довательно, совпадают уравнения (13, 9, 13.10), т.е. сумма первых т уравнений системы ограничений равна сумме оставшихся п уравнений системы ограничений: уравнения системы (13, 9, 13.10), линейно зависимы.

Докажем, что ранг r системы не меньше, чем т+п-1. Из ли­нейной алгебры известно, что если некоторые k переменных про­извольной системы линейных уравнений можно линейно выра­зить через остальные переменные системы, то ранг этой системы не меньше, чем k.

Выразим, например, переменные x _ij, входящие в первый стол­бец и первую строку таблицы 13.1, через остальные переменные x _ij, где i = 2, 3,..., т, j = 2, 3,...., п. Сначала получим такие выражения для переменных, отличных от х ₁₁.

Для каждой переменной х _lj первой строки, где j = 2, 3,..., п, воспользуемся уравнением ба­ланса по соответствующему столбцу:

(13.11)

Аналогично для каждой переменной Х_i1 первого столбца, где i = 2, 3,..., т, воспользуемся уравнением баланса по соответствующей строке:

(13.12)

Для получения выражения для х ₁₁ воспользуемся, например, уравнением баланса по первой строке:

(13.3)

Подставляя в правую часть уравнения (13.3) выражения для х _lj, где j = 2, 3,..., п из уравнения (13.2), получаем выражение для x_ll.

Таким образом, т+п- 1 переменных этой задачи можно вы­разить через остальные тп-т-п+l переменные, т.е. ранг r системы r ≥ т + п - 1.

Сравнивая два полученных ограничения на ранг r системы (13.9, 13.10

(r ≥ т+п-l и r ≤ т+п-l), получаем, что r = m+п - 1.

Основное следствие теоремы 13.1 - число r основных (базисных) переменных закрытой транспортной задачи равно т+п–1, где т ­ число поставщиков, п - число потребителей.

Каждому разбиению переменных х _ij задачи на основные (базисные) и неосновные (свободные) соответствует базисное решение и, как следствие, заполнение таблицы поставок, которое также назовем базисным.

Иными словами, распределение поставок называется базисным, если пepеменные, соответствующие заполненным клет­кам, можно принять за основные переменные. Клетки, отвечающие базисным переменным, в дальнейшем будем называть базисны­ми, а клетки, соответствующие.- свободным переменным, - сво­бодными или пустыми. Поскольку в дальнейшем мы используем исключительно базисные распределения поставок, то термины «базисная клетка» и «заполненная клетка» будем считать равнозначными.

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

Методы получения начального базисного распределения поставок (первоначального опорного плана)

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

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

- метод наименьших затрат (метод минимального элемента);

- метод аппроксимации Фогеля

Начнем рассмотрение этих методов с метода северо-западного угла.

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

Существо метода покажем на конкретном примере.

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

Р е ш е н и е.

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

Предположим, что поставщик 1, обладающий мощностью доставки 60 единиц груза планирует доставить первому потребителю 20 единиц груза. Формально это реализуется тем, что переменной х₁₁ мы присваиваем значение 20 (т.е. х₁₁ = 20). Покажем это в таблице 13.2.

Таблица 13.2 – Таблица распределения методом «северо-западного угла»

После этого спрос l-го потребителя будет полностью удовлетворен (20 = 20). В результате о первый столбец табли­цы поставок выпадет из последующего рассмотрения (заполнен­ные клетки будем перечеркивать сплошной линией (клетка 1.1 таблицы 13.2). Клетки, выпавшие из последующего рассмотрения, перечеркиваются пунктирной линией (клетки 2.2 и 2.2 первого столбца). У поставщика 1 осталось не распределенными 60 – 20 = 40 единиц груза.

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (1.2). Второму потребителю требуется доставка 110 единиц груза, а у первого поставщика осталось в запасе 40 единиц груза. Поэтому спланируем: первый поставщик должен перевести второму получателю 40 единиц груза. Формально это означает, что х₁₂ должно принять значение равное 40 (х₁₂ = 40). Запишем это в правом нижнем углу клетки (1.2). Отметим эту клетку сплошной косой чертой, а клетки (1.3) и (1.4) – пунктирной линией (т.к. возможности первого поставщика уже полностью исчерпаны).

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (2.2). Второму потребителю требуется доставка 110 единиц груза, от первого поставщика ему уже спланировано 40 единиц груза, следовательно, ему не достает 110 – 4 = 70 единиц груза. В то же время у поставщика 2 имеется в наличии 120 (больше, чем 70) единиц груза. Спланируем доставку 70–ти единиц груза от поставщика 2 к потребителю 2. Формально это означает, что х₂₂ должно принять значение равное 70 (х₂₂ = 70). Запишем это в правом нижнем углу клетки (2.2). Отметим эту клетку сплошной косой чертой, а клетку (2.2) – пунктирной линией (т.к. потребности второго потребителя обеспечены полностью).

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (2.3). Третьему потребителю требуется доставка 40 единиц груза, в то время как у поставщика 2 остались не спланированными 120 – 70 = 50 единиц груза (больше, чем требуется третьему потребителю). Спланируем доставку 40–ка единиц груза от поставщика 2 к потребителю 3. Формально это означает, что х₂₃ должно принять значение равное 40 (х₂₃ = 40). Запишем это в правом нижнем углу клетки (2.3). Отметим эту клетку сплошной косой чертой, а клетку (3.2) – пунктирной линией (т.к. потребности третьего потребителя обеспечены полностью).

Из оставшихся клеток таблицы 13.2 вновь выделяем клетку соответствующую северо-западному углу. Это будет клетка (2.4). Четвертому потребителю требуется доставка 110 единиц груза, в то время как у поставщика 2 остались не спланированными 120 – 70 - 40 = 10 единиц груза (меньше, чем требуется четвертому потребителю). Спланируем доставку 10–ти единиц груза от поставщика 2 к потребителю 4. Формально это означает, что х₂₄ должно принять значение равное 10 (х₂₄ = 10). Запишем это в правом нижнем углу клетки (2.4). Отметим эту клетку сплошной косой чертой.

После выполнения всех этих действий не наполненной осталась только клетка (3, 4). Анализируя сложившуюся на этом шаге ситуацию, можно обнаружить, что неизрасходованными остались только 100 единиц груза третьего поставщика и четвертому потребителю не достает тоже ровно 100 единиц груза. Поэтому запланируем перевозки: поставщик 3 должен доставить потребителю 4 ровно 100 единиц груза. Формально это означает, что х₃₄ должно принять значение равное 100 (х₃₄ = 100). Запишем это в правом нижнем углу клетки (3.4). Отметим эту клетку сплошной косой чертой.

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

Кроме того, число заполненных клеток (клеток перечеркнутых сплошной линией) в полученном распределении оказа­лось равным т+п­ -1 = 3+4 -1 = 6, т.е. числу основных (базисных) переменных. Это тоже не случайно, т.к. на каждом шаге распределения (кроме последнего) из рассмотрения удалялись одна (один) строка (столбец), кроме последнего шага, где одновременно удалились один столбец и удалилась одна строка. Именно поэтому, число заполненных клеток (число шагов) на единицу меньше, чем сумма числа строк и столбцов таблицы поставок, т.е. равно m + n -1.

Именно эта последняя особенность метода «северо-западного угла» является условием того, что полученное первоначальное распределение является базисным (допустимым), т.е. опорным планом.

Основными достоинствами метода «северо-западного угла» являются простота и логичность распределения, а важнейшим недостатком то, что это распределение никак не учитывает коэффициенты затрат на перевозки и поэтому полученное опорное решение может оказаться достаточно далеко от оптимального (потребуется много шагов, чтобы от этого первоначального базисного плана перейти к оптимальному).

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

1. 2.2 Получение начального базисного распределения поставок методом «наименьших затрат»

Покажем существо применения этого метода на примере той же самой задачи 13.1.

Решение. Так как мы должны минимизировать стоимость перевозок, то отыскиваем в таблице поставок (таблица 13.1) клетку (клетки) с наименьшими коэффициентами затрат (в данном случае таких клеток 2 – клетки (1.1) и (2.1). Коэффициенты затрат в этих клетках равны между собой и равны 1.

Сравним максимально возможные поставки для этх клеток между собой. Для клетки (1, 1) - х₁₁ = min {60, 20} = 20. Для клетки (2, 1) - х₂₁ = min {120, 20} = 20. Так как они совпадают, то первое распределение поставок можно осуществить в любую из них. Пусть мы отдадим первую поставку поставщику 2. Формально это означает, что х₂₁ должно принять значение равное 20 (х₂₁ = 20). Запишем это в правом нижнем углу клетки (2.1) (таблица 8.3). Отметим эту клетку сплошной косой чертой. Потребности первого получателя полностью удовлетворены, поэтому остальные клетки первого столбца отметим пунктирной линией.

Таблица 8.3 – Таблица распределения методом «наименьших затрат»

На втором шаге из оставшихся клеток отберем те, у которых наименьшие коэффициенты затрат. Это клетки (1.2) и (2.4), (с₁₂ = с₂₄ = 2). Сравним максимально возможные поставки для этих клеток:

Для клетки (1.2) – х₁₂ = min { 120, 20} = 20.

Для клетки (2.4) – х₂₄ = min { 120 - 20, 110} = 100. Планируем очередную поставку в клетку (2.4) – для нее максимальные поставки оказались больше.

Формально это означает, что х₂₄ должно принять значение равное 120 – 20 = 100 (х₂₄ = 100). Запишем это в правом нижнем углу клетки (2.1) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Возможности второго поставщика полностью исчерпаны, поэтому вторая строка выпадает из дальнейшего рассмотрения (отметим остальные клетки второй строки (кроме клеток (2.1), (2.4) пунктирной линией.

На третьем шаге из оставшихся клеток отберем те, у которых наименьшие коэффициенты затрат. Это клетка (1.2), оставшаяся от второго шага. У первого поставщика имеется 60 единиц груза, поэтому спланируем: первый поставщик должен поставить второму потребителю 60 единиц груза. т.к. х¹² = min {60, 110} = 60/. Формально это означает, что х₁₂ должно принять значение равное 60 (х₁₂ = 60). Запишем это в правом нижнем углу клетки (1.2) (таблица 13.3). Отметим эту клетку сплошной косой чертой. При этом оказывается, что возможности первого поставщика полностью исчерпаны. Первая строка выпадает из дальнейшего рассмотрения (отметим остальные клетки второй строки (кроме клетки (1.2.) пунктирной линией).

На четвертом шаге возможности планирования существенно уменьшились, т.к. все запасы поставщиков 1 и 2 полностью исчерпаны.. Отыскиваем минимальные коэффициенты затрат у поставщика 3. Это клетка (3, 2) (с₃₂ = 3). Произведем планирование. Третий поставщик может поставить второму потребителю в принципе 100 единиц груза, а ему требуется 110, но ему уже спланировано от первого поставщика 60 единиц груза. Следовательно. На этом шаге мы можем спланировать ему только 110 – 60 = 50 единиц груза. Выполним такое планирование. Формально это означает, что х₃₂ должно принять значение равное 50 (х₃₂ = 50). Запишем это в правом нижнем углу клетки (3.2) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Потребности второго потребителя оказались полностью удовлетворены, поэтому из дальнейшего рассмотрения выпадает столбец 2.

На пятом шаге устанавливаем, что наименьший коэффициент затрат имеет клетка (3, 4) (с₃₄ = 4). У третьего поставщика осталось 100 – 50 = 50 единиц груза. Однако мы не можем все 50 единиц груза распределить потребителю 4, т.к. ему уже запланировано 100 единиц груза от второго поставщика. Следовательно, запланируем ему 110 – 100 = 10 единиц груза от третьего поставщика. Формально это означает, что х₃₄ должно принять значение равное 10 (х₃₄ = 10). Запишем это в правом нижнем углу клетки (3.4) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Потребности четвертого потребителя оказались полностью удовлетворены, поэтому из дальнейшего рассмотрения выпадает столбец 4.

На очередном шаге свободная клетка (3.1) имеет минимальный коэффициент затрат с₃₁ = 6, но эта клетка уже перечеркнута пунктирной линией, т.к. потребности первого потребителя полностью удовлетворены. Остается только выбрать клетку (3.3) с коэффициентом затрат с₃₃ = 7. спланируем доставку от третьего поставщика третьему потребителю (100 – 50 – 10 = 40 единиц груза). Формально это означает, что х₃₃ должно принять значение равное 40 (х₃₃ = 40). Запишем это в правом нижнем углу клетки (3.3) (таблица 13.3). Отметим эту клетку сплошной косой чертой. Потребности четвертого потребителя оказались полностью удовлетворены т возможности третьего поставщика полностью исчерпаны, поэтому из дальнейшего рассмотрения выпадает строка 3 и столбец 4.

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

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

В обоих случаях кортеж опорного плана в общем виде записывается одинаково X⁰ = (x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄).

При использовании метода северо-западного угла имеем (таблица 13. 2):

X⁰ _сзу = (20, 40, 0, 0, 0, 70, 40, 10, 0, 0, 0, 100).

Суммарные затраты в денежных единицах примут значение:

F⁰ _сзу = c₁₁ x₁₁+ c₁₂x₁₂ + c₁₃x₁₃ + c₁₄x₁₄ + c₂₁ x₂₁ + c₂₂ x₂₂ + c₂₃x₂₃ + c₂₄ x₂₄ + + c₃₁ x₃₁ + c₃₂ x₃₂ + c₃₃ x₃₃ + c₃₄ x₃₄ =

= 1*20 + 2*40 + 6*70 + 5*40 +2*10 +4*100 = 1140 ден. ед.

При использовании метода наименьших затрат имеем (таблица 13. 3):

X⁰ _НЗ = (0, 60, 0, 0, 20, 0, 0, 100, 0, 50, 4, 10).

Суммарные затраты в денежных единицах примут значение:

F⁰ _НЗ = c₁₁ x₁₁+ c₁₂x₁₂ + c₁₃x₁₃ + c₁₄x₁₄ + c₂₁ x₂₁ + c₂₂ x₂₂ + c₂₃x₂₃ + c₂₄ x₂₄ + + c₃₁ x₃₁ + c₃₂ x₃₂ + c₃₃ x₃₃ + c₃₄ x₃₄ =

= 2*60 + 1*20 + 2*100 + 3*50 +7*40 +4*10 = 810 ден. ед.

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

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

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

Однако мы еще не получили ответы на следующие вопросы:

1) полученный опорный план является допустимым?

2) не является ли полученный опорный план оптимальным?

3) каким образом перейти от первоначального опорного плана к оптимальному?

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

Получение первоначального опорного плана методом аппроксимации Фогеля

Рассмотрим метод и его применение на следующем конкретном примере.

Транспортная задача задана таблицей 10.4.

Таблица 10.4 – Исходные данные транспортной задачи (для метода Фогеля)

К исходной таблице добавим справа и снизу столбцов и строк.

Шаг 1. Заполняем первый дополнительный столбец (разности по строкам). В строке А₁ вычисляем разницу между двумя минимальными элементами (минимальный элемент равен 2, из оставшихся – минимальный равен 4, следовательно их разность 4 – 2 = 2). Записываем эту разность в строку А₁ в дополнительный столбец 1.

Выполняем аналогичные действия для строк А₂ и А₃. Получаем соответствующие значения 3 и 1. Записываем полученные значения в дополнительный столбец 1 (строки А₂, А₃ ).

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

Теперь из всех разностей (по строкам и по столбцам) выбираем максимальную (она равна 8 – столбец В₁) и в клетку с минимальным тарифом в строке (1 – строка A₂) записываем максимально возможную поставку – 70 и потребителя В₁ исключаем из списка.

Шаг 2. Исключив потребителя В₁ вновь проводим аналогичные действия по строкам и столбцам. Полученные значения записываем во второй дополнительный столбец и вторую дополнительную строку.

В данном случае максимальным является элемент равный 7 и в столбец В4, строку с минимальным элементом А1 = 2 записываем очередную поставку равную 80. Строку А1 (поставщика А1) исключаем из дальнейшего рассмотрения.

Шаг 3. Проводим аналогичные действия для оставшихся столбцов и строк исходной таблицы. Полученные результаты записываем в третий дополнительный столбец и третью дополнительную строку. На этом шаге максимальным является элемент в столбце В₂ = 4 и, следовательно в клетку А₂В₂ назначаем очередную поставку в 60 единиц. Потребителя В₂ исключаем из дальнейшего рассмотрения.

Шаг 4. Проводим аналогичные действия для оставшихся столбцов и строк исходной таблицы. Полученные результаты записываем в четвертый дополнительный столбец и четвертую дополнительную строку. На этом шаге максимальным является элемент в строке А₃ = 3 и, следовательно, в клетку А₃В₃ назначаем очередную поставку в 40 единиц. Поставщика А₂ исключаем из дальнейшего рассмотрения.

Шаг 4. Рассмотрению подлежит только строка А₃. Назначаем в клетку А₃В₃ (где минимальный элемент) поставку 140 единиц. Оставшиеся 10 единиц, распределяем в клетку А₃В₄.

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

Х⁽⁰⁾ =

Задача решена.

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

Критерий (правило) отбора первоначального опорного базисного плана. Особые случаи получения первоначального опорного плана

Из линейной алгебры известно, что если ранг системы линейных уравнений равен r и некоторые r переменных системы выражены через остальные переменные, то эти r переменных можно взять за основные (базисные).

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

Теорема 13.2. Если на каждом шаге заполнения таблицы поставок (любым из двух методов) возникает только одна заполненная клетка и при этом из последующего рассмотрения на каждом шаге (кроме последнего) выпадает либо одна строка, либо один столбец, то переменные, соответствующие заполненным клеткам можно принять за базисные.

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

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

Пусть также на (t + 1) – м шаге реализации метода заполнена (p, q) – я клетка и из дальнейшего рассмотрения выпала, например, р – я строка. Выразим переменную x_pq из уравнения баланса по р – й строке

. (13.4)

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

В случае же, если на (t+1) –м шаге из дальнейшего рассмотрения выпал q – й столбец, то x_pq следует выразить из уравнения баланса по q – му столбцу.

Подобные рассуждения следует последовательно провести для каждого из шагов заполнения таблицы поставок. Этим теорема 13.2 будет доказана.

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

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

Задача 13.2. Получить опорный план распределения поставок для транспортной задачи, заданной таблицей 13.4.

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

На первом шаге спланируем поставку 20 единиц груза от поставщика 1, запасы которого составляют 30 единиц груза, получателю 1 (х₁₁ = 20).

Таблица 13.4 – Исходные данные для задачи 13.2.

Запишем в клетку (1.1) х₁₁ = 20. При этом потребности первого получателя будут удовлетворены полностью и клетки (2.1) (3.1) перечеркнем пунктирной линией. Из дальнейшего рассмотрения выпадет столбец 1.

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

Продолжая использовать метод северо-западного угла, мы, конечно, получим распределение поставок, но число заполненных клеток, а следовательно, и число базисных переменных будет меньше, чем m + n -1 = 3=3 -1 = 5. Такое распределение не будет базисным и не может считаться первоначальным опорным планом.

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

Разобьем шаг 2 на два шага. Предположим, что после поставки в клетку (1.2) 10 единиц груза из дальнейшего рассмотрения выпадет только первая строка. Для того, чтобы все же вывести из рассмотрения второй столбец, делаем еще один шаг: даем нулевую (фиктивную) поставку в произвольную, но не вычеркнутую клетку второго столбца, например в клетку (2.2).

В результате получим таблицу 13.5.

Таблица 13.5 – Таблица распределения поставок после третьего шага

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

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

Таблица 13.6 – Окончательная таблица распределения поставок в задаче 13.2

Анализируя таблицу 13.6, можно отметить, что ней имеется ровно m + n – 1= = 3 + 3 – 1 = 5 заполненных клеток, хотя одна из них с нулевой (фиктивной) поставкой. Тогда в соответствии с теоремой 13.2 такое распределение поставок является базисным, и полученный первоначальный план распределения является опорным планом.

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