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

«Национальный исследовательский ядерный университет «МИФИ»

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

ПО ПРЕДМЕТУ

МАТЕМАТИЧЕСКИЕ МЕТОДЫ

НА ТЕМУ:

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

Сдал(а)                                                                                                 

Проверил(а) _______________________________

г. Обнинск

        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) 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) 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) 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) 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) 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

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

Считаем общую стоимость всех перевозок:

L1= L0 + цена цикла * q =1509 + (-3*4)= 1497 условных единиц

Цена цикла = Цена цикла = 2-12+5-1 = -6 < 0 – делаем перестановки.

q = 4

Цикл 3

Считаем общую стоимость всех перевозок:

L2= L1+ цена цикла * q = 1497+(-6 * 4)=1473 условных единиц

Цена цикла = 4-11+5-8 = -10 < 0 – делаем перестановки.

q = 18

Цикл 4

Считаем общую стоимость всех перевозок:

L3= L2+ цена цикла*q = 1473+ (-10*18) =1293 условных единиц

Цена цикла = 4-12+5-10+4-11 = -20 < 0 – делаем перестановки.

q = 8

Цикл 5             

Считаем общую стоимость всех перевозок:

L4= L3+ цена цикла*q = 1293 + (-20 * 8) = 1133 условных единиц

Цена цикла = 6-16+2-12= -20 < 0 – делаем перестановки.

q = 13

Цикл 6

Считаем общую стоимость всех перевозок:

L5= L4+ цена цикла*q = 1133 + (-20 * 13) = 873 условных единиц

Цена цикла = 14-16+2-4 = -4 < 0 – делаем перестановки.

q = 7

Цикл 7

Считаем общую стоимость всех перевозок:

L6= L5+ цена цикла*q = 873 + (-4 * 7) = 845 условных единиц

13