Двойственность в линейном программировании. Анализ оптимального плана по двойственным оценкам основных переменных

Автор работы: Пользователь скрыл имя, 24 Апреля 2013 в 21:46, контрольная работа

Краткое описание

Целью контрольной работы является изучить литературу по выбранной теме и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования, а также решить двойственную задачу линейного программирования с помощью программы MS Excel.
Контрольная работа состоит из одного теоретического вопроса и двух задач линейного программирования, решаемых: симплексным методом и распределительным методом.

Содержание

Введение 3
1 Двойственность в линейном программировании. 4
Прямые и двойственные задачи ЛП 4
Основные теоремы двойственности. 7
Виды математических моделей двойственных задач. 11
Двойственный симплексный метод. 12
2 Разработка программы. 15
2.1. Постановка задачи. 15
2.2. Построение математической модели. 16
2.3. Описание решения данной задачи. 17
3 Анализ оптимального плана по двойственным оценкам основных переменных. 24
Заключение. 26
Литература. 27
Контрольная задача №1 28
Контрольная задача №2 34

Скачать полностью (210.50 Кб) Сколько стоит заказать работу?
Прикрепленные файлы: 1 файл

эмм готово.docx

— 235.63 Кб (Скачать документ)

2x₂+5x₄+9x₇≤40600

    1. Труд высококвалифицированный, чел.час.

18x₁+30x₃+40x₅≤220000

    1. Труд средней квалификации, чел.час.

20x₂+32x₄+48x₆+50x₇≤160000

  1. Блок ограничений по производству продукции для выполнения плана выпуска продукции.
    1. Продукции А, шт.  x₁+x₂≥5000
    1. Продукции Б, шт.   x₃+x₄≥2250
    2. Продукции В, шт.   x₅+x₆+x₇≥4000

Целевая функция – максимум прибыли, руб.

 Z=300x₁+500x₂+350x₃+700x₄+720x₅+1200x₆+1300x₇→max

 

Матрица решения задачи оптимизации производственной программы предприятия

 

Переменные

Объем левой части ограничения

Тип

Объем правой части ограничения

     

X1-выпуск прод-ии А

1тех. спос

X2-выпуск прод-ии

 А 2тех.сп.

X3-выпуск прод-ии

Б 1тех.сп.

X4-выпуск прод-ции Б 2тех.сп.

X5-выпуск прод-ции В 1тех.сп.

X6-выпуск прод-ции В 2тех. Сп.

X7-выпуск прод-ции 3тех.сп.

   
 

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ

1257,143

3742,857

0

2250

4934,286

0

262,8571

Наименование  ресурсов

Ограничения

Оборудование

Новое

10

  

20

  

30

32

  

160600

<=

160600

Старое

  

12

  

25

    

40

111678,6

<=

400600

Сырье

Высококачественное

2

  

5

  

10

10

  

51857,14

<=

70600

Стандартное

  

2

  

5

    

9

21101,43

<=

40600

Труд

Высококвалифицированный

18

  

30

  

40

    

220000

<=

220000

Средней квалификации

  

20

  

32

  

48

50

160000

<=

160000

Объемы заключенных 

Договоров

 

 

 

Продукция А

1

1

          

5000

>=

5000

Продукция Б

    

1

1

      

2250

>=

2250

Продукция В

        

1

1

1

5197,143

>=

4000

Прибыль

300

500

350

700

720

1200

1300

7717971

    




                                                                                                                                                                                                      

                                                                                                                                                                                                        Таблица 4. 

Изменяемые ячейки

          
     

Результ.

Нормир.

Целевой

Допустимое

Допустимое

 

Ячейка

Имя

значение

стоимость

Коэффициент

Увеличение

Уменьшение

 

$D$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X1-выпуск прод-ии А 1тех. спос

1257,142857

0

300

4

77,2

 

$E$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X2-выпуск прод-ии А 2тех.сп.

3742,857143

0

500

20

4

 

$F$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X3-выпуск прод-ии Б 1тех.сп.

0

-55,14285714

350

55,14285714

1E+30

 

$G$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X4-выпуск прод-ции Б 2тех.сп.

2250

0

700

132

55,14285714

 

$H$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X5-выпуск прод-ции В 1тех.сп.

4934,285714

0

720

240

8,888888889

 

$I$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X6-выпуск прод-ции В 2тех. Сп.

0

-84,57142857

1200

84,57142857

1E+30

 

$J$8

