Прикладная математика

4. Транспортная задача

Составить математическую модель транспортной задачи по исходным данным из приложения 2, где вектор объемов производства А (a1,…, am), вектор потребления В (b1,…, bn) и матрица транспортных издержек кратко записаны в виде:

Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.

Приложение 2

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

№ 2.18.

34 40 38 53

80 2 7 2 3

60 1 5 4 2

30 3 4 6 1

Решение:

Определим оптимальный плана перевозок некоторого однородного груза из 3-х пунктов отправления А1, А2, А3 в 4 пункта назначения B1, B2, B3., B4. В качестве критерия оптимальности возьмем минимальную стоимость перевозок всего груза. Пусть с тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai — запасы груза в пункте Аi через bj — потребности в грузе пункта Bj, xij — количество единиц груза, перевозимого из i-го пункта в j-й пункт. Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке xij единиц груза.

Поставщики Потребители Запасы

B1 B2 B3 B4

А1 2

X11 7

X12 2

X13 3

X14 80

А2 1

X21 5

X22 4

X23 2

X24 60

А3 3

X31 4

X32 6

X33 1

X34 30

Потребности 34 40 38 53 165 170

Соответственно математическая постановка задачи состоит в определении минимума целевой функции:

при условиях:

.

Транспортная задача является открытой, так как запас груза больше потребностей на 5 единиц. Приведем задачу к закрытому типу — введем фиктивного потребителя B5.

Поставщик Потребитель Запасы

груза

B1 B2 B3 B4 B5

A1 2

A2 1

A3 3

Потребность 34 40 38 53 5

Находим опорный план по правилу минимального элемента. Введем некоторые обозначения: Ai* - излишек нераспределенного груза от поставщика Ai; Bj* - недостача в поставке груза потребителю Bj.

Временно исключаем из рассмотрения клетки фиктивного потребителя. Находим незанятую клетку с минимальным тарифом: (2,1). Помещаем туда меньшее из чисел A2*=60 и B1*=34. Находим незанятую клетку с минимальным тарифом: (3,4). Помещаем туда меньшее из чисел A3*=30 и B4*=53. Находим незанятую клетку с минимальным тарифом: (1,3). Помещаем туда меньшее из чисел A1*=80 и B3*=38. Находим незанятую клетку с минимальным тарифом: (2,4). Помещаем туда меньшее из чисел A2*=26 и B4*=23. Находим незанятую клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2*=3 и B2*=40. Находим незанятую клетку с минимальным тарифом: (1,2). Помещаем туда меньшее из чисел A1*=42 и B2*=37. Теперь распределим оставшися груз между поставщиками и фиктивным потребителем B5. Поместим в клетку (1,5) 5 единиц груза.

5. Задача распределения капитальных вложений

Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб., по исходным данным, приведенным в приложении 3 (выделяемые суммы кратны 100 тыс.).

Приложение 3. Нелинейная задача распределения ресурсов. Динамическое программирование

№ 3.18.

0 100 200 300 400 500 600 700

0 20 33 42 48 53 56 58

0 22 37 49 59 68 76 82

0 10 29 42 52 60 65 69

0 16 27 37 44 48 50 56

Решение:

Таблица 1

0 100 200 300 400 500 600 700

0 20 33 42 48 53 56 58

0 22 37 49 59 68 76 82

0 10 29 42 52 60 65 69

0 16 27 37 44 48 50 56

Сначала заполняем таблицу 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение .

Таблица 2

0 100 200 300 400 500 600 700

0 20 33 42 48 53 56 58

0 0 0* 20 33 42 48 53 56 58

100 22 22* 42* 55 64 70 75 78

200 37 37 57* 70* 79 85 90

300 49 49 69 82* 91 97

400 59 59 79 92* 101*

500 68 68 88 101*

600 76 76 96

700 82 82

Заполняем далее таблицу 3:

Таблица 3

0 100 200 300 400 500 600 700

0 22 42 57 70 82 92 101

0 100 100 200 200 300 400 400 или 500

Продолжая процесс, табулируем функции F3(), () и т. д. В табл. 6 заполняем только одну диагональ для значения = 700. Наибольшее число на этой диагонали:

Таблица 4