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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Транспортная задача линейного программирования

Информация:

Тип работы: курсовая работа. Добавлен: 08.11.2012. Сдан: 2012. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):


?Обнинский математический техникум – филиал Федерального государственного бюджетного образовательного учреждения высшего профессионального образования
 
 
 
«Национальный исследовательский ядерный университет «МИФИ»
 
 
 
 
 
КУРСОВАЯ РАБОТА
ПО ПРЕДМЕТУ
МАТЕМАТИЧЕСКИЕ МЕТОДЫ
НА ТЕМУ:
Транспортная задача линейного программирования
 
 
 
 
 
 
 
Сдал(а)                                                                                                 
Проверил(а) _______________________________
 
 
 
г. Обнинск
        2012г.
 
Содержание:
1. Введение……………………………………………………………………….3
2. Составление допустимых планов………………………………………….…5
2.1. Метод северо-западного угла………………………………………...5
              2.2. Метод минимальной стоимости по строке……………………....….6
2.3. Метод минимальной стоимости по столбцу…………………….…..7
              2.4. Метод минимальной стоимости………….…………….………...…..8
2.5. Метод двойственного предпочтения………….……….………...…..9
3. Метод циклических перестановок…………………………...………………10
4. Метод потенциалов………………………………………………………….14
5. Вывод………………………..……………………………………………...…21
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. Введение
 
Постановка транспортной задачи.
Имеется m пунктов отправления  А1, А2…Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2…аm единиц.
Имеется n пунктов назначения  В1, В2…Вn, которые подают заявки соответственно на в1, в2…вn единиц груза.
              Сумма всех заявок = сумме всех запасов:  ?ai=?bj - когда идет выполнение этого равенства, то классическая транспортная задача, иначе называемая, транспортной задачей с правильным балансом.
              Встречаются такие варианты транспортной задачи, где условие ?ai=?bj нарушено. В этих случаях говорят о транспортной задаче с неправильным балансом.
              Требуется составить такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальной.
              Рассмотрим транспортную задачу как задачу линейного программирования и составим математическую модель, т. е. запишем целевую функцию и ограничения к ней.
              Количество неизвестных равно m * n, обозначаем их через Xij – это количество единиц груза, отправляемого из i-того пункта отправления, в j-тый пункт назначения, т. е. из Ai в Bj.
Все неизвестные можно записать в виде матрицы размерностью m на n.
 

 
Называть ее будем планом перевозок, а сами Xij – перевозками, любая Xij больше или равна нулю, отрицательных значений они принимать не могут.
Целевая функция -  суммарная стоимость всех перевозок.

Знак двойной суммы означает, что суммирование производится по всем парам пунктов отправления и назначения (ПО и ПН).
Далее нужно проверить план на допустимость, опорность и оптимальность.
              Будем называть любой план перевозок допустимым, если все заявки удовлетворены и все запасы исчерпаны.
              Допустимый план будет опорным, если в нем отличны от нуля не более
m + n – 1 базисных перевозок, а остальные равны нулю.
              План будет называться оптимальным, если среди всех допустимых планов, он приводит к минимальной суммарной стоимости перевозок.
 
Условие задачи: Имеется 5 пунктов отправления: А1, А2, А3, А4 и А5, в которых сосредоточены запасы, соответственно: а1 = 24, а2 = 29, а3 =30,
а4 = 29, а5 =32. И шесть пунктов назначения: В1, В2, В3, В4, В5, В6, которые подали заявки соответственно: в1 = 20, в2 =26, в3 =21, в4 =20, в5 =27, в6 =30.
Известны стоимости Сij перевозки единицы груза от каждого пункта отправления до каждого пункта назначения:
С11 = 16               С12 = 8               С13 = 10               С14 =1               С15 =2              С16 = 3
С21 = 14              С22 = 11               С23 = 5               С24 = 8               С25 = 4               С26 =8
С31 = 14               С32 = 4               С33 = 8              С34 = 10               С35 = 13               С36 = 14
С41 = 6              С42 = 6               С43 = 15               С44 = 5              С45 = 12               С46 = 12
С51 = 16               С52 = 14               С53 = 3              С54 = 4               С55 = 9               С56 = 9
 
Требуется составить такой план перевозок, чтоб все заявки были выполнены, а общая стоимость всех перевозок минимальная. Составить план перевозок 5 способами. Проверить методами потенциалов.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

 

 

 
 
 
 
 

2.Составление допустимых планов

 
              Сначала проверим задачу на правильность баланса. Баланс считается правильным, когда количество всех заявок  равно количеству всех запасов.
              Определяем общее количество всех запасов: 24 + 29 + 30 + 29 + 32 = 144 единиц груза.
              Определяем общее количество всех заявок: 20 + 26 + 21 + 20 + 27 + 30 = 144 единицы.
              Общее количество всех запасов = общему количеству всех заявок. Из этого следует, что задача с правильным балансом.
 
Далее составляем план перевозок.
             

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

 
 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
20
4
 
 
 
 
A2
            14     
11
5
8
4
8
29
 
22
7
 
 
 
A3
14
4
8
10
13
14
30
 
 
 14
16
 
 
A4
6
            6       
15
5
12
12
29
 
 
 
 4
25
 
A5
16
14
3
4
9
9
32
 
 
 
 
 2
30
Ai
20
26
21
20
27
30
   144
 
 
Проверяем план на допустимость: все заявки удовлетворены, запасы исчерпаны, значит, что план допустимый.
Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.
Считаем общую стоимость всех перевозок:
L=20*16+4*8+22*11+35+14*8+16*10+4*5+25*12+2*9+30*9=1509условных единиц.
 

2.2.Метод минимальной стоимости по строке

 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
 
 
 
 20

 
A2
            14     
11
5
8
4
8
29
 
 
6
 
23 
 
A3
14
4
8
10
13
14
30
 
 26

 
 
 
A4
6
            6       
15
5
12
12
29
 20
 
 
 
 
9
A5
16
14
3
4
9
9
32
 
 
 11
 
 
21
Ai
20
26
21
20
27
30
   144
 
Проверяем план на допустимость: все заявки удовлетворены, запасы исчерпаны, значит, что план допустимый.
Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.
Считаем общую стоимость всех перевозок:
L=20*1+4*2+6*5+23*4+26*4+4*8+20*6+9*12+11*3+21*9 =736условных единиц.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
             
 
 

2.3.Метод минимальной стоимости по столбцу

 
 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
 
 
 
 20

 
A2
            14     
11
5
8
4
8
29
 
 
 
 
23 

A3
14
4
8
10
13
14
30
 
 26
 
 
 

A4
6
            6       
15
5
12
12
29
 20
 
 
 
 
9
A5
16
14
3
4
9
9
32
 
 
 21
 
 
11
Ai
20
26
21
20
27
30
   144
 
 
Проверяем план на допустимость: все заявки удовлетворены, запасы исчерпаны, значит, что план допустимый.
Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.
Считаем общую стоимость всех перевозок:
L=20*1+4*2+6*8+23*4+26*4+4*14+20*6+9*12+11*9+21*3 =718 условных единиц.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
             
 

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

 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
 
 
 
 20

 
A2
            14     
11
5
8
4
8
29
 
 
 
 
23 

A3
14
4
8
10
13
14
30
 
 26
 
 
 

A4
6
            6       
15
5
12
12
29
 20
 
 
 
 
9
A5
16
14
3
4
9
9
32
 
 
 21
 
 
11
Ai
20
26
21
20
27
30
   144
 
Проверяем план на допустимость: все заявки удовлетворены, запасы исчерпаны, значит, что план допустимый.
Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.
Считаем общую стоимость всех перевозок:
L=20*1+4*2+6*8+23*4+26*4+4*14+20*6+9*12+11*9+21*3 =718 условных единиц.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.5. Метод двойственного предпочтения

 
 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
 
 
 
 20

 
A2
            14     
11
5
8
4
8
29
 
 
6
 
23 
 
A3
14
4
8
10
13
14
30
 
 26

 
 
 
A4
6
            6       
15
5
12
12
29
 20
 
 
 
 
9
A5
16
14
3
4
9
9
32
 
 
 11
 
 
21
Ai
20
26
21
20
27
30
   144
 
Проверяем план на допустимость: все заявки удовлетворены, запасы исчерпаны, значит, что план допустимый.
Проверяем план на опорность: (количество заявок + количество запасов – 1) m + n - 1 = 6 + 5 - 1 = 10. Количество базисных клеток 10. Следовательно план является опороным.
Считаем общую стоимость всех перевозок:
L=20*1+4*2+6*5+23*4+26*4+4*8+20*6+9*12+11*3+21*9 =736 условных единиц.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3. Метод циклических перестановок
 
Циклические перестановки делаем, используя таблицу северо-западного угла. В цикле участвует сколько угодно базисных клеток и одна свободная. Цикл имеет право поворачивать только на базисной клетке.
Если цена цикла  больше нуля, то цикл нам не подходит, если меньше, то мы делаем перестановки.
Цикл 1
 
 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
20
-4
 
+ *
 
 
A2
            14     
11
5
8
4
8
29
 
+22
-7
 
 
 
A3
14
4
8
10
13
14
30
 
 
 +14
-16
 
 
A4
6
            6       
15
5
12
12
29
 
 
 
 4
25
 
A5
16
14
3
4
9
9
32
 
 
 
 
 2
30
Ai
20
26
21
20
27
30
   144
 
L0=21*11+16*10+8*11+18*4+13*5+21*12+19*12+16*6+21*10+21*8+24*0=1509 условных единиц
Цена цикла = 1-10+8-5+11-8 = -3 < 0 – делаем перестановки.
q = 4
 
 
 
 
 
 
 
 
 
Цикл 2
 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
20
 
 
-4
+ *
 
A2
            14     
11
5
8
4
8
29
 
26
3
 
 
 
A3
14
4
8
10
13
14
30
 
 
 18
12
 
 
A4
6
            6       
15
5
12
12
29
 
 
 
 +4
-25
 
A5
16
14
3
4
9
9
32
 
 
 
 
 2
30
Ai
20
26
21
20
27
30
   144
 
Считаем общую стоимость всех перевозок:
L1= L0 + цена цикла * q =1509 + (-3*4)= 1497 условных единиц
Цена цикла = Цена цикла = 2-12+5-1 = -6 < 0 – делаем перестановки.
q = 4
Цикл 3
 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
20
 
 
 
4
 
A2
            14     
11
5
8
4
8
29
 
-26
+3
 
 
 
A3
14
4
8
10
13
14
30
 
+* 
 -18
12
 
 
A4
6
            6       
15
5
12
12
29
 
 
 
 8
21
 
A5
16
14
3
4
9
9
32
 
 
 
 
 2
30
Ai
20
26
21
20
27
30
   144
 
Считаем общую стоимость всех перевозок:
L2= L1+ цена цикла * q = 1497+(-6 * 4)=1473 условных единиц
Цена цикла = 4-11+5-8 = -10 < 0 – делаем перестановки.
q = 18
 
Цикл 4
 
 

и т.д.................


 
В1
В2
В3
В4
В5
В6
Ai
A1
16
8
10
              1
2
3
24
20
 
 
 
4
 
A2
            14     
11
5
8
4
8
29
 
-8
21
 
+*
 
A3
14
4
8
10
13
14
30
 
+18
 
-12
 
 
A4
6
            6       
15
5
12
12
29
 
 
 
+ 8
-21
 
A5
16
14
3
4
9
9
32

Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.