Решение оптимизационной задачи по грузоперевозкам

Министерство образования и науки России

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Санкт-Петербургский государственный политехнический университет»

 

ФАКУЛЬТЕТ ЭКОНОМИКИ И МЕНЕДЖМЕНТА

 

Кафедра «Финансы и денежное обращение»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

по дисциплине «Эконометрика»

на тему: «Решение оптимизационной задачи по грузоперевозкам»

 

 

Выполнил: студент группы №

                                                                                                                                      Сафонов Р.А.                                                                                            __________________________________

                                                                                       (подпись)                         (ФИО)

 

                                          Принял:

              _____          ___Батаев А.В.

                                                                                      (подпись)                         (ФИО)

__________________________________

                                                                                                    (дата)

 

 

 

 

 

 

 

 

 

 

Санкт – Петербург

2012

 

Содержание

 

Введение                                                                                                                       3

1. Техническое задание                                                                                                   4
2. Составление матричной модели транспортной задачи                                            6
3. Нахождение допустимых планов перевозок                                                             8
1. Метод северо-западного угла                                                                       9
2. Метод минимальной стоимости                                                                   9
4. Проверка наилучшего найденного плана на оптимальность решения                  11                                                              
5. Нахождение оптимального решения методом потенциалов                                  13
6. Использование программы QSB для решения транспортной задачи                   19

Выводы                                                                                                                         21

Список литературы                                                                                                     22

 

 

 

 

Введение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Техническое задание

 

 

Поставщики в количестве четырех штук поставляют определенную продукцию четырем конкретным потребителям, то есть m=n=4.

Пусть Am – поставщики продукта,

Вn – потребители поставленной продукции,

am – запас продукта у соответствующего поставщика,

bn – потребность продукта у соответствующего потребителя,

Cmn- затраты на транспортировку продукта m-поставщика n-потребителю.

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

 

Главные условия:

N = 10p + q,   1 ≤ p, q ≤ 9

В нашем случае p=1, q=3

 

a1 = 30*p*q-10*p-12*q

a2=a1+N

a3= (a1+a2)/2

a4= (a2+a3)/2

 

 

b1= (a3+a4)/2

b2= b1+N

b3= (b1+b2)/2

b4= (b2+b3)/2

 

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

 

Затраты транспортировки продукции от m-поставщика к n-потребителю можно рассчитать по следующей формуле:

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

Для реализации главной цели расчетного задания (нахождение такого плана поставок продукции, которой будет минимизировать транспортные задачи) необходимо:

1. Построить матричную  модель транспортной задачи.

2. Найти допустимые планы перевозок.

  2.1. Применить метод северо-западного угла.

  2.2. Применить метод минимальной стоимости.

3. Проверить планы на  оптимальность решения

4. Выбрать лучший план  из найденных допустимых планов  перевозок.

4. Применить метод потенциалов. Найти оптимальный план

5. Использовать программу QSB. Найти оптимальный план поставок.

6. Произвести сравнения  результатов и сделать выводы.

 

Рассчитаем все необходимые для решения показатели.

Запасы продуктов у поставщиков

a1 = 30*4*2-10*4-12*2=176

a2=176+42 =218

a3= (176+218)/2= 197

a4= (218+197)/2 = 207,5 ≈ 208

 

Потребность

b1= (197+207,5)/2 = 202,25 ≈ 202

b2= 202,25+42 = 244,25≈244

b3= (202,25+244,25)/2 = 223,25≈223

b4= (244,25+223,25)/2= 233,75≈234

 

Затраты (округлены до сотых)

С11=176/202 = 0,87

С12=176/244 = 0,72

С13=176/223 = 0,79

С14=176/234 = 0,75

С21=218/202 = 1,08

С22=218/244 =0,89

С23=218/223 =0,98

С24=218/234 =0,93

С31=197/202 =0,98

С32=197/244 =0,81

С33=197/223 =0,88

С34=197/234 =0,84

