logo search
Методичка_ММИО_2006

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

1. При некоторых реальных условиях перевозки груза из определенного пункта Ai в пункт назначения Bj не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт Bj является сколь угодно большой величиной М и при этом условии известными методами находят решение ТЗ. Такой подход к нахождению решения ТЗ называется запрещением перевозок.

2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Ai в Bj требуется обязательно перевезти αij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки Ai и столбца Bj, записывают указанное число αij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Иногда требуется найти решение ТЗ, при котором из Ai в Bj должно быть перевезено не менее заданного количества груза αij. Для определения оптимального плана такой задачи считают, что запасы Ai и потребности Bj меньше фактических на αij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.

Примечание: При целых ai (i = 1,..., m) и bj (j = 1,..., n), в силу специфики ограничений ТЗ, любое базисное допустимое решение является целочисленным.

Д омашнее задание №17

Решите транспортную задачу.

1.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 60, 30, 45, 25 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 20, 40, 25, 45, 30 и матрица

7 5 2 0 4

4 0 8 6 3

С =

5 6 0 9 8

6 4 5 7 6

характеризует эффективность использования специалиста на данной работе.

2. Выпуск продукции на трех заводах составляет 500 , 700 и 600 , причем затраты на производство единицы равны 9 , 8 и 2 соответственно. Потребности четырех потребителей на эту продукцию составляют 350 , 200, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю :

3 4 6 1

C = 5 1 2 3

4 5 8 1

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

3. Строительный песок добывается в трех карьерах с производительностью за день 46, 34 и 40 т. и затратами на добычу одной тонны 1 , 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки , потребность которых составляет 40, 35, 30, 45 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей :

4 3 2 5

C = 1 1 6 4

3 5 9 4

Недостающее количество песка - 30 т. в день можно обеспечить двумя путями : увеличением производительности а) 1 - го карьера , что повлечет дополнительные затраты в 3 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 2 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

4.Имеется три сорта бумаги в количествах 10 , 8 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 8000, 6000, 15000 и 10000 экз. Расход бумаги на одну книгу составляет 0,6; 0,8; 0,4 и 0,5 кг ,а себестоимость ( в коп. ) печатания книги при использовании i - го сорта бумаги задается матрицей:

24 16 32 25

C = 8 24 24 20

30 24 16 20

Определить оптимальное распределение бумажных ресурсов.

5. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 500, 700, 650 и 600 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300, 300 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

40 20 60 10 20

Cij = 10 80 30 40 30

70 30 30 50 10

50 10 40 50 40 ,

характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.

6.Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А 3 в В 5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 60 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

2

3

1

4

180

А2

6

3

4

5

2

220

А3

8

2

1

9

3

100

Потребности

120

80

160

90

50

500

7. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А2 в В4 и из А 3 в В 1 перевозки не могут быть осуществлены, а из А 4 в В 2 будет завезено 40 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

2

3

1

4

160

А2

6

3

4

5

2

220

А3

8

2

1

9

3

100

Потребности

120

80

140

90

50

8. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А 3 в В 2 и из А 4 в В 5 перевозки не могут быть осуществлены, а из А1 в В 3 будет завезено 35 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

2

3

1

4

160

А2

6

3

4

5

2

220

А3

8

2

1

9

3

100

Потребности

120

80

160

90

50

9. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А2 в В5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 45 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

2

3

1

4

180

А2

6

3

4

5

2

230

А3

8

2

1

9

3

100

Потребности

120

80

160

90

50

10.Найти решение транспортной задачи, исходные данные которой приведены в табл. , при дополнительных условиях : из А1 и В1 и из А2 и В5 перевозки не могут быть осуществлены, а из А2 и В1 будет завезено 60 единиц груза .

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

Пункты назначения

Запасы

В1 В2 В3 В4 В5

А1

1 2 3 1 4

180

А2

6 3 4 5 2

220

А3

8 2 1 9 3

100

Потребности

120 80 160 90 50

500

11.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 50, 40, 45, 35 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 30, 30, 45, 25, 30 и матрица

3 5 9 0 4

4 0 7 6 3

С =

6 6 0 5 8

6 4 5 9 6

характеризует эффективность использования специалиста на данной работе.

12. Выпуск продукции на трех заводах составляет 600 , 700 и 500 , причем затраты на производство единицы равны 8 , 6 и 3 соответственно. Потребности четырех потребителей на эту продукцию составляют 450 , 300, 150 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j -му потребителю :

2 5 6 4

C = 5 7 2 3

4 5 8 1

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

