Выполнение задания 1. Рассмотрим реализациюрешения транспортной задачи на примере

Рассмотрим реализациюрешения транспортной задачи на примере.

Пример

Рассмотрим транспортную задачу, в которой в трех пунктах производства:

A 1, A 2, A 3

изготавливается однородная продукция в количествах:

a 1=30, a 2=40, a 3=20

соответственно. Эту продукцию требуется доставить в четыре пункта потребления:

B 1, B 2, B 3, B 4

в количествах

b 1=20, b 2=30, b 3=30, b 4=10

соответственно. Матрица C задает стоимости перевозок единицы продукции cij из пункта производства Ai в пункт потребления Bj:

.

Требуется определить план перевозок, который минимизирует транспорт-ные расходы.

Запишем математическую модель данной транспортной задачи.

Обозначим xij – количество продукции, направляемое из пункта произ-водства Ai в пункт потребления Bj (табл. 2.1). Составим матрицу перевозок из величин xij

Таблица 2.1

Сумма элементов первой строки: x 11 + x 12 + x 13 + x 14 определяет количество продукции, вывозимое из пункта производства A 1. По условию задачи эта величина не может превосходить максимального количества продукции a 1 = 30, производимого в этом пункте, т.е. должно выполняться неравенство:

x 11 + x 12 + x 13 + x 14 ≤ 30.

Аналогично сумма элементов второй строки x 21 + x 22 + x 23 + x 24 определяет количество продукции, вывозимое из пункта производства A 2. По условию задачи эта величина не может превосходить максимального количества продукции a 2=40, производимого в этом пункте, т.е. должно выполняться неравенство:

x 21 + x 22 + x 23 + x 24 ≤ 40.

Сумма элементов третьей строки x 31 + x 32 + x 33 + x 34 определяет количество продукции, вывозимое из пункта производства A 3. По условию задачи эта величина не может превосходить максимального количества продукции a 3 = 20, производимого в этом пункте, т.е. должно выполняться неравенство

x 31 + x 32 + x 33 + x 34 ≤ 20.

Сумма элементов первого столбца x 11 + x 21 + x 31 определяет количество продукции, ввозимое в пункт B 1. По условию задачи эта величина не меньше минимального количества продукции b 1 = 20, необходимого в этом пункте потребления, т.е. должно выполняться неравенство:

x 11 + x 21 + x 31 ≥ 20.

Аналогично для всех остальных пунктов потребления должны выполняться неравенства:

x 12 + x 22 + x 32 ≥ 30,

x 13 + x 23 + x 33 ≥ 30,

x 14 + x 24 + x 34 ≥ 10.

Математически транспортную задачу (2.2.1 – 2.2.3) можно сформулировать следующим образом:

– найти переменные x ij, которые минимизируют транспортные расходы

T = 2 x 11+3 x 12+3 x 13+4 x 14+3 x 21+2 x 22+5 x 23+ x 24+4 x 31+3 x 32+2 x 33+6 x 34

– при ограничениях

x 11+ x 12+ x 13+ x 14 ≤ 30,

x 21+ x 22+ x 23+ x 24 ≤ 40,

x 31+ x 32+ x 33+ x 34 ≤ 20,

x 11+ x 21+ x 31 ≥ 20,

x 12+ x 22+ x 32 ≥ 30,

x 13+ x 23+ x 33 ≥ 30,

x 14+ x 24+ x 34 ≥ 10,

xij ≥ 0.

Поиск по сайту: