Контрольная работа: Применение методов линейного программирования для оптимизации стоимости перевозок

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

(3. )

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

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

(3. )

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

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

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

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

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

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

(3. )

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

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

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

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

Цеха Склад	B1 (b1 =40)	B2 (b2 =50)	B3 (b3 =15)	B4 (b4 =75)	B5 (b5 =40)
А1 (а1 =50)	1,0	2,0	3,0	2,5	3,5
А2 (а2 =20)	0,4	3,0	1,0	2,0	3,0
А3 (а3 =75)	0,7	1,0	1,0	0,8	1,5
А4 (а4 =80)	1,2	2,0	2,0	1,5	2,5