С41=208/202 = 1,03

С42=208/244 = 0,85

С43=208/223 =0, 93

С44=208/234 =0,89

 

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

 

 

 

 

 

 

 

 

 

 

 

2. Составление матричной модели транспортной задачи  

 

Для построения матричной модели необходимо:

 

• определить поставщиков и запасы продукции каждого из них. В данной задаче мы имеем дело с четырьмя поставщиками, которые имеют следующие запасы продукции (таблица 1).

 

Таблица 1

Поставщики и их запасы продукции

 

Поставщики	Запасы продукции (аm)
1	176
2	218
3	197
4	208

 

• определить потребителей и их потребность в продукции. В задаче указано четыре потребителя продукции, потребность которых оценивается в следующих цифрах (таблица 2).

 

Таблица 2

Потребители продукции

 

Потребители	Потребность в продукции (bn)
1	202
2	244
3	223
4	234

 

• проверить, выполняется ли условие баланса?

a= 176+218+197+208=  799

b= 202+244+223+234 = 903

В решаемой транспортной задаче условие баланса не выполняется (a<b). Мы имеем дело с дефицитом продукции. Для достижения баланса необходимо ввести фиктивного поставщика, запас продукции которого будет равняться  a5 = 903-799 = 104.

• для каждой пары поставщик – покупатель должны быть указаны транспортные затраты (в столбцах отражаются покупатели по порядку, в строчках – поставщики в соответствии со своим номером)

 

 

        С11  С12 С13 С14

                                                          С21  С22 С23 С24

С = С31  С32 С33 С34

                                                          С41  С42 С43 С44

                                                          С51  С52 С53 С54

 

0,87 0,72  0,79  0,75

1,08 0,89  0,98  0,93

С =       0,98  0,81 0,88  0,84

                                                            1,03 0,85  0,93  0,89

                                                            0        0       0      0

 

После того, как мы выполнили все требования для построения матричной модели, получим в результате следующую модель (таблица 3)

 

Таблица 3

Матричная модель транспортной задачи

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87	0,72	0,79	0,75
a2=218	1,08	0,89	0,98	0,93
a3=197	0,98	0,81	0,88	0,84
a4=208	1,03	0,85	0,93	0,89
a5=104	0	0	0	0

 

 

3. Нахождение допустимых планов перевозок

 

1. Метод северо-западного угла

 

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

Применим данный метод к конкретной задаче (таблица 4).

Таблица 4

Применение метода северо-западного угла

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87        176	0,72	0,79	0,75
a2=218	1,08        26	0,89        192	0,98	0,93
a3=197	0,98	0,81        52	0,88           145	0,84
a4=208	1,03	0,85	0,93           78	0,89         130
a5=104	0	0	0	0           104

 

 

В этом случае транспортные затраты составят С = 176*0,87 + 26*1,08 + 192*0,89 + 52*0,81 + 145*0,88 + 78*0,93 + 130*0,89 + 104*0= 710,04 денежных единиц.

Проанализируем полученное решение: при данном раскладе потребности в продукции первого, второго и третьего потребителя будут полностью удовлетворены, чего не скажешь о четвертом потребителе.  Его потребности в продукции будут удовлетворены примерно на 55,5 %, что является не самым лучшим раскладом для него.

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

Для того чтобы узнать, является ли план базисным или нет, надо исследовать решение на следующие условия:

1. Число положительных  клеток должно быть меньше  либо ровно N;

2. Отсутствие циклов.

N = m + n – 1. N = 8. Число положительных клеток данной модели равно 8.Это удовлетворяет условию  8 ≤ N. Из этого следует, что план невырожденный.

Также здесь отсутствует цикл.

В результате данный план является базисным.

Таким образом, в ходе применения метода северо-западного угла мы получили следующее решение (рис. 1) при транспортных затратах в 710,04 денежных единиц.

Рис. 1 Результат применения метода северо-западного угла

 

 

2. Метод минимальной стоимости

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