Экономико-математическое моделирование

Применение методов линейного программирования для оптимизации стоимости перевозок (стр. 2 из 5)

или короче

где символ

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

с помощью горизонтальных уравнений, мы получаем уравнение

Так как для закрытой модели транспортной задачи

, то полученные нами уравнения (3. ) и (3. ) одинаковы и, исключив из одного из них неизвестное

, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

Итак, преобразование системы (3. ) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (3. ). Остальные уравнения остаются неизменными. Система приняла вид

В системе (3. ) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного

[она входит в первое уравнение системы (3. )]. В системе (3. ) имеется

уравнений, выделенный базис содержит

неизвестных, а, следовательно, и ранг системы (3. )

.

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

, т. е. стоимость перевозки единицы груза с базы

потребителю

.

Совокупность тарифов

также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу 3.:

Таблица 3. - Совокупность тарифов данные о запасах и потребностях

ПунктыОтправления	Пункты назначения									Запасы
						…
			…

					…

…	…			…		…		…			…
				…

Потребности						…				или

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

:

Требуется в области допустимых решений системы уравнений (3. ) и (3.) найти решение, минимизирующее линейную функцию (3. ).

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен

то среди всех

неизвестных

выделяется

базисных неизвестных, а остальные

·

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

заполненных и

·

пустых клеток.

На предприятии ОАО «Электросигнал» имеется 4 транзитных склада А_i, на которых хранятся сборочные узлы и 5 цехов B_j, занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из А_i в B_j. Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.

Таблица 3. – Исходные данные по количеству сборочных узлов и стоимость перевозки

ЦехаСклад	B₁(b₁=40)	B₂(b₂=50)	B₃(b₃=15)	B₄(b₄=75)	B₅(b₅=40)
А₁(а₁=50)	1,0	2,0	3,0	2,5	3,5
А₂(а₂=20)	0,4	3,0	1,0	2,0	3,0
А₃(а₃=75)	0,7	1,0	1,0	0,8	1,5
А₄(а₄=80)	1,2	2,0	2,0	1,5	2,5

В данном случае Σa_i=225 >Σb_j=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B₆ с потребностью b₅=225-220=5 и стоимостью перевозок с_i₆=0.Имеем таблицу 3. :

читать дальше

2