Пример транспортной задачи

Построить экономико-математическую модель следующей задачи. имеются три поставщика и четыре потребителя. мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары “поставщик - потребитель” сведены в таблицу поставок (табл. 3).

Таблица 3

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

Задача ставится следующим образом: найти объемы перевозок для каждой пары «поставщик — потребитель» так, чтобы:

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

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

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

Решение. Построим экономико-математическую модель данной задачи, искомый объем перевозки от i-го поставщика к j-му потребителю обозначим черёз x_ij и назовём поставкой клетки (i,j). Например, х₁₂ - искомый объем перевозки от 1- го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д. заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х. так, например, объем груза, забираемого от 1 -го поставщика, должен быть равен мощности этого поставщика - 60 единицам, т.е. (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

,

, (19)

.

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

,

, (20)

,

.

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

Суммарные затраты р на перевозку выражаются через коэффициенты затрат и поставки следующим образом;

(21)

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

Решение. дадим переменной х₁₁ максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1,1) - “северо-западный” угол таблицы поставок: х₁₁= min {60, 20) = 20. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией (табл. 4) клетки, выпавшие из последующего рассмотрения, перечеркнуты пунктирной линией. в таблице поставок найдем новый “северо-западный” угол - клетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 20 единиц груза и у него осталось только 40 = 60 - 20 единиц груза, получаем, что . После этого мощность 1-го поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы поставок (перечеркиваем сплошной линией клетку (1,2) и пунктирной линией оставшиеся свободные клетки первой строки). в оставшейся таблице снова находим “северо-западный угол” и т. д. в результате получаем следующее исходное распределение поставок (табл.4).

Таблица 4.

Решение методом наименьших затрат.

Решение. Находим в таблице поставок (табл.4) клетки с наименьшим коэффициентом затрат. Таких клеток две – (1,1) и (2,1) с коэффициентами затрат, равными 1. сравним максимально возможные поставки для этих клеток: для клетки (1,1) , для клетки (2,1) .

Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам, в клетку (2,1). в результате спрос первого потребителя удовлетворен и первый столбец таблицы поставок выпадает из последующего рассмотрения (табл. 5.).

Таблица 5

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с₁₂ = с₂₄= 2. Сравним максимально возможные поставки для этих клеток: для клетки (1,2) ; для клетки (2,4) . Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: х₂₄ =100. При этом из рассмотрения выпадает вторая строка таблицы поставок (табл. 6).

Таблица 6

Аналогично, продолжая заполнение таблицы поставок шаг за шагом, получаем , , табл. 7.

Таблица 7