Решение задач методом потенциалов и симплексным методом

Автор работы: Пользователь скрыл имя, 10 Ноября 2013 в 12:40, контрольная работа

Описание работы

Задача 2

1. Возможности поставщиков, т:
1бригада = 320+10*8= 400
2 бригада = 260+20*8= 420
3 бригада = 1500-30*8= 1260
4 бригада = 700+5*8= 740
= 2820

Скачать архив (22.72 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

НАТАША 1.doc

— 155.00 Кб (Скачать файл)

Министерство  сельского хозяйства и продовольствия Республики Беларусь

Учреждение  образования

Белорусский  государственный  аграрный  технический  университет

Факультет  предпринимательства  и  управления

(заочное   отделение)

 

 

 

Контрольная  работа

 

 

 

По  курсу:  "Методы  оптимизации"

На  тему:  "Решение задач методом потенциалов и симплексным методом".

 

 

 

 

 

 

Выполнил: студентка  IV  курса

6 зэи группы

Карнилович  Т.В.

Проверил  ________________

 

 

 

 

 

Вариант 6     N=8

Задача 2

 

1. Возможности поставщиков,  т:

1бригада = 320+10*8= 400

2 бригада = 260+20*8= 420  

3 бригада = 1500-30*8= 1260

4 бригада = 700+5*8= 740

= 2820

2. Потребности потребителей, т:

1.   710+15*8= 830

2.   520+40*8= 840  

3.   500+10*8= 580

  1. 1100-20*8= 940

= 3190

 

Поскольку наличие ресурсов не равны потребностям  (2.820<3.190), задача является открытой.  Приведем задачу к закрытой.

5ф= 3190-2820= 370

всего поставщиков   -  4 i = 1…4

потребителей  -  5 j = 1…5

 

Цель - минимум затрат на перевозку    Fmin= Σ Σ  Cij Xij

                                      jÎJ     iÎI

 

 

V1

V2

V3

V4

  

U1

8

400

5

8

10,4

400

U2

10

420

6

9

5,4

420

U3

9

10

6,4

840

8,6

410

6

1260

U4

12,4

7

6

170

8

570

740

U5

0

0

0

0

370

370

 

830

840

580

940

  

 

Построили опорный план методом  северо-западного угла. Число загруженных клеток соответсвует равенству r = m+n-1 = 5+4-1= 8.

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

 

U1+V1=8     U1= 0


U2+V1=10     U2= 2

U3+V1=9     U3= 1

U3+V2=6,4  U1=0   U4= -1,6

U3+V3=8,6     U5= -9,6

U4+V3=6     V1= 8

U4+V4=8     V2= 5,4

U5+V4=0     V3= 7,6

V4= 9,6

Определяем  оценки свободных клеток по формуле Δks=Cks-(Uk+Vs). Если среди оценок есть отрицательная, значит план не является оптимальным.

Δ41= 6

Δ22= -1,4

Δ13= 15,6

Δ14= 0,4

Δ51= 1,6

Δ42= 3,2

Δ23= -0,6

Δ24= -6,2

Δ12= -1,4

Δ52= 4,2

Δ53= 2

Δ34= -4,6


 

Поскольку в  результатах содержатся отрицательные  числа (max= -6,2), то загружаем эту клетку.

 

 

V1

V2

V3

V4

  

U1

8

300

5

100

8

10,4

400

U2

10

 

6

9

5,4

420

420

U3

9

 

6,4

740

8,6

6

520

1260

U4

12,4

530

7

6

210

8

740

U5

0

0

0

370

0

370

 

830

840

580

940

  

 

     Число загруженных клеток соответсвует равенству r =m+n-1 = 5+4-1= 8.


U1+V1= 8     U1= 0

U4+V1= 12,4    U2= 0,8

U1+V2= 5     U3= 1,4

U3+V2= 6,4  U1=0   U4= 4,4

U4+V3= 6     U5= -1,6

U5+V3= 0     V1= 8

U2+V4= 5,4     V2= 5

U3+V4= 6     V3= 1,6

V4= 4,6

Δ21= 1,2

Δ22= 0,2

Δ13= 6,4

Δ14= 5,8

Δ31= -0,4

Δ42= -2,4

Δ23= 6,6

Δ44= -1

Δ51= -6,4

Δ52= -3,4

Δ33= 5,6

Δ54= -3


 

План не оптимальный (проблемная клетка 51). Получаем новый  опорный план:

 

 

V1

V2

V3

V4

  

U1

8

300

5

100

8

10,4

400

U2

10

 

6

9

5,4

420

420

U3

9

 

6,4

740

8,6

6

520

1260

U4

12,4

160

7

6

580

8

740

U5

0

370

0

0

0

370

 

830

840

580

940

  

 

     Число загруженных клеток соответсвует равенству r =m+n-1 = 5+4-1= 8.


U1+V1= 8     U1= 0

U4+V1= 12,4    U2= 0,8

U1+V2= 5     U3= 1,4

U3+V2= 6,4  U1=0   U4= 4,4

U4+V3= 6     U5= -8

U5+V1= 0     V1= 8

U2+V4= 5,4     V2= 5

U3+V4= 6     V3= 1,6

V4= 4,6

 

Δ21= 1,2

Δ22= 0,2

Δ13= 6,4

Δ14= 5,8

Δ31= -0,4

Δ42= -2,4

Δ23= 6,6

Δ44= -1

Δ53= 6,4

Δ52= 3

Δ33= 5,6

Δ54= 3,4


 

План не оптимальный (проблемная клетка 42). Получаем новый  опорный план:

 

 

 

 

 

V1

V2

V3

V4

  

U1

8

5

400

8

10,4

400

U2

10

 

6

9

5,4

420

420

U3

9

460

6,4

280

8,6

6

520

1260

U4

12,4

7

160

6

580

8

740

U5

0

370

0

0

0

370

 

830

840

580

940

  

 

     Число загруженных клеток соответсвует равенству r =m+n-1 = 5+4-1= 8.


U3+V1= 9     U1= -1,4

U5+V1= 0     U2= -0,6

U1+V2= 5     U3= 0

U3+V2= 6,4  U3=0   U4= 0,6

U4+V2= 7     U5= -9

U4+V3= 6     V1= 9

U2+V4= 5,4     V2= 6,4

U3+V4= 6     V3= 5,4

V4= 6

 

Δ11= 0,4

Δ22= 0,2

Δ23= 4,2

Δ14= 5,8

Δ21= 1,6

Δ52= 2,6

Δ33= 3,2

Δ44= 1,4

Δ41= 2,8

Δ1,3= 4

Δ53= 3,6

Δ54= 3


 

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

 

Fmin= 9*460+0*370+5*400+6,4*280+7*160+6*580+5,4*420+6*520 = 17 920           

 

 

 

 

 

 

 

Задача 3

 

  1. Содержание к.ед. в рационе составит не меньше минимума:

1,16Х1+0,48Х2+0,22Х3≥(36+0,2*8)≥37,6

2. Содержание переваримого протеина  в рационе составит не меньше  минимума:

0,12Х1+0,05Х2+0,02Х3≥(3,5+0,05*8)≥3,9

    1. По весу концентратов — верхняя граница:

Х1≤(14-0,2*8) ≤12,4

    1. По весу сена  —  нижняя  граница:

Х2≥(6+0,3*8) ≥8,4

    1. По весу сена  —  верхняя  граница:

Х2≤(22+0,3*8)≤24,4

    1. По весу зеленого корма  —  верхняя  граница:

Х3≤(50+1*8)≤58

Стоимость рациона минимальная:  Fmin=11,4X1+4,2X2+1,1X3

Система неравенства  задачи имеет вид:

    1. 1,16Х1+0,48Х2+0,22Х3≥37,6
    2. 0,12Х1+0,05Х2+0,02Х3≥3,9
    3. Х1≤12,4
    4. Х2≥8,4 5)Х2≤24,4