13. Строительный песок добывается в трех карьерах с производительностью за день 56, 44 и 50 т. и затратами на добычу одной тонны 1 , 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки , потребность которых составляет 60, 25, 20, 25 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей :

5 2 2 7

C = 1 2 6 4

3 5 8 4

Недостающее количество песка можно обеспечить двумя путями : увеличением производительности а) 1 - го карьера , что повлечет дополнительные затраты в 2 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 1 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

14.Имеется три сорта бумаги в количествах 10 , 9 и 6 т., которую необходимо использовать на издание четырех книг тиражом в 6000, 5000, 13000 и 11000 экз. Расход бумаги на одну книгу составляет 0,5; 0,8; 0,7 и 0,5 кг ,а себестоимость ( в коп. ) печатания книги при использовании i - го сорта бумаги задается матрицей:

14 26 32 25

C = 8 34 24 20

20 24 16 20

Определить оптимальное распределение бумажных ресурсов.

15. Четыре ремонтные мастерские могут за год отремонтировать соответственно 800, 600, 350 и 450 машин при себестоимости ремонта одной машины в 600, 700, 650 и 500 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 450, 100, 400 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

50 20 60 10 20

Cij = 10 70 30 40 10

70 30 30 50 10

50 10 20 50 40 ,

характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.

16.Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А 3 в В 5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 50 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

3

3

1

4

180

А2

7

3

5

5

2

210

А3

8

2

1

7

3

110

Потребности

100

90

170

90

50

500

17. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А2 в В4 и из А 3 в В 1 перевозки не могут быть осуществлены, а из А 4 в В 2 будет завезено 40 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

3

3

3

4

150

А2

7

3

5

5

2

220

А3

8

2

1

9

3

110

Потребности

120

90

130

90

50

18. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А 3 в В 2 и из А 4 в В 5 перевозки не могут быть осуществлены, а из А1 в В 3 будет завезено 45 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

4

3

2

5

150

А2

6

3

4

6

2

220

А3

7

2

1

9

1

110

Потребности

120

80

150

90

60

19. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А2 в В5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 40 единиц груза.

Пункты

Пункты назначения

Запасы

Отправления

В1

В2

В3

В4

В5

А1

1

4

3

1

4

170

А2

6

3

5

5

3

240

А3

7

2

1

9

3

100

Потребности

110

90

160

90

50

20.Найти решение транспортной задачи, исходные данные которой приведены в табл. , при дополнительных условиях : из А1 и В1 и из А2 и В5 перевозки не могут быть осуществлены, а из А2 и В1 будет завезено 50 единиц груза .

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

Пункты назначения

Запасы

В1 В2 В3 В4 В5

А1

2 3 3 1 4

180

А2

6 3 4 5 2

200

А3

8 2 1 9 4

120

Потребности

110 80 160 90 60

500

21.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 360, 40, 45, 35 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 20, 40, 35, 35, 30 и матрица

9 7 2 0 5

4 0 6 6 3

С =

3 6 0 7 8

6 4 5 7 6

характеризует эффективность использования специалиста на данной работе.

22. Выпуск продукции на трех заводах составляет 600 , 500 и 600 , причем затраты на производство единицы равны 11 , 7 и 4 соответственно. Потребности четырех потребителей на эту продукцию составляют 450 , 100, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю :

2 5 6 1

C = 7 1 2 3

4 4 8 1

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

23. Строительный песок добывается в трех карьерах с производительностью за день 47, 35 и 50 т. и затратами на добычу одной тонны 1 , 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки , потребность которых составляет 50, 25, 30, 45 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей :

7 4 2 5

C = 1 2 5 4

3 5 9 4

Недостающее количество песка можно обеспечить двумя путями: увеличением производительности а) 1 - го карьера , что повлечет дополнительные затраты в 3 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 2 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

24.Имеется три сорта бумаги в количествах 11 , 9 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 9000, 5000, 10000 и 12000 экз. Расход бумаги на одну книгу составляет 0,5; 0,8; 0,3 и 0,5 кг ,а себестоимость ( в коп. ) печатания книги при использовании i - го сорта бумаги задается матрицей:

20 16 30 25

C = 15 25 24 30

30 20 16 20

Определить оптимальное распределение бумажных ресурсов.

25. Четыре ремонтные мастерские могут за год отремонтировать соответственно 600, 500, 350 и 550 машин при себестоимости ремонта одной машины в 300, 600, 650 и 500 рублей. Планируется годовая потребность в ремонте пяти автобаз: 450, 350, 200, 300 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

30 10 50 10 20

Cij = 10 70 30 40 30

50 30 20 50 10

50 20 40 50 40 ,

характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.