Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Транспортная задача
|
|
Это еще одна типичная и очень важная задача линейного программирования.
| Постановка задачи. В n пунктах отправления (склады, заводы и т.п.) A 1, A 2,.., An имеется (или производится) некоторый однородный продукт в количествах a 1, a 2,.., an. Необходимо доставить этот продукт в m пунктов назначения B 1, B 2,.., Bm в количествах b 1, b 2,.., bm. Стоимость перевозки единицы груза из пункта Ai в пункт Bj равна cij. Заметим, что стоимость – это условное понятие, которое может означать расстояние, тариф, расход топлива, время и т.д. Количество перевозимого груза из пункта Ai в пункт Bj обозначим через xij (i =1, 2,.., n; j =1, 2,.., m). Задача заключается в определении таких величин xij, при которых стоимость перевозок будет минимальной. |
Условия задачи можно записать компактно в виде таблицы (двойной матрицы):
Таблица
| B j A i | b 1 | b 2 | … | bm |
| a 1 | c 11 x 11 | c 12 x 12 | ….. | c 1 m x 1 m |
| a 2 | c 21 x 21 | c 22 x 22 | ….. | c 2 m x 2 m |
| … | … | … | … | …. |
| an | cn 1 xn 1 | cn 2 xn 2 | … | cnm xnm |
Cовокупность 
чисел xij, т.е. матрицу Х = [ xij ] будем называть матрицей перевозок или планом перевозки, а матрицу С =[ cij ] – матрицей транспортных издержек (затрат).
Сформулируем математическую модель транспорт-ной задачи.
Транспортная задача заключается в отыскании среди допустимых планов оптимального, т.е. такого, по которому общая стоимость перевозок будет минимальна, т.е
План является допустимым, если числа x ij удовлетворяют следующим естественным ограничениям:
Поскольку грузы предполагается перевозить только в одном направлении – из пунктов отправления в пункты назначения, то на переменные накладываются условия неотрицательности переменных:
в которых первые m равенств означают, что из каждого пункта производства Ai вывозится весь произведенный продукт. Последние n равенства означают, что каждый пункт потребления полностью удовлетворяется.
Транспортную задачу в приведенной формулировке (6.26) – 6.28) называют закрытой (или замкнутой) транспортной задачей, в отличие от открытой, в которой
n Пример 6.8. Построить математическую модель транспортной задачи.
На трех цементных заводах производится цемент одной и той же марки в количествах соответственно 100, 130, 170 тонн. Цемент следует доставить на четыре ЖБК, потребляющих его соответственно в количествах 150, 120, 80, 50 тонн. Стоимости (у.е.) перевозок одной тонны продукта с i -го (i =1, 2, 3) завода на j -й (j =1, 2, 3, 4) ЖБК приведены в табл.
Спланировать перевозки так, чтобы их стоимость была минимальной.
Проектные параметры: xij –количество (т) продукта, перевозимого с i- го (i =1, 2, 3) завода на j -й (j =1, 2, 3, 4) ЖБК.
Условия задачи записываем в виде таблицы.
| Цемент-ные заводы | Стоимость перевозки (у.е.) Количество. перевозимого продукта (т) | Объем производ-ства (т) | |||
| ЖБК-1 | ЖБК-2 | ЖБК-3 | ЖБК-4 | ||
| №1 | 3 x11 | 5 x12 | 7 x13 | 11 x14 | |
| №2 | 1 x21 | 4 x22 | 6 x23 | 3 x24 | |
| №3 | 5 x31 | 8 x32 | 12 x33 | 7 x34 | |
| Объем потребления |
Тогда целевая функция (общая стоимость перевозок) имеет вид:
Z min =3 x 11+5 x 12+7 х 13+11 х 14+ x 21+4 x 22+6 x 23+3 x 24+5 x 31+8 x 32+12 x 33+7 x 34.
Ограничения записываем из условия, что вывозится весь произведенный на каждом заводе цемент (первые три) и что каждый ЖБК полностью обеспечивается цементом:
x 11 + x 12 + х 13+ х 14=150,
x 21 + x 22 + x 23+ x 24=130,
x 31 + x 32.+ x 33+ x 34=170,
x 11 + x 21 + х 31=150,
x 12 + x 22 + x 32=120,
x 13 + x 23.+ x 33=80,
x 14 + x 24.+ x 34=50,
xij ³ 0 (i =1, 2, 3; j =1, 2, 3, 4).
Решение данной транспортной задачи с использованием приложения Microsoft Excel приведено в подразделе 6.5.