6)  Х3≤58

Приводим все ограничения  к типу меньше-равно (≤):

    1. -1,16Х1-0,48Х2-0,22Х3≤-37,6
    2. -0,12Х1-0,05Х2-0,02Х3≤-3,9
    3. Х1≤12,4
    4. -Х2≤-8,4 5)Х2≤24,4

6)  Х3≤58

Fmin=11,4X1+4,2X2+1,1X3

 

Приводим все ограничения  к типу меньше-равно (≤):

    1. -1,16Х1-0,48Х2-0,22Х3+У1≤-37,6
    2. -0,12Х1-0,05Х2-0,02Х3+У2≤-3,9
    3. Х1+У3≤12,4
    4. -Х2+У4≤-8,4  5)Х2+У5≤24,4

6)  Х3+У6≤58

 

Fmin=11,4X1+4,2X2+1,1X3

 

 

 

Исходная  симплексная таблица

Базисные переменные

λj

Свободные члены

bi

Небазисные

Единичный баланс

Х1

Х2

Х3

У1

У2

У3

У4

У5

У6

У1

-37,6

-1,16

-0,48

-0,22

1

          

У2

-3,9

-0,12

-0,05

-0,02

  

1

        

У3

12,4

1

        

1

      

У4

-8,4

  

-1

        

1

    

У5

24,4

  

1

          

1

  

У6

58

    

1

          

1

F

0

-11,4

-4,2

-1,1

0

0

0

0

0

0


 

Определяем разрешающий  элемент:

-37,6/-0,48=78,3 -3,9/-0,05=78 -8,4/-1=8,4 24,4/1=24,4

  1. Базисная переменная У4 заменит небазисную Х2.
  2. Новый коэффициент определяем по формуле  ark=1/ark
  3. Новые коэффициенты строки разрешающего элемента равны предыдущим, деленным на разрешающий  arj=arj/ark
  4. Новые коэффициенты столбца разрешающего элемента равны предыдущим, деленным на разрешающий элемент с противоположным знаком aik=- aik/ark
  5. Новые коэффициенты не стоящие в строке и столбце разрешающего элемента равны частному от деления разности произведения коэффициентов в главной и побочной диагонали на разрешающий элемент

 

aij=

aij*ark - aik*arj

  

       ark

  

  1. Аналогично определяем новый коэффициент вместо аF0=0

 

 

Симплексная таблица  1

Базисные переменные

λj

Свободные члены

bi

Небазисные

Х1

У4

Х3

У1

-33,568

-1,16

-0,48

-0,22

У2

-3,48

-0,12

-0,05

-0,02

У3

12,4

1

    

Х2

8,4

  

-1

  

У5

16

  

1

  

У6

58

    

1

F

35,28

-11,4

-4,2

-1,1


 

В таблице 1 опорное решение  отсутствует, так как два свободных  члена — отрицательные. Продолжаем решение дальше до получения опорного и далее оптимального решения.

Чтобы быстрее решить задачу можно воспользоваться программой Excell. Обработаем данные с помощью функции "поиск решения" установив к чему будет стремиться функция и ограничения. Далее нажимаем кнопку "выполнить"

Информация о работе Решение задач методом потенциалов и симплексным методом