Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Курсовой проект по математическому моделированию - файл 1.docx


Загрузка...
Курсовой проект по математическому моделированию
скачать (258.7 kb.)

Доступные файлы (1):

1.docx259kb.05.02.2012 08:41скачать

1.docx

Реклама MarketGid:
Загрузка...
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

кафедра «высшая математика»

КУРСОВОЙ ПРОЕКТ

по предмету математическое моделирование

тема: «линейное программирование»

Проверил: Выполнил:

преподаватель студент группы ЭкТ-

Филипова Е. Г. Сычёв А. В.

Екатеринбург, 2010 г.



Графическое решение задач линейного программирования.

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

продукт

расход на 1 кг.

запас, кг.

клубничное

малиновое

ягоды

2

5

50

сахар

4

3

44

вода

4

1

36

Розничная цена 1 килограмма клубничного варенья равна 2 евро, а малинового 1 евро.

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

Решение:

Пусть x1, кг. – необходимое количество клубничного варенья; x2, кг. – необходимое количество малинового варенья. (x 1, x 2 ≥0)

Тогда получим систему ограничений:

2x1+5x2 ≤50 (l1) 4x1+3x2≤44 (l2)4x1+x2≤36 (l3)

fX=16x1+14x2→ max

Задача составлена. Решим ее графически.

Построим прямые l1, l2, l3

l1: x2≤50-2x15 l2: x2≤44-4x13 l3: x2≤36-4x1

x1

10

0

x2

6

10

x1

5

8

x2

8

4

x1

7

8

x2

8

4

Общее решение: A, B, C

Общее допустимое решение: A, B, C, D, 0, A

n={16;14} – нормальный вектор целевой функции. Строи линию уровня и передвигаем ее в сторону нормального вектора целевой функции до тех пор, пока она не коснется фигуру ровно один раз.

Таким образом оптимальное решение достигается в вершине С, С = l2∩l3

C: 4x1+3x2≤444x1+x2≤36 - ⇒ x2=4 ⇒ x1=36-44=8

Таким образом, для того, чтобы доход был максимальным необходимо изготавливать 8 килограмм клубничного варенья и 4 килограмма малинового. При этом доход от реализации продукции составляет:

fX=2* x1+x2=2*8+4=20 (евро)

Сосчитаем остаток продукции на складе фирмы:

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

50 – (8*2+4*5) =14 кг. – остаток ягод;

44 – (8*4+4*3)=0 кг. – остаток сахара;

36 – (8*4+4*1)=0 кг. – остаток воды.

Ответ: для того чтобы реализация от продажи было максимальным, фирме ежедневно нужно выпускать 8 килограмм клубничного варенья и 4 килограмма малинового. При таком выпуске продукции доход фирмы составляет 20 евро, при стоимости 1 килограмма клубничного варенья в 2 евро, а малинового – 1 евро. При этом на складе от суточного запаса продуктов, входящих в состав варенья остается: 14 килограмм ягод, 0 килограмм сахара и 0 килограмм воды.



Симплекс метод.

Задача: рассматриваем условие предыдущей задачи.

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

Решение:

Составляем каноническую модель

2x1+5x2+x3=504x1+3x2+x4=444x1+x2+x5=36

fX=-16x1-14x2→min

Нулевой шаг. Составим симплекс таблицу



bi

x1

x2

x3

x4

x5

50

2

5

1

0

0

44

4

3

0

1

0

36

4

1

0

0

1

:4 *(-1) *(-0,5)

0

2

1

0

0

0

X0 = x3,x4, x5- базисx1,x2=0-свободные (0; 0; 50; 44; 36) – опорное решение

fX0=0

Из последней строки выбираем наибольшее значение. Это число 2 ⇒ х1 – разрешающий столбец. Ищем минимальное значение в этом столбце.

min→50:2=2544:4=1136:4=9

Выбираем разрешающий элемент равный 4, получим новую симплекс таблицу.

Первый шаг.

bi

x1

x2

x3

x4

x5

32

0

4,5

1

0

-0,5

8

0

2

0

1

-1

:2 *(-2,25) *(-0,125) *(-0,25)

9

1

0,25

0

0

0,25

-18

0

0,5

0

0

-0,5

X1 = x1,x3, x4- базисx2,x5=0-свободные (9; 0; 32; 8; 0) – опорное решение

fX1=18

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