ЗНАЧЕНИЕ ПЕРЕМЕННЫХ X7-выпуск прод-ции 3тех.сп.

262,8571429

0

1300

10

50

               

Ограничения

          
     

Результ.

Теневая

Ограничение

Допустимое

Допустимое

 

Ячейка

Имя

значение

Цена

Правая часть

Увеличение

Уменьшение

 

$K$10

Новое Объем левой части ограничения

160600

0

160600

1E+30

0

 

$K$10

Новое Объем левой части ограничения

160600

1,142857143

160600

0

13100

 

$K$11

Старое Объем левой части  ограничения

111678,5714

0

400600

1E+30

288921,4286

 

$K$12

Высококачественное Объем левой части ограничения

51857,14286

0

70600

1E+30

18742,85714

 

$K$13

Стандартное Объем левой части ограничения

21101,42857

0

40600

1E+30

19498,57143

 

$K$14

Высококвалифицированный Объем левой  части ограничения

220000

17,14285714

220000

17466,66667

3066,666667

 

$K$15

Средней квалификации Объем левой  части ограничения

160000

26

160000

108325,3968

13142,85714

 

$K$16

Продукция А Объем левой части ограничения

5000

-20

5000

657,1428571

3742,857143

 

$K$17

Продукция Б Объем левой части ограничения

2250

-132

2250

410,7142857

2250

 

$K$18

Продукция В Объем левой части ограничения

5197,142857

0

4000

1197,142857

1E+30


 

                                                                                                                                                                                              Таблица 5. 

Ι. Анализ устойчивости результатов.

Предприятию выгодно выпускать :

Продукцию А 1 технологическим способом 1257,143

Продукцию А 2 технологическим способом   3742,857

Продукцию Б 2 технологическим способом   2250

Продукцию В 1 технологическим способом   4934,285

Продукцию В 3 технологическим способом  262,857

При этом прибыль будет  max и равна 7717971 руб.

ΙΙ. Анализ не выгодной продукции.

Не выгодно выпускать  продукцию Б 1 тех. способом, выпуск единиц продукции снизится на 55,14 тыс.руб., и продукции В 2 тех.способом на 84,571 тыс.руб.

Ресурсы:

Новое оборудование используется полностью, его выгодно увеличивать, при увеличении его на 1 единицу  прибыль увеличится на 1,142 тыс. руб.;

Труд высококвалифицированный  используется полностью, его выгодно  увеличивать, при увеличении его  на 1 единицу прибыль увеличится на 17,14тыс. руб.;

Труд средней квалификации используется полностью, его выгодно  увеличивать, при увеличении его  на 1 единицу прибыль увеличится на 26 тыс. руб.;

Остатки ресурсов каждого  вида:

Оборудования старого: 400600-111678=288922

Сырья высококачественного: 70600-51857=18743

Сырья стандартного: 40600-21101=19499

Договор по третьему виду продукции: 5197-4000=1197.

 

 

 

 

 

Контрольная задача 2

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

      Четыре оптовых склада обслуживают четыре магазина одним товаром.

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

                                                                                 Таблица 1.

Мощности поставщиков

Мощности потребителей

30

20

110

120

60

10

4

5

9

80

10

5

3

5

45

5

9

10

4

95

7

6

4

5


       

   Таблица 2

  

Матрица перевозок(изменяемые ячейки)

60

0

20

40

0

80

0

0

70

10

45

30

0

0

15

95

0

0

0

95

 

30

20

110

120

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

      
 

30

20

110

120

60

10

4

5

9

80

10

5

3

5

45

5

9

10

4

95

7

6

4

5

         

Целевая функция

1225

    

   
   
   
   

Оптимальный план перевозок.

x₁₂=20 единиц груза перевести от 1-го поставщика, 2-му потребителю;

x₁₃=40 единиц груза перевести от 1-го поставщика, 3-му потребителю;

x₂₃=70 единиц груза перевести от 2-го поставщика, 3-му потребителю;

x₂₄=10 единиц груза перевести от 2-го поставщика, 4-му потребителю;

x₃₁=30 единиц груза перевести от 3-го поставщика, 1-му потребителю;

x₃₄=15 единиц груза перевести от 3-го поставщика, 4-му потребителю;

x₄₄=95 единиц груза перевести от 4-го поставщика, 4-му потребителю.

Общая стоимость перевозок 1225.

 

 

 

 


Информация о работе Двойственность в линейном программировании. Анализ оптимального плана по двойственным оценкам основных переменных