ЛАБОРАТОРНАЯ РАБОТА 4 ТРАНСПОРТНАЯ ЗАДАЧА

Цельработы

Ознакомиться со структурой транспортных задач, методами их решения и анализа результатов; приобрести навыки в проведении вычислительного эксперимента на ЭВМ.

Краткиетеоретическиесведения

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

Пусть в пунктах А1, А2, …, Аm изготавливается некоторый однородный продукт, причем объем производства этого продукта в пункте Ai составляет ai ед., i = 1, …, m. Произведенный продукт должен быть доставлен в пункты потребления В1, В2, …, Вn, причем объем потребления в пункте Bj составляет bj ед. продукта. Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта Аi в пункт Вj, составляют cij ден. ед. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.

Обозначим через xij количество продукта, перевозимого c i-го предприятия к j-му потребителю. План перевозки груза в данной транспортной сети представляет собой массив элементов размерности m × n:

x = (x1,1, …, x1,n, x2,1, …, x2,n, …, xm,1, …, xm,n).

Если реальная перевозка между пунктами i и j отсутствует, то полагают xi,j = 0.

Ограничения на возможные значения x Rmn включают в себя: ограничения на удовлетворение потребностей во всех пунктах по-

требления:

m
∑xi, j ≥ bj , j =1, ..., n;	(4.1)

i=1

Моделирование процессов и объектов в металлургии. Лаб. практикум

-54-

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

Краткие теоретические сведения

ограничения на возможности вывоза запасов из всех пунктов производства:

n
∑xi, j ≤ ai , i =1, …, m;	(4.2)
j=1
условия неотрицательности компонент плана:
xi,j ≥ 0, i = 1, …, m, j = 1, …, n.	(4.3)

Математически транспортная задача ставится следующим образом: определить точку минимума функции суммарных транспортных издержек

m n

f (x)= ∑∑cij xi, j

i=1 j=1

при ограничениях (4.1), (4.2), (4.3).

Полученная задача является задачей линейного программирования. Существенная характеристика описываемой задачи – соотношение параметров ai и bj. Если суммарный объем производства равен суммарному объему потребления, а именно выполняется условие баланса

m	n
∑ai = ∑b j ,		(4.4)
i=1	j=1

то система называется сбалансированной. При выполнении условия баланса разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т.е. условия (4.1), (4.2) приобретают форму равенства. При таких ограничениях выполнение равенства (4.4) становится необходимым и достаточным условием для разрешимости транспортной задачи.

Порядоквыполненияработы

1.Изучить постановку и методы решения транспортных задач.

2.Изучить порядок эксплуатации программных средств решения задачи ЛП с помощью ЭВМ.

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

Моделирование процессов и объектов в металлургии. Лаб. практикум

-55-

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

Порядок выполнения работы

4.Ввести данные в ЭВМ в соответствии с вариантом задания и получить решение задачи.

5.Оформить отчет, в который включить: титульный лист, краткую формулировку цели и содержания работы, математическую модель транспортной задачи, краткое описание методов решения, задание, результаты расчета на ЭВМ, анализ результатов.

Задание

Вариант 1

	15	20	20	30
50	13	17	17	14
25	18	16	16	18
25	12	14	19	17

Вариант 2

160	120	50	190	110
	7	8	1	2
140	4	5	9	8
170	9	2	3	6

Вариант 3

6 000	1 500	2 500	2 700	3 300
	1	4	1	9
3 000	9	2	2	8
3 000	6	1	7	3

Вариант 4

	250	1 000	700	650	450
950	12	14	21	19	32
300	4	4	9	5	24
1 350	3	8	14	10	26
450	24	33	36	34	49

Вариант 5

9	6	4	10	13	7	10
	2	9	3	10	8	7
14	3	2	6	3	5	2
16	1	8	2	4	1	5
11	4	8	7	6	6	6

Моделирование процессов и объектов в металлургии. Лаб. практикум

-56-

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

Задание

Вариант 6

145	120	125	130	110	140
	18	24	23	27	32
125	19	20	14	16	26
220	21	20	17	15	28
135	15	21	22	19	22

Вариант 7

180	120	60	60	80
	2	3	4	3
60	5	3	1	2
80	2	1	4	2

Вариант 8

12	50	30	20
	15	19	14
15	19	18	16
26	19	18	20
36	15	19	18

Вариант 9

	4	9	9	13
8	4	3	3	1
11	3	2	4	8
16	5	4	6	3

Вариант 10

	30	30	10	20
50	1	2	4	1
30	2	3	1	5

Вариант 11

180	110	90	120	80	150
	7	12	4	6	5
350	1	8	6	5	3
20	6	16	8	7	4

Вариант 12

20	10	15	20	10	15
	24	16	8	10	14
30	21	15	7	12	16
20	23	14	7	14	12

Моделирование процессов и объектов в металлургии. Лаб. практикум

-57-

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

Задание

Вариант 13

950	250	1 000	700	650	450
	12	14	21	19	32
300	4	4	9	5	24
350	3	8	14	10	26
450	24	33	36	34	49

Вариант 14

6 000	1 500	2 500	2 700	3 300
	1	4	1	9
3 000	9	2	2	8
3 000	6	1	7	3

Вариант 15

145	120	125	130	110	140
	18	24	23	27	32
125	19	20	14	16	26
220	21	20	17	15	28
135	15	21	22	19	22

Контрольныевопросыизадания

1.Дайте содержательную формулировку транспортной задачи.

2.Какие ограничения задают допустимое множетво транспортной за-

дачи?

3.Каков экономический смысл решения транспортной задачи?

4.Можно ли решать транспортную задачу методами линейного программирования?

5.Сформулируйте условие баланса. Какова его роль в транспортных

задачах?

6.Когда транспортна задача называется сбалансированной?

Моделирование процессов и объектов в металлургии. Лаб. практикум

-58-