Xreferat.com » Рефераты по экономико-математическому моделированию » Экономико-математический практикум

Экономико-математический практикум

VALIGN=TOP>8 0 1 0 ← А8 М 15 13 2 9 4 6 0 0 1

Экономико-математический практикум

0 -1 5 -6 -8 2 0 0 0

Экономико-математический практикум

48 28 19 10 19 19 0 0 0

Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора Аk, вводимого в базис опорного решения, и вектора Аl, выводимого из базиса. В столбце «А3» (см. табл. 2.1) за разрешающий элемент выбираем коэффициент 9 в третьей строке и выполняем преобразование Жордана.

Вектор А3 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем первое опорное решение Экономико-математический практикум с базисом Экономико-математический практикум (табл. 2.3). Целевая функция Экономико-математический практикум =31,33М -10. Это решение не является оптимальным, так как имеются положительные оценки.

Таблица 2.3





1 -5 6 8 -2 М M M

Б

Сб А0 А1 А2 А3 А4 А5 А6 A7 A8

А6 М 14,33 9,56 6,78 0,00 11,56 4,33 1,00 0,00 -0,11

A7 M 17,00 14,00 10,00 0,00 3,00 8,00 0,00 1,00 0,00
← А3 6 1,67 1,44 0,22 1,00 0,44 0,67 0,00 0,00 0,11

Экономико-математический практикум

10,00 -7,67 -6,33 0,00 5,33 -6,00 0,00 0,00 -0,67


31,33 13,56 16,78 0,00 14,56 12,33 0,00 0,00 -1,11

Вводим вектор А4 в базис, получаем второе опорное решение (таблица 2.4) Экономико-математический практикум с базисом Экономико-математический практикум. Целевая функция Экономико-математический практикум = 3,38+13,28M. Далее в таблице 2.4 приведены расчеты с третьей по пятую итерации.


Таблица 2.4




4 2 -1 5 1 М M M
Б Сб А0 А1 А2 А3 А4 А5 А6 A7 A8
a4 8 1,24 0,83 0,59 0,00 1,00 0,38 0,09 0,00 -0,01
a7 M 13,28 11,52 8,24 0,00 0,00 6,88 -0,26 1,00 0,03
a3 6 1,12 1,08 -0,04 1,00 0,00 0,50 -0,04 0,00 0,12

Экономико-математический практикумЭкономико-математический практикум


3,38 -12,08 -9,46 0,00 0,00 -8,00 -0,46 0,00 -0,62

13,28 1,52 8,24 0,00 0,00 6,88 -1,26 0,00 -0,97
a4 8 0,52 0,20 0,14 0,00 1,00 0,00 0,10 -0,05 -0,01
a5 -2 1,93 1,68 1,20 0,00 0,00 1,00 -0,04 0,15 0,00
a3 6 0,15 0,24 -0,64 1,00 0,00 0,00 -0,02 -0,07 0,11


18,84 1,33 0,13 0,00 0,00 0,00 -0,76 1,16 -0,58


0,00 -10,00 0,00 0,00 0,00 0,00 -1,00 -1,00 -1,00
a1 1 2,60 1,00 0,69 0,00 5,04 0,00 0,51 -0,27 -0,06
a5 -2 -2,42 0,00 0,04 0,00 -8,44 1,00 -0,89 0,61 0,10
a3 6 -0,47 0,00 -0,80 1,00 -1,20 0,00 -0,14 -0,01 0,13


4,19 0,00 -0,79 0,00 -6,68 0,00 -1,44 1,53 -0,51


25,99 0,00 6,90 0,00 50,35 0,00 4,07 -3,75 -1,56

Целевая функция после пятой итерации равна Экономико-математический практикум = 4,19. Положительных оценок нет, план оптимален. Ответ: min Z(X*) =4,2.


3.Построим двойственную задачу


Используя вторую симметричную пару двойственных задач, составим задачу, двойственную к исходной:


Экономико-математический практикум

Экономико-математический практикум


Вводим неотрицательные дополнительные переменные у4, у5, у6 у7, у8 для приведения задачи к каноническому виду:


Экономико-математический практикум

Экономико-математический практикум


Находим начальное опорное решение Y1 = (0,0,0,1,-5,6,8,-2) с базисом Б1 = (А4, А5, А6, А7, А8). Решение задачи симплексным методом приведено в табл. 2.5. (расчеты табл.2.2. и табл.2.4.)

Таблица 2.5





1 -5 6 8 -2 М M M

Б

Сб А0 А1 А2 А3 А4 А5 А6 A7 A8
← А6 М 16 11 7 1 12 5 1 0 0

A7 M 17 14 10 0 3 8 0 1 0

А8 М 15 13 2 9 4 6 0 0 1

Экономико-математический практикум

0 -1 5 -6 -8 2 0 0 0

Экономико-математический практикум

48 28 19 10 19 19 0 0 0

a1 1 2,60 1,00 0,69 0,00 5,04 0,00 0,51 -0,27 -0,06

a5 -2 -2,42 0,00 0,04 0,00 -8,44 1,00 -0,89 0,61 0,10

a3 6 -0,47 0,00 -0,80 1,00 -1,20 0,00 -0,14 -0,01 0,13

Экономико-математический практикумЭкономико-математический практикум



4,19 0,00 -0,79 0,00 -6,68 0,00 -1,44 1,53 -0,51

Экономико-математический практикумЭкономико-математический практикум


25,99 0,00 6,90 0,00 50,35 0,00 4,07 -3,75 -1,56

Приведем оптимальное решение прямой задачи


Экономико-математический практикум


Окончательный базис, соответствующий оптимальному решению прямой задачи, состоит из векторов А2А3А4 поэтому базисная матрица имеет вид


Экономико-математический практикум


Решение прямой задачи начиналось с единичного базиса А6,А7,А8 . Поэтому в окончательной таблице указанные столбцы преобразуются в матрицу Экономико-математический практикум, обратную к базисной матрице Экономико-математический практикум, следовательно,

Экономико-математический практикум


Оптимальный план двойственной найдем из соотношения


Экономико-математический практикум


Откуда Экономико-математический практикум При этом плане максимальное значение функции двойственной задачи составляет величину равную

Экономико-математический практикум

Максимальное значение целевой функции двойственной задачи совпадает с минимальным значением целевой функции прямой задачи.

Проанализируем решение задачи, используя условия дополняющей нежесткости (вторую теорему двойственности).

Подставляем координаты оптимального решения двойственной задачи Экономико-математический практикум в систему ограничений.


Экономико-математический практикум

Экономико-математический практикум


Первое, третье и пятое ограничения выполняются как строгие неравенства, следовательно, их координаты оптимального решения исходной задачи равны нулю: Экономико-математический практикум. Учитывая это, первую, вторую и пятую координаты оптимального решения Х* находим при совместном решении уравнений-ограничений исходной задачи:


Экономико-математический практикум


Ответ: Z(X) = 4,2 при Х* = (0;1,6; 0;4,9;0).


Задача № 3


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

Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.


24



34 30 39 29 18 82
40 35 45 41 10 36
36 38 41 50 8 79
14 10 13 10 12 80
77 60 22 68 50


Решение.

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

Исходные данные задачи сведем в таблицу (табл. 3.1).


Таблица 3.1.

Поставщики Потребители Запасы

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум


Экономико-математический практикум

34 30 39 29 18

82

Экономико-математический практикум

40 35 45 41 10

36

Экономико-математический практикум

36 38 41 50 8

79

Экономико-математический практикум

14 10 13 10 12

80

Потребности

77

60

22

68

50



Решение. Построим опорный план задачи методом северо-западного угла.

Объем перевозки Экономико-математический практикум и последовательность заполнения матрицы Экономико-математический практикум будем записывать в соответствующие клетки табл. 3.2.

Цифры, стоящие в скобках над объемами перевозок, обозначают номер шага, на котором определяются эти перевозки.

1. х11(1)=min(82,77)=77. Потребности первого потребителя удовлетворены, исключаем его. Запасы первого поставщика уменьшились на х11(1) и стали равны (82-77=5) 5.

2. х12(1)=min(5,60)=5. Запасы первого поставщика исчерпаны, исключим первую строку. Второй потребитель удовлетворил свои потребности на 5 единиц, его спрос уменьшился на величину х11(1) и стал равным 55.

3. х22(3)=min(36,55)=36. После третьего шага ресурсы поставщика А2 исчерпаны. Спрос потребителя B2 равен b2(3)=55-36=19.

4. х23(4)=min(79,19)=19. Следует исключить потребителя B2. Ресурсы поставщика А3(4) = a3 – х23(4)=79-19=60 составляет 60 единиц.

5. х33(5)=min(60,22)=22. Потребитель В3 полностью удовлетворил свой спрос, исключаем столбец 3.

6. х34(6)=min(38,68)=38. Следует исключить поставщика А3, запасы которого исчерпаны. Спрос потребителя В4 в4(6) – х34(5)=68-38=30 составляет 30 единиц.

7. х44(7)=min(80,30)=30. Спрос четвертого потребителя удовлетворен. Запасы поставщика А4 составляет

80-30=50.

8. х45(8)=min(50,50)=0. Запасы исчерпаны, потребности удовлетворены.

Опорный план построен (табл. 3.2).


Таблица 3.2.

34

30

39

29

18


77(1) 5(2)


82

40

35

45

41

10



36(3)


36

36

38

41

50

8



19(4) 22(5) 38(6)

79

14

10

13

10

12





30(7) 50(8)

80

77

60

22

68

50



Суммарные транспортные издержки на перевозку продукции от поставщиков к потребителю составляют

Экономико-математический практикум

2.Метод минимального элемента.


Исходные данные

поставщики потребители Запасы

В1 В2 В3 В4 В5
А1 34 30 39 29 18

82

А2 40 35 45 41 10

36

А3 36 38 41 50 8