min→32:4,5=7,18:2=49:0,25=36

Переводим х2 в базис, получим новую симплекс таблицу.

Второй шаг.

bi

x1

x2

x3

x4

x5

14

0

0

1

-2,25

1,75

4

0

1

0

0,5

-0,5

8

1

0

0

-0,125

0,375

-20

0

0

0

-0,25

-0,25

X2 = x1,x2, x3- базисx4,x5=0-свободные (8; 4; 14; 0; 0) – оптимальное решение

fX2=20 (евро)

В последней строке нет положительный элементов. Следовательно, симплекс метод закончен.

Ответ: в ходе решения задачи симплекс методом получили оптимальное решение (8;4;14;0;0), где первые две цифры являются значением х1 (количество килограмм клубничного варенья необходимое выпускать ежедневно фирме, при реализации которого она бы получала максимальный доход) и х2 (количество килограмм малинового варенья необходимое выпускать ежедневно фирме, при реализации которого она бы получала максимальный доход) соответственно, а остальные – это остаток сырья на складе. Так же получили значение fX2=20 (евро), являющиеся максимальным доходом от реализации продукции.

Правильность вычислений можно проверить сравнением ответов с задачей, решенной графическим способом:

ответ полученный

графическим способом

ответ полученный симплекс методом

х1, кг

8

8

х2, кг

4

4

fX, евро

20

20

остаток ягод, кг

14

14

остаток сахара, кг

0

0

остаток воды, кг

0

0



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

Задача: рассматриваем условие первой задачи.

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

Решение:

Составим двойственную задачу из исходной (см. условие графической задачи). Для этого все матрицы исходной задачи транспонируются. При этом неравенство исходной системы имеют одинаковый знак (≤ или ≥)

Исходная задача:
2x1+5x2 ≤50 (l1) 4x1+3x2≤44 (l2)4x1+x2≤36 (l3)

fX=16x1+14x2→ max,

где х1 и х2 – количество килограмм каждого из варений.

Двойственная задача:

2y1+4y2+4y3≥25y1+3y2+y3≥1

gY=50y1+44y2+36y3

y1, y2, y3≥0,

где y1, y2, y3 – цена одного килограмма ягод, сахара и воды соответственно

gY – опорное решение двойственной задачи.

Имеем х1=8 и х2=4. Подставим их в ограничения исходной задачи и найдем строгое неравенство.

2*8+5*4=36<504*8+3*4=44≤444*8+1*4=36≤36 ⇒ y1=0 ⇒ 4y2+4y3=23y2+y3=1 - ⇒

y2+3y3=1

y2=1-y3

4-12y3=2

y3=0,25 ; y2=0,25

gY=50*0+44*0,25+36*0,25=11+9=20 (евро)

Ответ: продавец согласен продать, а покупатель купить за 0,25 евро один килограмм сахара, за такую же цену килограмм воды, а килограмм ягод отдать бесплатно. При этом минимальные затраты на производство варенья составят 20 евро.



Правильность решения можно проверить, сравнив данные y2и y3 из этой задачи с данными x4и x5 из последней таблицы, полученной в ходе решения симплекс методом. Эти данные должны быть равны друг другу, но только с обратным знаком.

Проверка:

y2=-x4;

0,25=-(-0,25);

0,25=0,25;

y3=-x5;

0,25=-(-0,25);

0,25=0,25;



Транспортная задача.

Задача: в порту стоят три рыболовецких судна А1, А2, А3, вмещающих рыбу в количествах 125 тонн, 125 тонн и 105 тонн соответственно. Необходимо доставить свежо пойманную рыбу в пять магазинов, находящиеся от порта на 60, 65, 95, 35 и 100 километров соответственно. Стоимость перевозки одной тонны из судна Аi в магазин Bj заданы в виде матрицы.

C=8224 71015 15236 279 41835 ; A=125125105 ; B=6065 9535100

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

Решение:

A=B=125+125+105=60+65+95+100 ⇒

355=355 ⇒ закрытая транспортная задача.

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

B1

B2

B3

B4

B5

запас

A1

8

7

15

2

4

125

60

65

0

A2

2

10

23

7

18

125

95

30

A3

24

15

6

9

35

105

5

100

потребности

60

65

95

35

100

355

n+m-1=5+3-1=7

F – суммарные затраты на перевозку

F1=60*8+65*7+0*15+95*23+30*7+5*9+100*35=6875 (рублей)

Метод наименьшей стоимости в таблице.

V1

V2

V3

V4

V5

запас

B1

B2

B3

B4

B5

U1

A1

8

7

15

2

4

125

0

35

90

U2

A2

2

10

23

7

18

125

60

65

U3

A3

24

15

6

9

35

105

95

10

потребности

60

65

95

35

100

355

n+m-1=5+3-1=7

F – суммарные затраты на перевозку

F2=0*7+35*2+90*4+60*2+65*10+95*6+10*35=2120 (рублей)

Метод потенциалов.

Проверим на оптимальность план, полученный во второй таблице.

V1

V2

V3

V4

V5

запас

B1

B2

B3

B4

B5

U1

A1

8

7

15

2

4

125

0

35

90

U2

A2

2

10

23

7

18

125

60

65

U3

A3

24

15

6

9

35

105

95

10

потребности

60

65

95

35

100

355

Для занятых клеток

U1+V2=7U1+V4=2U1+V5=4U2+V1=2U2+V2=10U3+V3=6U3+V5=35 U1=0U2=3U3=31 V1=-1V2=7V3=-25V4=2V5=4

Для свободных клеток

U1+V1=-1≤8U1+V3=7≤15U2+V3=-22≤23 U2+V4=5≤7 U2+V5=7≤18U3+V1=30≤24 (!∆=6)U3+V2=38≤15 (!∆=23)U3+V4=33≤9 (!∆=24)

Так как имеются нарушения, то проверяемый план не является оптимальным. Среди нарушений выбираем наибольшее и строим цикл перерасчета данной клетки. Наибольшим нарушением является U3+V4=33≤9 (!∆=24)

V1

V2

V3

V4

V5

запас

B1

B2

B3

B4

B5

U1

A1

8

7

15

2

4

125

0

25

100

U2

A2

2

10

23

7

18

125

60

65

U3

A3

24

15

6

9

35

105

95

10

потребности

60

65

95

35

100

355

n+m-1=5+3-1=7

F – суммарные затраты на перевозку



F3=0*7+25*2+100*4+60*2+65*10+95*6+10*9=1880 (рублей)

Для занятых клеток

U1+V2=7U1+V4=2U1+V5=4U2+V1=2U2+V2=10U3+V3=6U3+V4=9 U1=0U2=3U3=7 V1=-1V2=7V3=-1V4=2V5=4

Для свободных клеток

U1+V1=-1≤8U1+V3=-1≤15U2+V3=2≤23 U2+V4=5≤7 U2+V5=7≤18 U3+V1=6≤24U3+V2=14≤15U3+V5=11≤35

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

Ответ: в ходе решения задачи получили следующие данные:

минимальные суммарные затраты на перевозку

F1 = 6875 рублей (метод северо-западного угла);

F2 = 2120 рублей (метод наименьшей стоимости);

F3 = 1880 рублей (метод потенциалов)

оптимальный план перевозок можно представить в виде матрицы

C=0600 0650 0095 25010 10000



Транспортная задача на сети.

Задача: даны узлы (обозначены кругом или квадратом) и дуги (прямые, соединяющие узлы). На каждой дуге указывается длина или стоимость перевозки единицы груза. На каждой вершине показываются запасы груза со знаком «+» (склад - квадрат) и потребности в этом грузе со знаком «-» (потребители – круг).

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

Решение:

составим схему.

Число загруженных дуг n-1, где n – количество вершин

n=10; 10 – 1 = 9 – загруженные дуги

Один из потенциалов выбираем произвольно. Пусть А1=100. Далее двигаемся по загруженным дугам, если направление совпадает, то к известному потенциалу прибавляем значение указанное на дуге, если направление встречное – вычитаем.

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

A1-B1=119-100=19≤50

A1-B4=100-93=7≤27

B1-B4=119-93=26≤32

B2-B5=140-120=20≤25

B2-A2=120-110=10≤25

B4-A2=110-93=17≤42

B4-B3=93-91=2≤15

B4-B6=104-93=11≤20

A2-B6=110-104=6≤28

B5-B7=140-127=13≤35

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

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

F=20*20+28*50+30*30+15*80+17*10+28*60+23*30+17*90+30*10=400+1400+900+1200+170+1680+690+1530+300=8270 (условных денежных едениц).

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

F=8270 условных денежных едениц.




Скачать файл (258.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации