Т оптимизация әдістері пәнінен практикум



бет5/40
Дата31.01.2018
өлшемі5,39 Mb.
1   2   3   4   5   6   7   8   9   ...   40

Қорытынды: қойылған есептің тиімді шешімі табылды: аптасына фирма А1 өнімнің 300 бірлігін, ал А2 өнімнің 200 бірлігін дайындау қажет, бұл жағдайда фирма пайдасы максимум 1400 (ш.б) мәніне жетеді.
Өзіндік тапсырмалар

Тапсырма 1

Берілген СП есебін симплекс әдісімен шешу

F=2X1+X2+X4→max

X1+X2+X3+X4=2

X1-X2-X3=0

X1+X2+2X3=1

Xj≥0 (j=1,4)
Тапсырма 2

Берілген СП есебін симплекс әдісімен шешу

F=50X1+40X2→max

2X1+5X2≤20

8X1+5X2≤40

5X1+6X2≤30

Xj≥0 (j=1,2)
Тапсырма 3

Берілген СП есебін симплекс әдісімен шешу

F=3X1-2X2-5Х45→max

2X1+X345≤2

X1-X3+2Х45≤3

2X1+X34+2Х5≤6

Х14-5Х5≥8

Xj≥0 (j=1,5)


Тапсырма 4

Берілген СП есебін симплекс әдісімен шешу

F=-X1+2X234→max

2X1-X234≤6

X1+2X234≥8

3X1-X3-2Х3+2Х4≤10

1+3Х2+5Х3-3Х4=15

Xj≥0 (j=1,4)


Тапсырма 5

Берілген СП есебін симплекс әдісімен шешу

F=2X1-6X2+5Х5→max

-2X1+X235=20

-X1-2X24+3Х5=24

3X1-X2-12Х56=18

Xj≥0 (j=1,6)
Бақылау сұрақтары


  1. Бастапқы тірек жоспары дегеніміз не?

  2. Симплекс кестесінде бағыттаушы бағана қалай анықталады?

  3. Симплекс кестесінде бағыттаушы жол қалай анықталады?

  4. Симплекс әдісімен сызықты программалау есебінің қысқаша шешу алгоритмін анықтаңыз.

  5. Қандай жағдайда симплекс әдісімен сызықты программалау есебінің шешімі болмайды?

  6. Базисты айнымалылар дегеніміз не?

  7. Симплекс кестесінде шешуші элемент қалай анықталады?


Тест тапсырмалары

1.1. Бастапқы симплекс кестеде Базис бағанасы қай элементтермен толтырылады?

A) базисті айнымалылармен;

B) мақсатты функцияда базисті айнымалылардың алдындағы коэффициенттерімен;

C) шектеулердің оң жағында тұратын бос айнымалылармен;

D) мақсатты функцияның барлық айнымалыларымен;

E) бағыттаушы жолды анықтауға пайдаланатын, міндетті емес бағана.

**********


1.2. Бастапқы симплекс кестеде Сб бағанасы қай элементтермен толтырылады?

A) базисті айнымалылармен;

B) мақсатты функцияда базисті айнымалылардың алдындағы коэффициенттерімен;

C) шектеулердің оң жағында тұратын бос айнымалылармен;

D) мақсатты функцияның барлық айнымалыларымен;

E) бағыттаушы жолды анықтауға пайдаланатын, міндетті емес бағана.

**********
1.3. Бастапқы симплекс кестеде В бағанасы қай элементтермен толтырылады?

A) базисті айнымалылармен;

B) мақсатты функцияда базисті айнымалылардың алдындағы коэффициенттерімен;

C) шектеулердің оң жағында тұратын бос айнымалылармен;

D) мақсатты функцияның барлық айнымалыларымен;

E) бағыттаушы жолды анықтауға пайдаланатын, міндетті емес бағана.

**********
1.4. Бастапқы симплекс кестеде Q бағанасы қай элементтермен толтырылады?

A) базисті айнымалылармен;

B) мақсатты функцияда базисті айнымалылардың алдындағы коэффициенттерімен;

C) шектеулердің оң жағында тұратын бос айнымалылармен;

D) мақсатты функцияның барлық айнымалыларымен;

E) бағыттаушы жолды анықтауға пайдаланатын, міндетті емес бағана.

**********
1.5. Бастапқы симплекс кестеде ∆j жолы қалай аталады?

A) айнымалылар жолы;

B) коэффициенттер жолы;

C) бағалар жолы;

D) базисті айнымалылар жолы;

E) міндетті емес жол.

**********


    1. . Негізгі түрде берілген сызықты программалау есебінің бастапқы симплекс кестесін анықтау F=2X1+3X2→max, шарттары:

Х1+3Х23=300

Х124=150

Xj≥0 (j=1,4)

A)


Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х3

0

300

1

3

1

0

Х4

0

150

1

1

0

1

j=zj-cj

0

-2

-3

0

0

B)

Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х1

0

300

1

3

1

0

Х2

0

150

1

1

0

1

j=zj-cj

0

-2

-3

0

0

C)

Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х1

0

150

1

1

0

1

Х2

0

300

1

3

1

0

j=zj-cj

0

-2

-3

0

0

D)

Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х3

300

0

1

3

1

0

Х4

150

0

1

1

0

1

j=zj-cj

0

-2

-3

0

0

E)

Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х3

0

300

1

0

1

3

Х4

0

150

0

1

1

1

j=zj-cj

0

-2

-3

0

0

**********
1.7. Берілген симплекс кестенің бағыттаушы бағанасын анықтау:


Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х3

0

300

1

3

1

0

Х4

0

150

1

1

0

1

j=zj-cj

0

-2

-3

0

0

A) Р2 бағанасы

B) Р1 бағанасы

C) Р3 бағанасы

D) Р3 және Р4 бағаналары

E) Р1 және Р2 бағаналары

**********


1.8. Берілген симплекс кестенің шешуші элементің анықтау:

Базис

Сб

В

2

3

0

0

Р1

Р2

Р3

Р4

Х3

0

300

1

3

1

0

Х4

0

150

1

1

0

1

j=zj-cj

0

-2

-3

0

0

A) 3

B) 1


C) -3

D) -1


E) 0

**********


1.9. Берілген симплекс кестенің шешуші элементің анықтау:

Базис

Сб

В

9

10

16

0

0

0

Р1

Р2

Р3

Р4

Р5

Р6

Х4

0

360

18

15

12

1

0

0

Х5

0

192

6

4

8

0

1

0

Х6

0

180

5

3

3

0

0

1

j=zj-cj

0

-9

-10

-16

0

0

0

A) 16

B) 12


C) 8

D) 3


E) -16

**********




    1. Негізгі түрде жазылған СП есебінің бастапқы тірек жоспарын анықтау. F=2X1+3X2 4→max, шарттары:

12-2Х4 5=16

1+2Х23 -3Х4=18

1+3Х2+4Х46=24

Xj≥0 (j=1,6)

A) Хопор=(18;16;0;0;24;0);

B) Хопор=(0;0;-18;0;-16;-24);

C) Хопор=(0;0;18;0;16;24);

D) Хопор=(18;16;24;0;0;0);

E) Хопор=(24;16;16;0;0;0).

**********


1.11. Берілген СП есебін симплекс әдісімен шешу:

F=2X1+3X2→max, шарттары:

Х1+3Х2=300

Х12=150

Xj≥0 (j=1,2)

A) Хопт=(75; 75);

B) Хопт=(-75; -75);

C) Хопт=(75; 0);

D) Хопт=(0; 75);

E) дұрыс жауабы жоқ

**********
1.12. Берілген СП есебін симплекс әдісімен шешу:

F=2X1+3X2→max, шарттары:

1+4Х2=250

Х12=25

Xj≥0 (j=1,2)

A) Хопт=(25; 0);

B) Хопт=(0; 25);

C) Хопт=(25; 25);

D) Хопт=(-25; -25);

E) дұрыс жауабы жоқ

**********
1.13. Берілген СП есебін симплекс әдісімен шешу:

F=4X1+5X2→max, шарттары:

1+4Х2=100

Х12=200

Xj≥0 (j=1,2)
A) Хопт=(25; 0);

B) Хопт=(0; 50);

C) Хопт=(50; 0);

D) Хопт=(-50; -25);

E) дұрыс жауабы жоқ

**********


1.14. Берілген СП есебін симплекс әдісімен шешу:

F=2X1+2X2→max, шарттары:

1+4Х2=35

Х12=50

Xj≥0 (j=1,2)
A) Хопт=(17,5; 0);

B) Хопт=(0; 17,5);

C) Хопт=(17,5; 17,5);

D) Хопт=(-17,5; 0);

E) дұрыс жауабы жоқ

**********


1.15. Берілген СП есебін симплекс әдісімен шешу:

F=3X1+6X2→max, шарттары:

1+4Х2=40

Х12=100

Xj≥0 (j=1,2)
A) Хопт=(-20; 20);

B) Хопт=(0; 20);

C) Хопт=(20; 0);

D) Хопт=(-20; 0);

E) дұрыс жауабы жоқ

**********


1.16. Берілген СП есебін қосалқы симплекс әдісімен шешу:

F=2X1+3X2→max

3X1+8X2≤240

4X1+5Х2≤200

9X1+4Х2≤360

Xj≥0 (j=1,2)


A) Yопт=(2/17; 7/17; 0);

B) Yопт=(-2/17; 0; 7/17);

C) Yопт=(2/17; -7/17; 0);

D) Yопт=(-2/17; -7/17; 0);

E) дұрыс жауабы жоқ

**********


1.17. Берілген СП есебін қосалқы симплекс әдісімен шешу:

F=2X1+X23→min

X1+X23≥4

X123≥2

Xj≥0 (j=1,3)

A) Yопт=(1; 0);

B) Yопт=(-1; 0);

C) Yопт=(1; 1);

D) Yопт=(0; 0);

E) дұрыс жауабы жоқ

**********
1.18. Берілген СП есебін қосалқы симплекс әдісімен шешу:

F=6X1+9X2+3Х3→min

-X1+2X23≥3

3X123≥1

Xj≥0 (j=1,3)

A) Yопт=(4; 0);

B) Yопт=(-4; 0);

C) Yопт=(4; 1);

D) Yопт=(-4; -1);

E) дұрыс жауабы жоқ

**********
1.19. Берілген СП есебін қосалқы симплекс әдісімен шешу:

F=3X1+X234→max

2X1+X2+4Х3+3Х4≤3

3X12+2Х3+5Х4≤1

Xj≥0 (j=1,4)
A) Yопт=(-6/5; -1/5);

B) Yопт=(6/5; -1/5);

C) Yопт=(6/5; 1/5);

D) Yопт=(-6/5; 1/5);

E) дұрыс жауабы жоқ

**********


1.20. Берілген СП есебін қосалқы симплекс әдісімен шешу:

F=X1-3X2-5Х34→max

X1+4X2+4Х34=5

X1+7Х2+8Х3+2Х4=9

Xj≥0 (j=1,4)

A) Yопт=(-3; 0);

B) Yопт=(-3; 2);

C) Yопт=(-3; -2);

D) Yопт=(3; -2);

E) дұрыс жауабы жоқ

**********

Тақырып 2. Сызықты программалауда қосалқы теориясы.
Негізгі ұғымдар
Сызықты программалау есебінің әрбір есебіне оның қосалқы немесе түйіндес есеп деп аталатын басқа бір есеп сәйкес келеді. Осы есептің алғашқысын бастапқы (тура) есеп деп атайды.

Бастапқы есептің түріне қарай симметриялық, симметриялық емес және аралас қосалқы есептердіажыратады.


Қосалқы есептерді анықтау ережелері:

  1. Симметриялық жұп

Тура есеп

F=c1x1+c2x2+…cnxn→max

a11x1+a12x2+…a1nxn≤b1

a21x1+a22x2+…a2nxn≤b2

am1x1+am2x2+…amnxn≤bm



Xj≥0, j=1,n

Қосалқы есеп

Y=b1y1+b2y2+…bmym→min

a11y1+a12y2+…a1mym≥c1

a21y1+a22y2+…a2mym≥c2

a1ny1+a2ny2+…amnyn≥cm



yj≥0, j=1,m


  1. Симметриялық емес жұп

1 жағдай)

Тура есеп

F=c1x1+c2x2+…cnxn→max

a11x1+a12x2+…a1nxn=b1

a21x1+a22x2+…a2nxn=b2

am1x1+am2x2+…amnxn=bm



Xj≥0, j=1,n

Қосалқы есеп

Y=b1y1+b2y2+…bmym→min

a11y1+a12y2+…a1mym≥c1

a21y1+a22y2+…a2mym≥c2

a1ny1+a2ny2+…amnyn≥cm



yj€R, j=1,m

2 жағдай)



Тура есеп

F=c1x1+c2x2+…cnxn→max

a11x1+a12x2+…a1nxn≤b1

a21x1+a22x2+…a2nxn≤b2

am1x1+am2x2+…amnxn≤bm



Xj€R, j=1,n

Қосалқы есеп

Y=b1y1+b2y2+…bmym→min

a11y1+a12y2+…a1mym=c1

a21y1+a22y2+…a2mym=c2

a1ny1+a2ny2+…amnyn=cm



yj≥0, j=1,m


  1. Аралас жұп

Тура есеп

F=c1x1+c2x2+…cnxn→max

a11x1+a12x2+…a1nxn≤b1

ak1x1+ak2x2+…aknxn≤bk



ak+1,1x1+ak+1,2x2+…ak+1,nxn≤bk+1

am1x1+am2x2+…amnxn=bm



Xj≥0, j=1,p, p≤n

Қосалқы есеп

Y=b1y1+b2y2+…bmym→min

a11y1+a12y2+…a1mym≥c1

a1py1+a2py2+…ampym≥cp



a1p+1y1+a2p+1y2+…amp+1ym≥cp+1

a1ny1+a2ny2+…amnyn≥cm



yj≥0, j=1,k
Есеп 1.

Сызықты программалау есебі берілген.

F=2X1+3X2→max,

3X1+8X2≤240

4X1+5X2≤200

9X1+4X2≤360

X1≥0, X2≥0

Есептің тиімді шешімі белгілі.

Хт=(23,53; 21,18), F=110,6
Шешімі:

Қосалқы есепті анықтаймыз:

Y=240Y1+200Y2+360Y3→min

3Y1+4Y2+9Y3≥2

8Y1+5Y2+4Y3≥3

Yi≥0, i=1,3

Бірінші қосалқы теоремасына сәйкес, Fmax=Ymin=110,6

Екінші қосалқы теоремасын пайдаланамыз: тура есептің тиімді шешімінде Х1 және Х2 айнымалылары теріс емес болғандықтан, қосалқы есептің тиімді шешімінде бірінші және екінші шектеулер теңдіктер ретінде орындалады.

3Y1+4Y2+9Y3=2

8Y1+5Y2+4Y3=3

Хт мәнін тура есептің үшінші шектеуіне енгізіп, яғни 296,49<360, болғандықтан, Y3=0 деп есептейміз.

Сонымен үш теңсіздіктен тұратын жүйені анықтаймыз:

3Y1+4Y2+9Y3=2

8Y1+5Y2+4Y3=3

Y3=0

Жүйенің шешімін іздестіреміз, яғни Yт=(2/17; 7/17; 0)

Қосалқы есептің тиімді шешімі табылды.
Өзіндік тапсырмалар

Тапсырма 1

Сызықты программалау есебі берілген.

F=2X1+X2 +3X3→min

2X1+X2+X3≥5

-X1+X2 -X3≥8

2X1-X2 -2X3≥4

X1≥0, X2≥0, X3≥0

Берілген есепке қосалқы есепті анықтап, тиімді шешімін табу.


Тапсырма 2

Сызықты программалау есебі берілген.

F=X1+7X2 -5X3+3X4→ max

X1+3X2-4X3-5X4=6

X1+X2 -X3 +X4=5

X1≥0, X2≥0, X3≥0, X3≥0

Берілген есепке қосалқы есепті анықтап, тиімді шешімін табу.
Тапсырма 3

Сызықты программалау есебі берілген.

F=2X1+X2 +X3→ min

X1+X2+X3≥4

X1-X2 +X3≥2

X1≥0, X2≥0, X3≥0

Берілген есепке қосалқы есепті анықтап, тиімді шешімін табу.
Тапсырма 4

Сызықты программалау есебі берілген.

F=2X1+X2 +3X3→max

-X1+3X2-5X3=12

2X1-X2 +4X3=24

3X1+X2 +X3=18

X1≥0, X2≥0, X3≥0

Берілген есепке қосалқы есепті анықтау.


Тапсырма 5

Сызықты программалау есебі берілген.

F=4X1+X2 -4X3→max

2X1-X2+4X3≤12

X1+3X2 -2X3=13

2X1+5X2 -6X3≤11

X1≥0, X2≥0, X3≥0

Берілген есепке қосалқы есепті анықтау.


Бақылау сұрақтары

  1. Сызықты программалауда қосалқы мәні неде?

  2. Қосалқы теоремаларын анықтап, дәлелдендер.

  3. Сызықты программалау есептерінің қайсысы симметриялық, қайсысы аралас түрлеріне жатады?

  4. Тура есептің тиімді шешімі белгілі болса, қосалқы есептің тиімді шешімін қалай анықтауға болады?

  5. Қосалқы симплекс әдісінің мәні неде?


Тест тапсырмалары
1.1. Берілген СП есебіне қосалқы есебін анықтау:

F=2X1+3X2→max

3X1+8X2≤240

4X1+5Х2≤200

Xj≥0 (j=1,2)

A) S=240Y1+200Y2→min;

3Y1+4Y2≥2

8Y1+5Y2≥3

Yi≥0, i=1,2

B) S=-240Y1-200Y2→min;

3Y1+4Y2≥2

8Y1+5Y2≥3

Yi≥0, i=1,2

C) S=240Y1+200Y2→min;

-3Y1-4Y2≥2

8Y1+5Y2≥3

Yi≥0, i=1,2

D) S=240Y1+200Y2→min;

3Y1+4Y2≥2

-8Y1-5Y2≥3

Yi≥0, i=1,2

E) S=240Y1+200Y2→min;

-3Y1+4Y2≥2

-8Y1+5Y2≥3

Yi≥0, i=1,2

**********


1.2. Берілген СП есебіне қосалқы есебін анықтау:

F=2X1+X2→max

2X1+X2≤5

-X12≤8

Xj≥0 (j=1,2)

A) S=5Y1+8Y2→min;

2Y1-Y2≥2

Y1+Y2≥1

Yi≥0, i=1,2

B) S=-5Y1-8Y2→min;

2Y1-Y2≥2

Y1+Y2≥1

Yi≥0, i=1,2

C) S=5Y1+8Y2→min;

-2Y1+Y2≥2

Y1+Y2≥1

Yi≥0, i=1,2

D) S=5Y1+8Y2→min;

2Y1-Y2≥2

-Y1-Y2≥1

Yi≥0, i=1,2

E) S=-5Y1+8Y2→min;

-2Y1-Y2≥2

-Y1+Y2≥1

Yi≥0, i=1,2

**********


1.3. Есепті қосалқы симплекс әдісімен шешу:

F=2X1+3X2→max

3X1+8X2≤240

4X1+5Х2≤200

9X1+4Х2≤360

Xj≥0 (j=1,2)

A) Yопт=(2/17; 7/17; 0);

B) Yопт=(-2/17; 0; 7/17);

C) Yопт=(2/17; -7/17; 0);

D) Yопт=(-2/17; -7/17; 0);

E) дұрыс жауабы жоқ

**********


1.4. Есепті қосалқы симплекс әдісімен шешу:

F=2X1+X23→min

X1+X23≥4

X123≥2

Xj≥0 (j=1,3)

A) Yопт=(1; 0);

B) Yопт=(-1; 0);

C) Yопт=(1; 1);

D) Yопт=(0; 0);

E) дұрыс жауабы жоқ

**********
1.5. СП есебі берілген. Қосалқы есептің 1 шарты қандай түрге ие болады?

F=2X1+3X2→max

3X1+8X2≤240

4X1+5Х2≤200

9X1+4Х2≤360

Xj≥0 (j=1,2)

A) 3Y1+4Y2+9Y3≥2;

B) 8Y1+5Y2+4Y3≥3;

C) 240Y1+200Y2+360Y3≥2;

D) 2Y1+3Y2≥3;

E) дұрыс жауабы жоқ

**********


1.6. СП есебі берілген. Қосалқы есептің 2 шарты қандай түрге ие болады?

F=2X1+3X2→max

3X1+8X2≤240

4X1+5Х2≤200

9X1+4Х2≤360

Xj≥0 (j=1,2)

A) 3Y1+4Y2+9Y3≥2;

B) 8Y1+5Y2+4Y3≥3;

C) 240Y1+200Y2+360Y3≥2;

D) 2Y1+3Y2≥3;

E) дұрыс жауабы жоқ

**********

1.7. СП есебі берілген. Қосалқы есептің мақсатты функциясы қандай түрге ие болады?

F=4X1+5X2+6Х3→min

X1+X23≥5

X12+2Х3≥3

X12-4Х3≥-3

X12+8Х3≥4

Xj≥0 (j=1,3)

A) Y1+2Y2-4Y3+8Y4→max;

B) Y1+Y2+Y3+Y4→max;

C) Y1-Y2-Y3-Y4→max;

D) 5Y1+3Y2-3Y3+4Y4→max;

E) дұрыс жауабы жоқ

**********
1.8. Қосалқы есептің тиімді шешімі белгілі: Уопт=(0;4;3), Ymax=44. Тура есептің мақсатты функциясы нешеге тең?

A) Fmin=44;

B) Fmax=44;

C) Fmin=4;

D) Fmin=3;

E) дұрыс жауабы жоқ

**********
1.9. Қосалқы есептің тиімді шешімі белгілі: Уопт=(0;4;3), Ymax=38. Тура есептің мақсатты функциясы нешеге тең?

A) Fmin=0;

B) Fmax=4;

C) Fmin=38;

D) Fmin=3;

E) дұрыс жауабы жоқ

**********
1.10. Қосалқы есептің тиімді шешімі белгілі: Уопт=(0;-4;-3), Ymax=40. Тура есептің мақсатты функциясы нешеге тең?

A) Fmin=0;

B) Fmax=-4;

C) Fmin=40;

D) Fmin=-3;

E) дұрыс жауабы жоқ

**********
1.11. СП есебі берілген. Қосалқы есептің 1 шарты қандай түрге ие болады?

F=X1-X23→max

X1+X23≤4

X12+X3≤2

Xj≥0 (j=1,3)
A) Y1+Y2≥1;

B) Y1-Y2≥-1;

C) Y1+Y2≥-1;

D) 4Y1+2Y2≥1;

E) дұрыс жауабы жоқ

**********


1.12. СП есебі берілген. Қосалқы есептің 2 шарты қандай түрге ие болады?

F=X1-X23→max

X1+X23≤4

X12+X3≤2

Xj≥0 (j=1,3)
A) Y1+Y2≥1;

B) Y1-Y2≥-1;

C) Y1+Y2≥-1;

D) 4Y1+2Y2≥1;

E) дұрыс жауабы жоқ

**********


1.13. СП есебі берілген. Қосалқы есептің 3 шарты қандай түрге ие болады?

F=X1-X23→max

X1+X23≤4

X12+X3≤2

Xj≥0 (j=1,3)
A) Y1+Y2≥1;

B) Y1-Y2≥-1;

C) Y1+Y2≥-1;

D) 4Y1+2Y2≥1;

E) дұрыс жауабы жоқ

**********


1.14. СП есебі берілген. Қосалқы есептің 1 шарты қандай түрге ие болады?

F=6X1+9X2+3Х3→min

-X1+2X23≥3

3X12-X3≥1

Xj≥0 (j=1,3)
A) 2Y1+Y2≤9;

B) -Y1+3Y2≤6;

C) Y1-Y2≤3;

D) 3Y1+Y2≤1;

E) дұрыс жауабы жоқ

**********


1.15. СП есебі берілген. Қосалқы есептің 2 шарты қандай түрге ие болады?

F=6X1+9X2+3Х3→min

-X1+2X23≥3

3X12-X3≥1

Xj≥0 (j=1,3)
A) 2Y1+Y2≤9;

B) -Y1+3Y2≤6;

C) Y1-Y2≤3;

D) 3Y1+Y2≤1;

E) дұрыс жауабы жоқ

**********


1.16. СП есебі берілген. Қосалқы есептің 3 шарты қандай түрге ие болады?

F=6X1+9X2+3Х3→min

-X1+2X23≥3

3X12-X3≥1

Xj≥0 (j=1,3)
A) 2Y1+Y2≤9;

B) -Y1+3Y2≤6;

C) Y1-Y2≤3;

D) 3Y1+Y2≤1;

E) дұрыс жауабы жоқ

**********


1.17. СП есебі берілген. Қосалқы есептің 3 шарты қандай түрге ие болады?

F=4X1+5X2+6Х3→min

X1+X23≥5

X12+2Х3≥3

X12-4Х3≥-3

X12+8Х3≥4

Xj≥0 (j=1,3)
A) Y1+2Y2-4Y3+8Y4≤6;

B) Y1+Y2+Y3+Y4≤4;

C) Y1-Y2-Y3-Y4≤5;

D) 5Y1+3Y2-3Y3+4Y4≤1;

E) дұрыс жауабы жоқ

**********


1.18. СП есебі берілген. Қосалқы есептің 2 шарты қандай түрге ие болады?

F=4X1+5X2+6Х3→min

X1+X23≥5

X12+2Х3≥3

X12-4Х3≥-3

X12+8Х3≥4

Xj≥0 (j=1,3)
A) Y1+2Y2-4Y3+8Y4≤6;

B) Y1+Y2+Y3+Y4≤4;

C) Y1-Y2-Y3-Y4≤5;

D) 5Y1+3Y2-3Y3+4Y4≤1;

E) дұрыс жауабы жоқ

**********


1.19. СП есебі берілген. Қосалқы есептің 1 шарты қандай түрге ие болады?

F=4X1+5X2+6Х3→min

X1+X23≥5

X12+2Х3≥3

X12-4Х3≥-3

X12+8Х3≥4

Xj≥0 (j=1,3)
A) Y1+2Y2-4Y3+8Y4≤6;

B) Y1+Y2+Y3+Y4≤4;

C) Y1-Y2-Y3-Y4≤5;

D) 5Y1+3Y2-3Y3+4Y4≤1;

E) дұрыс жауабы жоқ

**********


1.20. СП есебі берілген. Қосалқы есептің мақсатты функциясы қандай түрге ие болады?

F=4X1+5X2+6Х3→min

X1+X23≥5

X12+2Х3≥3

X12-4Х3≥-3

X12+8Х3≥4

Xj≥0 (j=1,3)
A) Y1+2Y2-4Y3+8Y4→max;

B) Y1+Y2+Y3+Y4→max;

C) Y1-Y2-Y3-Y4→max;

D) 5Y1+3Y2-3Y3+4Y4→max;

E) дұрыс жауабы жоқ

**********



Тақырып 3. Жүк тасымалдау есебі
Негізгі ұғымдар
Жүкті тасымалдау туралы есептің жалпы қойылымы мынадай. Біртектес жүкті жүк жіберуші пункттер А1, А2, ..., Аn мен жүкті қабылдаушы пункттер В1, В2, ..., Вm-ге жеткізудің ең тиімді жоспарын табу қажет. Ең тиімді жоспардың критериі ретінде берлық жүкті тасуға кететін шығынның ең аз болуы немесе барлық жүкті тасуға кететін уақыттың аз болуы. Біз қарастыратын жүк тасымалы туралы есепте ең тиімді жоспардың критериі ретінде барлық жүкті тасуға кететін шығынның барынша аз болуы. Мынадай белгілеулер енгізейік.

Сij – тариф. Жүкті Ai пунктінен Bj пуктіне жеткізуге кететін шығын.

ai – жүктің қоры. Ai пуктінде

bj – жүкке сұраныс. Bj пунктінде

xij – жүк мөлшері. Ai пунктінен Bj пунктіне жеткізетін жүк мөлшері.

Сонда жүк тасымалы туралы есептің математикалық қойылымы мынадай болады:



min (1)

шарттары


(2)

(3)

(4)

Сызықты программалаудың жүк тасымалдау есебі экономиканың әр түрлі құбылыстары мен процестерді зерттеуге және теориялық ізденістерде кеңімен қолданылады. Әсіресе бұл есептер өнеркәсіп және ауыл шаруашылық өнімдерін тасымалдаудың ұтымды жоспарын анықтау үшін жиі қолданылады.

Егер есептің берілуі бойынша барлық жабдықтаушылардағы (тасымалдаушы) жүк қорларының қосындысы мен тұтынушылардың қажеттіліктерінің (сұраныс) қосындысы тең болатын болса, яғни ∑ai=∑bj, онда бұл жүк тасымалдау есебі жабық есеп деп аталады. Егер ∑ai≠∑bj, онда жүк тасымалдау есебі ашық деп аталады.

Егер ∑ai>∑bj, онда жалған тұтынушы енгізу арқылы ашық жүк тасымалдау есебінен өтуге болады, бұл кезде осы барлық жабдықтаушыдан жасанды тұтынушыға апаратын жүктердің 1 данасына кететін шығын, яғни cn+1j=0 және керісінше.

Егер ∑ai<∑bj, онда жасанды жабдықтау пайда болады, ол тұтынушы жүгінің көлемі am+1=∑bj-∑ai

Жүк тасымалдау жоспары келесі талаптарға сай болу тиіс:



  • тарату пунктерінен жүкті толығымен тасымалдау

  • әрбір тұтынушының қажеттілігі орындалуы тиіс

  • жүк тасымалдауға кететін шығындар минималды болу тиіс


Жүк тасымалы туралы есептің тірек жоспарын анықтау
Сызықты программалау есебінің симплекс әдісімен ең тиімді жоспарын іздегендей жүк тасымалы туралы есептің ең тиімді жоспарын табу үшін әуелі оның тірек жоспарын анықтау қажет. Ол үшін жоғарыда айтқандай солтүстік-батыс бұрыш әдісі, ең кіші элементтер әдісі немесе Фогел әдісі қолданылады. Бұл әдістердің неізгі идеясы мынада: тірек жоспары n+m- 1 қадам жаслғаннан кейін табады. Және әрбір қадам сайын есептің шарты жазылған кестенің бір торы ғана толтырылады. Оны бос емес тор деп атайды. Бір торды толтырудың нәтижесінде жүк қабылдаушы бір пункттің қоры толғанымен тасылып әкелінеді.

Бірінші жағдайда толтырылған торы бағананы әрі қарай қарастырмайды. Нәтижесінде есептің шарты жазылған кестеде бір бағананың саны кемиді, бірақ жолдардың саны өзгеріссіз қалады, соның нәтижесінде жіберуші пунттің біреуінде жүктің қоры өзгереді. Екінші жағдайда толтырылған кесте орналасқан бір жолды әрі қарай қарастырмайды, нәтижесінде есептің шарты жазылған кетенің жолдарының саны бірге азаяды да, бағаны өзгермейді.

Осылайша n+m- 2 қадам жасалғаннан кейін шыққан есепте бір ғана жүк қабылдаушы болады. Ал толтырылған тордың саны да біреу ғана болады. Толтырылған бір тордың n+m-1 қадам жасап толтырылғаннан кейін жүк тасымалы туралы есептің тірек жоспары табылады. Қабылдаушы пукттің қажеттілігі, жіберуші пункттің қорына тең болуы мүмкін. Осы жағдайда жолды немесе бағананы уақытша қарстырмаймыз (екеуінің біреуін). Осыған сәйкес жіберуші пунктің қоры немесе берілген қабылдаушы пункттің қажеттіліктері нолге тең деп санауға болады. Осы нолді кезкекті толтырып жатқан торға жазады. Жоғарыда көрсетілген шарттар тірек жоспарының компоненттері тұратын n+m- 1 бос емес торын табуға кепілдеме береді. Тиімді жоспарын табу және соңғысының тиімділігін тексеру бастапқы шарты болып табылады.



А.байтұрсынов атындағы қостанай мемлекеттік университеті
Сотүстік батыс бұрыш әдісі.
Ms excel көмегімен шешу.
Сызықты программалау есептерін

Каталог: files
files -> Бастауыш білім беру деңгейінің ОҚу пәндері бойынша үлгілік тақырыптық жоспарлары
files -> Астрономия Мазмұны
files -> Қазақстан тарихы 5 сынып. 2013-2014 оқу жылы
files -> Расул гамзатов
files -> Жамбыл атындағы республикалық жасөспірімдер кітапханасы Қазақстан ақын – жазушылары ХХ ғасырда
files -> «№ мектеп-лицей» мемлекеттік мекемесі Күнтізбелік- тақырыптық жоспар
files -> Ермұхан Бекмахановқа Сыздайды жаным, мұздайды қаным, жан аға!
files -> Жамбыл атындағы республикалық жасөспірімдер кітапханасы Қазақстан ақын – жазушылары ХХ ғасырда
files -> Қазақстан Республикасы Білім және ғылым министрлігі, жергілікті атқарушы органдар көрсететін білім және ғылым саласындағы мемлекеттік қызмет стандарттарын бекіту туралы


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   40


©engime.org 2017
әкімшілігінің қараңыз

енгізу | тіркеу
    Басты бет


материалдарды жүктеу