79

А4 14 10 13 10 12

80

потребности

77

60

22

68

50



1. Экономико-математический практикум Объем запасов и потребностей после первого шага уменьшается на величину: х31(1)=50; Экономико-математический практикум. Запасы пятого поставщика исчерпаны, потребности первого потребителя уменьшились на 50 единиц и стали равны 29, исключаем пятый столбец.

2. Экономико-математический практикум. Объем запасов и потребностей после второго шага уменьшается на величину: х42(2)=60; Экономико-математический практикум. Потребности пункта В2 удовлетворены, исключим из рассмотрения второй столбец.

3. Экономико-математический практикум. Объем запасов и потребностей после третьего шага уменьшается на величину: х44(3)=20; Экономико-математический практикум. Запасы пункта А4 исчерпаны, исключим из рассмотрения четвертую строку.

4. Экономико-математический практикум. Корректируем объемы запасов и потребностей после четвертого шага: Экономико-математический практикум. Потребности пункта В4 удовлетворены, исключим четвертый столбец.

5. Экономико-математический практикум. После пятого шага запасы поставщика А1 будут исчерпаны, исключаем первую строку. Потребности В1 равны: Экономико-математический практикум.

6. Экономико-математический практикум. После шестого шага запасы третьего поставщика будут исчерпаны Экономико-математический практикум, потребности первого потребителя равны Экономико-математический практикум. Исключаем третью строку.

7. Экономико-математический практикум. После седьмого шага запасы второго поставщика будут равны Экономико-математический практикум, потребности первого потребителя удовлетворены.

8. Экономико-математический практикум. После восьмого шага запасы и потребности будут удовлетворены.

Потребности всех потребителей удовлетворены, запасы поставщиков исчерпаны. После седьмого шага мы получили исходный опорный план Экономико-математический практикум (Табл.3.3).


Х0 Таблица 3.3.

34

30

39

29

18


34(5)

48(4)

82

40

35

45

41

10


14(7)
22(8)

36

36

38

41

50

8


29(6)


50(1)

79

14

10

13

10

12



60(2)
20(3)

80







77

60

22

68

50



Также как и в предыдущем случае, номер шага помещен в скобках над объемами перевозок. Суммарные транспортные расходы, соответствующие данному плану перевозок равны

Экономико-математический практикум

По сравнению с расчетом по методу северо-западного угла суммарные транспортные расходы уменьшились с 8452 у.е. до 6342 у.е.

Для проверки плана на оптимальность составим систему уравнений, следуя условию — для базисных переменных сумма потенциалов равна тарифу. Значение одного из потенциалов зададим произвольно (пусть Экономико-математический практикум), последовательность вычисления остальных потенциалов указана ниже: 1), 2),…, 8).


Экономико-математический практикум


Потенциалы поставщиков Экономико-математический практикум поместим слева от таблицы, а потенциалы потребителей Экономико-математический практикум – сверху над таблицей (табл.3.4).


Таблица 3.4



34

29

39

29

6

0 34
30
39
29
18



34(5)







48(4)



82




-1
0


-12

6 40
35
45
41
10



14(7)




22(8)






36




0


-6
-2

2 36
38
41
50
8



29(6)










50(1)

79




-7
0
-19



-19 14
10
13
10
12






60(2)




20(3)



80


1


7


-25



77



60



22



68



50




Для небазисных переменных вычислим оценки по формуле:


Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум


Значения оценок поместим в левом нижнем углу незанятых клеток табл. 3.4. Фиксируем наибольшую положительную оценку. В данном случае: Экономико-математический практикум. Разрешающей объявим коммуникацию (4,3). Строим цикл пересчета, который показан в табл. 3.4 пунктирной линией.

Величина корректировки ρ=(58,79)=58. Вносим изменение в план: перевозки отрицательного полуцикла уменьшаем на Экономико-математический практикум, а перевозки положительного полуцикла увеличиваем на эту же величину, остальные перевозки оставим без изменения. Переменная х11 вводится в базис со значением =58,переменная х14 выводится из базиса. Получим план Экономико-математический практикум (табл. 3.5).

План Экономико-математический практикум Таблица 3.5



34

29

39

29

6

0 34
30
39
29
18



34(5)







48(4)



82




-1
0


-12

6 40
35
45
41
10



14(7)




22






36




0


-6
-2

2 36
38
41
50
8



29(6)










50(1)

79




-7
0
-19



-19 14
10
13
10
12






60(2)




20(3)



80


1


7


-25



77



60



22



68



50




Значение функции уменьшилось на (38*16-9*38=290) и стало: Экономико-математический практикум

План не оптимален. Заново вычисляем потенциалы и оценки (табл. 3.6). Наибольшая положительная оценка– это Экономико-математический практикум, план не оптимален. Строим цикл пересчета и определяем величину корректировки плана ρ=(48,58)=48.


Таблица 3.6

План X2



34

29

39

29

6

0 34
30
39
29
18






14




68(4)



82




-1
0


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: