Закрытая транспортная задача

Автор: Пользователь скрыл имя, 17 Января 2013 в 21:49, курсовая работа

Описание работы

Среди задач математического программирования самыми простыми (и лучше всего изученными) являются так называемые задачи линейного программирования. Характерно для них то, что целевая функция линейно зависит от элементов решения и ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно элементов решения.
Целью курсового проекта является углубленное изучение раздела «Линейное программирование», а, конкретно, задача об оптимальном плане перевозки грузов (Транспортная задача), анализ литературы по заданной теме, выполнение практической части проекта в виде подробного решения задач.

Содержание

Введение 4
1 Линейное программирование 5
1.1 Основные понятия линейного программирования 5
1.2 Общая задача линейного программирования 6
1.3 Задача об оптимальном плане перевозок грузов (транспортная задача) как специальная задача линейного программирования 7
1.4 Этапы решения транспортной задачи 8
1.4.1 Нахождение начального плана 8
1.4.2 Улучшение начального плана и нахождение оптимального решения 9
2 Задача об оптимальном плане перевозок (Транспортная задача) 10
2.1 Решение задачи 1 10
2.2 Решение задачи 2 21
2.3 Решение задачи 3 29
Заключение 35
Список используемых источников 36

Скачать полностью (6.96 Мб) Сколько стоит заказать работу?
Работа содержит 1 файл

Курсовой проект.docx

— 7.38 Мб (Скачать)

 

Решение задачи 1 при помощи пакета Mathcad 2000 представлено на рисунках 7 и 8:

Рисунок 7 – Ввод условия для решения задачи при помощи пакета Mathcad 2000

 

 

 

 

 

 

Рисунок 8 – Найденное решение задачи

 

2.2. Решение задачи 2

Составьте оптимальный план перевозки автомобилей, если известно, что стоимость перевозки одного автомобиля составляет 10 руб. за км. Расстояние между городами и объёмы заявок приведены в таблице 6. Составьте оптимальный план перевозок, обеспечивающий минимальные затраты на перевозку.

Таблица 6 – Тарифы на доставку товара, объемы запасов и заказы на продукцию для задачи 2

Склады

Супермаркеты

Запасы, шт.

Москва

Саранск

Ульяновск

Coca-Cola

10500

6000

4500

20

Sprite

7500

3900

2100

65

Fanta

9000

3600

1500

80

Заказы, уп.

100

50

15

  

 

Целевая функция:

 

Ограничения:

x11 + x12 + x13 =20;


x21 + x22 + x23 =65

x31 + x32 + x33 =80;

x11 + x21 + x31=100;

x12 + x22 + x32=50;

x13 + x23 + x33 = 15; 

 

 

 

Запишем начальный план перевозок. Для удобства, обозначим за B1, B2, B3, B4 магазины, а за A1, A2, A3 склады.

Таблица 7 – Начальный план перевозок продукции для решения задачи 2

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500    -

6000  5

4500    15

A2

65

7500  20

3900   45

2100      -

A3

80

9000    80

3600     -

1500      -


U1=0;


V2=6000;

V3=4500;

U2= -2100;

V1=9600;

U3=-600;

V3=4

 

U1 + V2 = 6000;


U1 + V3 = 4500;

U2 + V1 = 7500;

U2 + V2 = 3900;

U3 + V1 = 9000;

 


 

 

                                    =>

 

 

 

С111 = U1 + V1 = 0 + 9600 = 9600;

C123 = U2 + V3 = -2100 + 4500 = 2400;

C132 = U3 + V2 = -600 + 6000 = 5400;

C133 = U3 + V3 = -600 + 4500 = 3900;

Проверим план на оптимальность:

;

;

;

;

 

Таблица 8 – Построение цикла для получения новой транспортной таблицы

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500    -

6000  5 +

4500    15 -

A2

65

7500  20 +

3900   45 -

2100      -

A3

80

9000    80  -

3600     -

1500      +


 

Таблица 9 – Вторая транспортная таблица для решения задачи  2

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500    -

6000  20

4500    -

A2

65

7500  35

3900   30

2100      -

A3

80

9000    65 

3600     -

1500 15


 

Определим потенциалы производителей и потребителей:

U1 = 0;


V2 = 6000;

U2 = -2100;

V1 = 9600;

U3 = -600;

V3 = 2100;

U1 + V2 = 6000;


U2 + V1 = 7500;

U2 + V2 = 3900;

U3 + V1 = 9000;

U3 + V3 = 1500;


 

                            =>

                                              

 

 

Определим суммы потенциалов:

С211 = U1 + V1 = 9600;

C213 = U1 + V3 = -2100;

C223 = U2 + V3 = 0;

C232 = U3 + V2 = 5400;

 

 

 

 

 

Проверим план на оптимальность:

;

;

;

;

Таблица 10 – Построение цикла  для получения новой транспортной таблицы

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500    -

6000  20

4500    -

A2

65

7500  35 +

3900   30 -

2100      -

A3

80

9000    65  -

3600     +

1500 15 


Таблица 11 – Третья транспортная таблица для решения задачи  2

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500    -

6000  20

4500    -

A2

65

7500  65

3900   -

2100      -

A3

80

9000    35 

3600    30

1500 15 


Аналогично предыдущему  плану перевозок, определим потенциалы производителей и потребителей:

U1 = 0;


V2 = 6000;

U3 = -2400;

V1 = 11400;

U2 = -3900;

V3 = 3900;

U1 + V2 = 6000;


U2 + V1 = 7500;

U3 + V1 = 9000;

U3 + V2 = 3600;

U3 + V3 = 1500;


 

 

 

 

 

 

 

 

 

 

 

С311 = U1 + V1 = 11400;

C313 = U1 + V3 = 3900;

C322 = U2 + V2 = 2100;

C323 = U2 + V3 = 0;

Проверим план на оптимальность:

;

;

;

;

Таблица 12 – Построение цикла для получения новой транспортной таблицы

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500   +

6000  20 -

4500    -

A2

65

7500  65

3900   -

2100     -

A3

80

9000    35  -

3600   30 +

1500 15 


 

Таблица 13 – Четвертая транспортная таблица для решения задачи  2

Потребитель

Поставщик

Склады

B1

B2

B3

100

50

15

A1

20

10500   20

6000  -

4500    -

A2

65

7500  65

3900   -

2100     -

A3

80

9000    15 

3600   50

1500 15 


Определим потенциалы производителей и потребителей:

U1 = 0;


V1 = 10500;

U2 = -3000;

U3 = -1500;

V2 = 5100;

V3 = 3000;

U1 + V1 = 10500;


U2 + V1 = 7500;

U3 + V1 = 9000;

U3 + V2 = 3600;

U3 + V3 = 1500;


 

 

 

 

 

 

С412 = U1 + V2 = 5100;

C413 = U1 + V3 = 3000;

C422 = U2 + V2 = 2100;

C423 = U2 + V3 = 0;

Проверим план на оптимальность:

;

;

;

;

Данный план является оптимальным.

Вычислим целевую функцию:

 

Ответ: Таким образом, оптимально перевозить грузы так:

Из А1 в B1 – 20 автомобилей;

Из А2 в B1 – 65 автомобилей;

Из А3 в B1 – 15 автомобилей;

Из А3 в B2– 50 автомобилей;

Из А3 в B3 – 15 автомобилей;

При этом, стоимость перевозки минимальна и составляет 10350000 рублей.

 

 

Решение задачи 2 при помощи пакета Mathcad

Рисунок 9 – Ввод условия для решения задачи при помощи пакета Mathcad 2000

 

 

 

 

Рисунок 10 – Найденное решение задачи

 

2.3 Решение задачи 3

Составьте оптимальный план перевозки лекарств с минимальными затратами из аптечных складов в  пять аптек города. Запасы лекарств на складах, заявки потребителей и тарифы перевозок указаны в таблице.

Таблица 14 – Тарифы на доставку товара, объемы запасов и заказы на продукцию для задачи 3

Склады

Аптеки больниц

Запасы, шт.

№ 15

№ 17

№23

№ 50

Госпиталь им. Н.Н. Бурденко

АС №1

10

11

6

7

8

100

Фарма К.

10

11

8

9

12

150

ПРОТЕК

12

12

10

12

14

200

Заказы

50

200

60

100

40

  

Целевая функция:

+  

Ограничения:

x11 + x12 + x13 + x14 + x15 =100;


x21 + x22 + x23 + x24 + x15 =150

x31 + x32 + x33 + x34 + x35 =200;

x11 + x21 + x31=500;

x12 + x22 + x32=200;

x13 + x23 + x33 = 60;

x14 + x24 + x34 = 100;

x15 + x25 + x35 = 40;

 

 

Запишем начальный план перевозок. Для удобства, обозначим за B1, B2, B3, B4 магазины, а за A1, A2, A3 склады.

Таблица 15 – Начальный план перевозок продукции для решения задачи 3

Потребитель

Поставщик

Склады

B1

B2

B3

B4

B5

50

200

60

100

40

A1

100

10      -

11     -

6    60

7    40

8      -

A2

150

10  50

11   40

8      -

9    60

12     -

A3

200

12     -

12   160

10    -

12     -

14    40

Информация о работе Закрытая транспортная задача