При заданных объёмах груза в пунктах отправления и потребности в пунктах назначения определить оптимальный план перемещения груза от отправителя к потребителю.
Исходные данные:
Запас груза в i-м пункте отправления ai: a1 = 30, a2 = 15, a3 = 25.
Потребность j-го пункта назначения в грузе bj: b1 = 20, b2 = 5, b3 = 45.
Матрица тарифов (стоимость перевозки единицы груза) Cij:
Рисунок 6.16 – Пояснение №1 к симплекс-методу
Составим математическую модель задачи транспортного типа.
Целевая функция:
F = 10x1,1 + 20x1,2 + 30x1,3 + 30x2,1 +10x2,2 + 20x2,3 + 5x3,1 +15x3,2 +10x3,3 → min.
Граничные условия:
Транспортная задача разрешима только в случае, если соблюдается условие баланса Σai = Σbi. В нашем случае оно выполняется, так как:
Σai = 30 + 15 + 25 = 70,
Σbi = 20 + 5 + 45 = 70.
Следовательно, задача является закрытой (сбалансированной).
Приведём систему ограничений к каноническому виду, для этого введём в каждое условие искусственную переменную R. Тогда система запишется ввиде:
Переходим к формированию исходной симплекс-таблицы. В строку F таблицы заносятся коэффициенты целевой функции.
Так как среди исходного набора условий были равенства, мы ввели искусственные переменные R. Это значит, что в симплекс-таблицу нам необходимо добавить дополнительную строку M, элементы которой рассчитываются как сумма соответствующих элементов условий-равенств (тех, которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.
Из данных задачи составляем исходную симплекс-таблицу 6.4.
Таблица 6.4 – Исходная симплекс-таблица
| x1,1 | x1,2 | x1,3 | x2,1 | x2,2 | x2,3 | x3,1 | x3,2 | x3,3 | Свободный член | |
| F | ||||||||||
| R1 | ||||||||||
| R2 | ||||||||||
| R3 | ||||||||||
| R4 | ||||||||||
| R5 | ||||||||||
| R6 | ||||||||||
| M | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -140 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x1,1). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R4, а ведущий элемент: 1.
Таблица 6.5
| x1,2 | x1,3 | x2,1 | x2,2 | x2,3 | x3,1 | x3,2 | x3,3 | Свободный член | |
| F | -5 | -200 | |||||||
| R1 | -1 | -1 | |||||||
| R2 | |||||||||
| R3 | |||||||||
| x1,1 | |||||||||
| R5 | |||||||||
| R6 | |||||||||
| M | -2 | -2 | -2 | -2 | -2 | -2 | -100 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2(столбец x1,2). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R5, а ведущий элемент: 1.
Таблица 6.6
| x1,3 | x2,1 | x2,2 | x2,3 | x3,1 | x3,2 | x3,3 | Свободный член | |
| F | -10 | -5 | -5 | -300 | ||||
| R1 | -1 | -1 | -1 | -1 | ||||
| R2 | ||||||||
| R3 | ||||||||
| x1,1 | ||||||||
| x1,2 | ||||||||
| R6 | ||||||||
| M | -2 | -2 | -2 | -90 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x1,3). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 1.
Таблица 6.7
| x2,1 | x2,2 | x2,3 | x3,1 | x3,2 | x3,3 | Свободный член | |
| F | -450 | ||||||
| x1,3 | -1 | -1 | -1 | -1 | |||
| R2 | |||||||
| R3 | |||||||
| x1,1 | |||||||
| x1,2 | |||||||
| R6 | |||||||
| M | -2 | -2 | -2 | -2 | -2 | -2 | -80 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x2,1). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R2, а ведущий элемент: 1.
Таблица 6.8
| x2,2 | x2,3 | x3,1 | x3,2 | x3,3 | Свободный член | |
| F | -30 | -30 | -1200 | |||
| x1,3 | -1 | -1 | ||||
| x2,1 | ||||||
| R3 | ||||||
| x1,1 | -1 | -1 | ||||
| x1,2 | ||||||
| R6 | ||||||
| M | -2 | -2 | -2 | -50 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2(столбец x3,1). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x1,1, а ведущий элемент: 1.
Таблица 6.9
| x2,2 | x2,3 | x1,1 | x3,2 | x3,3 | Свободный член | |
| F | -5 | -5 | -25 | -1325 | ||
| x1,3 | -1 | -1 | ||||
| x2,1 | ||||||
| R3 | -1 | |||||
| x3,1 | -1 | -1 | ||||
| x1,2 | ||||||
| R6 | ||||||
| M | -2 | -2 | -2 | -2 | -2 | -40 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2(столбец x2,2). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x1,2, а ведущий элемент: 1.
Таблица 6.10
| x1,2 | x2,3 | x1,1 | x3,2 | x3,3 | Свободный член | |
| F | -5 | -25 | -1300 | |||
| x1,3 | ||||||
| x2,1 | -1 | -1 | ||||
| R3 | -1 | -1 | ||||
| x3,1 | -1 | |||||
| x2,2 | ||||||
| R6 | -1 | -1 | ||||
| M | -2 | -2 | -30 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x2,3). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x2,1, а ведущий элемент: 1.
Таблица 6.11
| x1,2 | x2,1 | x1,1 | x3,2 | x3,3 | Свободный член | |
| F | -25 | -1250 | ||||
| x1,3 | ||||||
| x2,3 | -1 | -1 | ||||
| R3 | -1 | -1 | ||||
| x3,1 | ||||||
| x2,2 | ||||||
| R6 | -1 | -1 | ||||
| M | -2 | -2 | -10 |
В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x3,2). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R3, а ведущий элемент: 1.
Таблица 6.12
| x1,2 | x2,1 | x1,1 | x3,3 | Свободный член | |
| F | -15 | -1375 | |||
| x1,3 | -1 | ||||
| x2,3 | -1 | ||||
| x3,2 | -1 | -1 | |||
| x3,1 | |||||
| x2,2 | -1 | ||||
| R6 | |||||
| M |
В строке F имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке F максимальный по модулю отрицательный элемент – это -15. Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкойявляется x3,2, а ведущий элемент: 1.
Таблица 6.13
| x1,2 | x2,1 | x1,1 | x3,3 | Свободный член | |
| F | -15 | -1300 | |||
| x1,3 | |||||
| x2,3 | -1 | -1 | |||
| x3,3 | -1 | -1 | |||
| x3,1 | |||||
| x2,2 | |||||
| R6 | |||||
| M |
В строке F имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке F максимальный по модулю отрицательный элемент – это x1,1. Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x3,1, а ведущий элемент: 1.
Таблица 6.14
| x1,2 | x2,1 | x1,1 | x3,3 | Свободный член | |
| F | -1000 | ||||
| x1,3 | -1 | -1 | |||
| x2,3 | -1 | -1 | |||
| x3,3 | |||||
| x1,1 | |||||
| x2,2 | |||||
| R6 | |||||
| M |
Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение (минимальные транспортные расходы):
F =10 · 30 + 10 · 20 + 25 · 10 + 20 · 10 + 5 · 10 = 1000,
при значениях переменных равных:
x1,3 = 10 (количество продукции, доставленное от поставщика №1 к потребителю№3);
x2,3 = 10 (количество продукции, доставленное от поставщика №2 к потребителю№3);
x3,3 = 25 (количество продукции, доставленное от поставщика №3 к потребителю№3);
x1,1 = 20 (количество продукции, доставленное от поставщика №1 к потребителю№1);
x2,2 = 5 (количество продукции, доставленное от поставщика №2 к потребителю№2).
Результат решения задачи можно представить в виде графа.
Рисунок 6.17 – Пояснение №2 к симплекс-методу