Тусдаа слайд дээрх үзүүлэнгийн тайлбар:
1 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол ПетрСУ, А.П.Мощевикин, 2004 Шугаман програмчлал Энэ ангид шугаман програмчлал(Америкчуудын шийддэг бодлогын 75%) зорилтын функц Wm(x), m=1,2,...,M, hk(x)=0, k=1, тэгш байдлын хэлбэрийн хязгаарлалтууд, 2... K ба gj(x)>0, j=1,2,...J, тэгш бус байдал нь шугаман ба математикийн шийдэл. LP-ийн даалгаврын боломжит сэдвүүд: түүхий эд, материалыг зохистой ашиглах; оновчлолын ажлыг багасгах; аж ахуйн нэгжүүдийн үйлдвэрлэлийн хөтөлбөрийг оновчтой болгох; үйлдвэрлэлийн оновчтой байршил, төвлөрөл; тээвэрлэлт, тээврийн үйл ажиллагааны оновчтой төлөвлөгөө гаргах; Бараа материалын менежмент; оновчтой төлөвлөлтийн салбарт хамаарах бусад олон. LP асуудлыг тавих (гүйцэтгэлийн үзүүлэлт, даалгаврын хувьсагчдыг тодорхойлох, шугаман зорилгын функцийг W(x)-ийг багасгах буюу нэмэгдүүлэх, функциональ hk(x), gj(x) болон бүсийн xli 2 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол ПетрСУ, А.П.Мощевикин, 2004 LP асуудлын жишээ Жишээ - Ойн аж ахуйн хажуугийн үйлдвэрлэлийн байршлыг оновчтой болгох Ойн аж ахуй нь уриншгүй 24 га талбайтай бөгөөд үүнээс орлого олох сонирхолтой байдаг. Энэ нь хурдан ургадаг эрлийз гацуур модны суулгацыг нэг жилийн дотор боловсорч гүйцдэг, эсвэл говь, газрын зарим хэсгийг бэлчээрт шилжүүлж болно. Модыг ургуулж, 1000 ширхэгээр зардаг. Нэг хэсэг мод ургуулахын тулд 1.5 га, нэг бухыг тэжээхэд 4 га талбай шаардлагатай. Ойн тойрог жилд 200 гаруй цагийг хажуугийн үйлдвэрлэлдээ зарцуулдаг. Дадлагаас харахад нэг хэсэг модыг ургуулж, огтолж, огтолж, бооход 20 цаг зарцуулдаг. Мөн нэг бухыг арчлахад 20 цаг зарцуулдаг.Үүнд зориулж 6 мянган рубль зарцуулах боломж ойн аж ахуйд бий. Нэг багц модны жилийн зардал нь 150 рубль болдог. ба 1.2 мянган рубль. нэг бухын төлөө. 2 бух нийлүүлэхээр гэрээ байгуулчихсан байгаа. Одоогийн үнээр нэг гацуур мод 2.5 рубль, нэг бух 5 мянган рублийн ашиг авчрах болно. 3 слайд
Слайдын тайлбар:
PetrSU-ийн шийдвэр гаргах онол, A.P.Moshchevikin, 2004 Асуудлын мэдэгдэл 1. Үр ашгийн үзүүлэлтийн хувьд нэг үйл ажиллагааны ашгийг (газрын жилийн ашгийг рубльээр) авах нь зүйтэй. 2. Асуудлын хяналттай хувьсагчаар дараахь зүйлийг авна: x1 - жилд таргалсан бухын тоо; x2 - хурдан ургадаг гацуур модны ургасан багцын тоо, 1000 ширхэг. жил бүр. 3. Зорилтот функц: 5000 x1 + 2500 x2 max, энд 5000 нь нэг бухын цэвэр орлого, руб.; 2500 - нэг багц модны цэвэр орлого (2.5 рубльд 1000 ширхэг). 4. Хязгаарлалт: 4.1. Газар ашиглалтаар га: 4 х1 + 1,5 х2 24 4.2. Төсвийн дагуу рубль: 1200 x1 + 150 x2 6000 4.3. Хөдөлмөрийн нөөцөөр h: 20 x1 + 20 x2 200 4.4. Гэрээгээр хүлээсэн үүрэг, ширхэг: x1 2 4.5. Талбайн хязгаар: x1 0, x2 0 4 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол ПетрСУ, А.П.Мощевикин, 2004 LP бодлогын график шийдэл Дараах тэгшитгэлд харгалзах шугамуудыг график дээр харуулах 4 x1 + 1.5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 2 x2 = 0 бид бүх хязгаарлалтыг хангасан цэгүүдийг сүүдэрлэдэг. Ийм цэг бүрийг зөвшөөрөгдөх шийдэл гэж нэрлэдэг бөгөөд бүх зөвшөөрөгдөх шийдлүүдийн багцыг зөвшөөрөгдөх бүс гэж нэрлэдэг. Мэдээжийн хэрэг, LP-ийн асуудлын шийдэл нь зөвшөөрөгдөх бүсэд хамгийн сайн шийдлийг олохоос бүрддэг бөгөөд үүнийг эргээд оновчтой гэж нэрлэдэг. Энэ жишээнд W=5000 x1 + 2500 x2 функцийг хамгийн их байлгах боломжтой шийдэл нь оновчтой шийдэл юм. Оновчтой шийдэлд харгалзах зорилгын функцийн утгыг LP асуудлын оновчтой утга гэнэ. 5 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол ПетрСУ, А.П.Мощевикин, 2004 LP асуудлын график шийдэл 6 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол ПетрСУ, A.P. Мощевикин, 2004 LP асуудлын график шийдэл Боломжит шийдлүүдийн талбайн бүх булангийн цэгүүдийг тоолох нь 34 мянган рублийн хамгийн их орлогыг олоход хүргэдэг. (W=5000x1+2500x2) ойн аж ахуй нь 3.6 азарга, 6.4 багц гацуур мод ургуулах замаар олборлох боломжтой. Бүхэл тоон аргууд (жишээ нь, тоолох) x1=3 ба x2=6-г өгдөг бөгөөд энэ нь 30 мянган рублийн орлого, x1=4 ба x2=5 нь 32.5 мянган рублийн илүү оновчтой үр дүнд хүргэдэг, x1 =3 цэг ба x2=7 нь ижил төстэй үр дүнд хүргэдэг. Бодит практик LP асуудлуудын том хэмжээтэй тул график аргыг бараг ашигладаггүй боловч энэ нь LP-ийн үндсэн шинж чанаруудын нэгийг тодорхой ойлгох боломжийг олгодог - хэрэв LP асуудалд оновчтой шийдэл байгаа бол дор хаяж нэгийг нь ойлгох боломжийг олгодог. Зөвшөөрөгдөх бүсийн оройнууд нь оновчтой шийдэл юм. LP асуудлын зөвшөөрөгдөх талбар нь хязгааргүй тооны цэгээс бүрддэг хэдий ч түүний төгсгөлийн тооны оройг зориудаар тоолох замаар оновчтой шийдлийг үргэлж олох боломжтой. Доор авч үзсэн LP асуудлыг шийдэх симплекс арга нь энэхүү үндсэн шинж чанарт суурилдаг. 7 слайд
Слайдын тайлбар:
PetrSU-ийн шийдвэр гаргах онол, A.P.Moshchevikin, 2004 MS Excel дээр LP асуудлыг шийдвэрлэх нь MS Excel хүснэгт засварлагчийн суулгасан функцүүдийн нэг (MS Office програмыг суулгах явцад хайрцгийг шалгах шаардлагатай) нь "Шийдэл хайх" юм. . Энэхүү багц нь шугаман болон шугаман бус програмчлалын асуудлыг хурдан шийдвэрлэх боломжийг олгоно. 8 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол ПетрСУ, А.П.Мощевикин, 2004 Стандарт хэлбэрийн LP бодлого m хязгаарлалт ба n хувьсагчтай стандарт хэлбэрийн LP бодлого нь дараах хэлбэртэй байна: W = c1x1 + c2x2 + ... + cnxn min (max) дор хязгаарлалт a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 Матриц хэлбэрээр W = cx min (max) хязгаарлалтын үед Ax = b; x0; b0, энд A нь m*n хэмжээсийн матриц, x нь n*1 хэмжигдэхүүнтэй хувьсагчдын баганын вектор, b нь m*1 хэмжээсийн нөөцийн баганын вектор, с нь тооцооллын эгнээний вектор юм. LP асуудал 1*n. 9 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол PetrSU, A.P.Moshchevikin, 2004 Тэгш бус байдлын хувиргалт Тэгш бус байдлын хязгаарлалтыг үлдэгдэл эсвэл илүүдэл хэмжигдэхүүн гэж нэрлэгдэх замаар тэгш байдал болгон хувиргаж болно. Өмнөх жишээний 4x1 + 1.5x2 24-ийн тэгшитгэлийг сөрөг бус үлдэгдэл хувьсагч 4x1 + 1.5x2 + x3 = 24 ашиглан тэгшитгэл болгон хувиргаж болно. x3 хувьсагч нь сөрөг биш бөгөөд баруун болон зүүн талын зөрүүтэй тохирч байна. тэгш бус байдлын талууд. Үүний нэгэн адил x1 2-г илүүдмэл хувьсагч x4 оруулах замаар хувиргаж болно: x1 - x4 = 2. 10 слайд
Слайдын тайлбар:
Петр СУИС-ийн шийдвэр гаргах онол, А.П.Мощевикин, 2004 он. Хувьсагчийн тэмдгээр Тэмдгээр хязгаарлагдахгүй хувьсах хэмжигдэхүүнийг хувиргах эерэг ба сөрөг утгыг хоёуланг нь авдаг хувьсагчдыг хоёр сөрөг бус утгын зөрүүгээр солих ёстой: x = x+ - x-; x+0; x- 0. Жишээ. 3x1+4x2+5x3+4x4 max 2x1+x2+3x3+5x4 5 5x1+3x2+x3+2x4 20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 = тэмдэг -3x1-4x2+5x3-4x4 min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 = тэмдэг; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8 -x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 мин 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x = 15 x1,x2,x3,x4,x5,x6,x70; x8-г x4-ээр сольсон 11 слайд
Слайдын тайлбар:
ПетрСУ-ийн шийдвэр гаргах онол, А.П.Мощевикин, 2004 Simplex LP арга Симплекс арга нь стандарт хэлбэрээр бичигдсэн LP бодлогуудыг шийдвэрлэх давтагдах процедур бөгөөд матрицууд дээр энгийн үйлдлүүдийн тусламжтайгаар каноник хэлбэрт шилжүүлдэг тэгшитгэлийн систем юм. хэлбэр: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Системийн зөвхөн нэг тэгшитгэлд нэгж коэффициенттэй, үлдсэн хэсэгт нь тэг коэффициенттэй орох x1, x2,...,xm хувьсагчдыг үндсэн гэнэ. Каноник системд тэгшитгэл бүр яг нэг үндсэн хувьсагчтай тохирч байна. Үлдсэн n-m хувьсагчдыг (xm+1, ...,xn) үндсэн бус хувьсагчид гэнэ. Системийг каноник хэлбэрт оруулахын тулд мөр дээрх хоёр төрлийн энгийн үйлдлийг ашиглаж болно: Системийн аливаа тэгшитгэлийг эерэг эсвэл сөрөг тоогоор үржүүлэх. Системийн өөр тэгшитгэлийг дурын тэгшитгэлд нэмэх, эерэг эсвэл сөрөг тоогоор үржүүлнэ. 12 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол PetrSU, A.P. Moshchevikin, 2004 Simplex-method LP Асуудлыг x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1 тэгшитгэлийн хэлбэрээр бүртгэх; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 матрицаар адилхан бичигдэнэ. . ... . ... ... .. .. 0 0 .. 1 цаг,м+1 .. амс .. amn xn bm 13 слайд
Слайдын тайлбар:
PetrSU-ийн шийдвэр гаргах онол, А.П.Мощевикин, 2004 Энгийн аргачлалын алгоритм 1. Анхны зөвшөөрөгдөх үндсэн шийдлийг сонгоно уу. Суурь шийдэл нь үндсэн бус хувьсагчдын тэг утгыг ашиглан олж авсан шийдэл юм. xi=0, i=m+1,...,n. Үндсэн шийдэлд багтсан үндсэн хувьсагчдын утгууд сөрөг биш байвал үүнийг зөвшөөрөгдөх үндсэн шийдэл гэж нэрлэдэг. xj = bj 0, j=1,2,...,m. Энэ тохиолдолд зорилгын функц дараах хэлбэрийг авна: W=cbxb=c1b1+c2b2+...+cmbm. Бид симплекс аргын эхний хүснэгтийг бөглөнө. 14 слайд
Слайдын тайлбар:
PetrSU-ийн шийдвэр гаргах онол, A.P.Moshchevikin, 2004 Simplex аргын алгоритм 2. Цэг үржвэрийн дүрмийг cj = cj - cbSj ашиглан харьцангуй тооцооллын векторыг тооцоолох, энд cb нь үндсэн хувьсагчдын тооцооллын вектор; Sj нь авч үзсэн үндэслэлд тохирох каноник систем дэх aij коэффициентүүдийн j-р багана юм. Бид эхний хүснэгтийг c - шугамаар нэмж оруулав. 15 слайд
Слайдын тайлбар:
Шийдвэр гаргах онол PetrSU, A.P. Moshchevikin, 2004 Simplex аргын алгоритм ). Шийдэл олдлоо. 4. Үгүй бол аль нэг үндсэн хувьсагчийн оронд суурьт хамгийн том cj утгатай үндсэн бус xr хувьсагчийг оруулах шаардлагатай (хүснэгтийг үзнэ үү). 16 слайд
Слайдын тайлбар:
PetrSU-ийн шийдвэр гаргах онол, A.P.Moshchevikin, 2004 Simplex аргын алгоритм 5. Минимум харьцаа min(bi/air)-ын дүрмийг ашиглан бид үндэслэлээс гаргаж авсан xp хувьсагчийг тодорхойлно. Хэрэв агаарын коэффициент сөрөг байвал bi/air=. Үүний үр дүнд xr оролтын үндсэн бус хувьсагчийг агуулсан баганын огтлолцол, xp гаралтын үндсэн хувьсагчийг агуулсан мөр нь хүснэгтийн тэргүүлэх элементийн байрлалыг тодорхойлно. 6. Бид шинэ хүлээн зөвшөөрөгдөх суурь шийдэл, шинэ хүснэгтийг олж авахын тулд энгийн хувиргалтуудыг ашигладаг. Үүний үр дүнд эргэлтийн элемент нь 1-тэй тэнцүү байх ёстой бөгөөд тэнхлэгийн баганын үлдсэн элементүүдийг тэг болгон тохируулах ёстой. 7. Скаляр хувиргах дүрмийг ашиглан харьцангуй шинэ оноог тооцоод 4-р алхам руу шилжинэ. 17 слайд
Слайдын тайлбар:
PetrSU-ийн шийдвэр гаргах онол, A.P.Moshchevikin, 2004 Симплекс аргын шийдлийн жишээ Жишээ - Ойн аж ахуйн хажуугийн үйлдвэрлэлийн байршлыг оновчтой болгох 3. Зорилтот функц: 5000 x1 + 2500 x2 max, 4. Хязгаарлалт: 4.1. Газар ашиглалтаар га: 4 х1 + 1,5 х2 24 4.2. Төсвийн дагуу рубль: 1200 x1 + 150 x2 6000 4.3. Хөдөлмөрийн нөөцөөр h: 20 x1 + 20 x2 200 4.4. Гэрээгээр хүлээсэн үүрэг, ширхэг: x1 2 4.5. Бүс нутгийн хязгаарлалт: x1 0, x2 0 Асуудлыг стандарт хэлбэрт оруулъя: 4 x1 + 1.5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6 0 Эхний гурван тэгшитгэл нь үндсэн хувьсагчдаа тус тус x3, x4, x5-тай, харин дөрөв дэх нь x6 хувьсагч сөрөг нэгж коэффициенттэй тул байхгүй байна. Системийг каноник хэлбэрт оруулахын тулд бид хиймэл хувьсагчийн аргыг ашигладаг. x1 – x6+x7= 2, x7 хиймэл хувьсагчийг нэвтрүүлсэн. слайд 2 Шугаман програмчлалын аргыг урьдчилан таамаглах тооцоолол, үйлдвэрлэлийн үйл явцыг төлөвлөх, зохион байгуулахад ашигладаг. Шугаман програмчлал нь аргументууд нь шугаман хязгаарлалттай байдаг зарим шугаман функцийн хэт утгыг судлах, олох аргуудыг судалдаг математикийн салбар юм. слайд 3 Ийм шугаман функцийг зорилтот функц гэж нэрлэдэг ба эдийн засгийн асуудлын тодорхой шаардлагыг тэгшитгэл буюу тэгш бус байдлын хэлбэрээр илэрхийлдэг хувьсагчдын хоорондын тоон харилцааны багцыг хязгаарлалтын систем гэж нэрлэдэг. Үл мэдэгдэх хувьсагч нь ихэвчлэн ямар нэг хичээлийн хөтөлбөр эсвэл ажлын төлөвлөгөөг тодорхойлдог тул програмчлал гэдэг үгийг нэвтрүүлсэн. слайд 4 Зорилгын функц, түүний аргументуудын хязгаарлалтыг агуулсан харилцааны багцыг оновчлолын асуудлын математик загвар гэж нэрлэдэг. ZLP нь ерөнхий хэлбэрээр дараах байдлаар бичигдсэн: хязгаарлалт дор слайд 5 Энд - үл мэдэгдэх, - өгөгдсөн тогтмолууд.Хязгаарлалтуудыг тэгшитгэлээр өгч болно. Хамгийн нийтлэг даалгавар нь хэлбэрээр байдаг: хязгаарлалттай нөөцүүд байдаг. Зорилгын функц нь дээд тал нь (хамгийн бага) хүрэх эдгээр нөөцийн хэмжээг тодорхойлох, өөрөөр хэлбэл хязгаарлагдмал нөөцийн оновчтой хуваарилалтыг олох шаардлагатай. Энэ тохиолдолд байгалийн хязгаарлалтууд >0 байна. слайд 6 Энэ тохиолдолд зорилгын функцийн экстремумыг хязгаарлалтын системээр тодорхойлсон шийдлийн зөвшөөрөгдөх багцаас хайж олох ба хязгаарлалтын систем дэх бүх буюу зарим тэгш бус байдлыг тэгшитгэл хэлбэрээр бичиж болно. Слайд 7 Товчхондоо, ХХК нь хязгаарлалттай гэсэн хэлбэртэй байна Слайд 8 ZLP-ийн математик загварыг бүрдүүлэхийн тулд дараахь зүйлийг хийх шаардлагатай: 1) хувьсагчдыг тодорхойлох; 2) зорилгын функцийг бүрдүүлэх; 3) даалгаврын зорилгын дагуу хязгаарлалтын тогтолцоог бичих; 4) асуудлын нөхцөл байдалд байгаа үзүүлэлтүүдийг харгалзан хязгаарлалтын системийг бичнэ үү. Хэрэв асуудлын бүх хязгаарлалтыг тэгшитгэлээр өгсөн бол энэ төрлийн загварыг каноник гэж нэрлэдэг. Хэрэв хязгаарлалтуудын дор хаяж нэг нь тэгш бус байдлаар өгөгдсөн бол загвар нь каноник биш болно. Слайд 9 аж ахуйн нэгжийн үйлдвэрлэлийн төлөвлөлтөд нөөцийг оновчтой хуваарилах асуудал (төрөл бүрийн асуудал); өгөгдсөн нэр төрлийн бүтээгдэхүүний гарцыг нэмэгдүүлэх даалгавар; хольцын асуудал (хоолны дэглэм, хоолны дэглэм гэх мэт); тээврийн даалгавар; байгаа хүчин чадлыг оновчтой ашиглах даалгавар; томилох даалгавар. Слайд 10 Аж ахуйн нэгж янз бүрийн бүтээгдэхүүн үйлдвэрлэдэг гэж бодъё. Тэдгээрийг үйлдвэрлэхэд янз бүрийн төрлийн нөөц (түүхий эд, хөдөлмөр, машины цаг, туслах материал) шаардлагатай байдаг. Эдгээр нөөц нь хязгаарлагдмал бөгөөд төлөвлөлтийн хугацаанд ердийн нэгжтэй тэнцэнэ. j-р төрлийн бүтээгдэхүүн үйлдвэрлэхэд i-р нөөцийн хэдэн нэгж шаардагдахыг харуулсан технологийн коэффициентүүд бас мэдэгдэж байна. j-р төрлийн бүтээгдэхүүний нэгжийг худалдах үед аж ахуйн нэгжийн олж авсан ашгийг тэнцүү гэж үзье. Төлөвлөлтийн хугацаанд бүх үзүүлэлтүүд тогтмол байна гэж үздэг. слайд 11 Бүтээгдэхүүн үйлдвэрлэх ийм төлөвлөгөө гаргах шаардлагатай бөгөөд үүнийг хэрэгжүүлэхэд аж ахуйн нэгжийн ашиг хамгийн их байх болно. Асуудлын эдийн засаг, математик загвар слайд 12 Зорилгын функц нь бүх төрлийн үйлдвэрлэсэн бүтээгдэхүүний борлуулалтаас олсон нийт ашиг юм. Асуудлын энэ загварт хамгийн ашигтай төрлийн бүтээгдэхүүнийг сонгох замаар оновчтой болгох боломжтой. Хязгаарлагдмал байдал гэдэг нь аливаа нөөцийн хувьд бүх төрлийн бүтээгдэхүүн үйлдвэрлэхэд шаардагдах нийт хэрэглээ нь нөөцөөс хэтрэхгүй байхыг хэлнэ. слайд 13 Слайд 14 А төрлийн бүтээгдэхүүн, - В төрлийн бүтээгдэхүүн, - С төрлийн бүтээгдэхүүн үйлдвэрлэнэ гэж бодъё.Тэгвэл ийм тооны бүтээгдэхүүн үйлдвэрлэхийн тулд тээрэмдэх машин цаг зарцуулна. Энэ төрлийн машинуудын нийт ажлын цагийн сан 120-аас хэтрэхгүй тул тэгш бус байдлыг хангах ёстой. слайд 15 Үүнтэй адилаар бид хязгаарлалтын тогтолцоог бүрдүүлж чадна слайд 16 Одоо зорилгын функц үүсгэе. А төрлийн бүтээгдэхүүний борлуулалтын ашиг нь 10, В төрлийн бүтээгдэхүүний борлуулалтаас -14, С-12 төрлийн бүтээгдэхүүний борлуулалтаас олсон ашиг нь бүх бүтээгдэхүүний борлуулалтаас олсон нийт ашиг юм. Слайд 17 Тиймээс бид дараахь LLP-д хүрч байна: Тэгш бус байдлын системийн бүх сөрөг бус шийдлүүдийн дотроос зорилгын функц хамгийн их утгыг авах нэгийг олох шаардлагатай. Слайд 18 Сүүний үйлдвэрийн бүтээгдэхүүн нь саванд савласан сүү, kefir, цөцгий юм. 1 тонн сүү, kefir, цөцгий үйлдвэрлэхэд 1010.1010, 9450 кг сүү шаардлагатай. Үүний зэрэгцээ 1 тонн сүү, kefir асгарах үед ажлын цагийн зардал 0.18 ба 0.19 машин цаг байна. 1 тонн цөцгийн савлагаа дээр тусгай машинууд 3.25 цагийн турш ажилладаг. Слайд 19 Тус үйлдвэр нийтдээ 136 мянган кг сүүг цэвэр сүүн бүтээгдэхүүн үйлдвэрлэх хүчин чадалтай. Үндсэн тоног төхөөрөмжид 21,4 цаг, цөцгий савлах машин 16,25 цаг ажиллах боломжтой. 1 тонн сүү, kefir, цөцгий борлуулснаас олсон ашиг нь 30, 22, 136 рубль байна. Тус үйлдвэр өдөрт дор хаяж 100 тонн савласан сүү үйлдвэрлэх ёстой. Бусад бүтээгдэхүүний үйлдвэрлэлд хязгаарлалт байхгүй. Слайд 20 Борлуулалтаас олох ашгийг нэмэгдүүлэхийн тулд үйлдвэр өдөр бүр ямар бүтээгдэхүүн, ямар хэмжээгээр үйлдвэрлэх ёстойг тодорхойлох шаардлагатай. Бодлогын математик загварыг гарга. слайд 21 Үйлдвэр нь хэдэн тонн сүү, тонн кефир, тонн цөцгий үйлдвэрлэе. Дараа нь түүнд нэг кг сүү хэрэгтэй болно. Үйлдвэр нь өдөрт 136,000 кг-аас ихгүй сүү хэрэглэх боломжтой тул тэгш бус байдлыг хангах ёстой. слайд 22 Сүү, kefir савлах, цөцгий савлах хугацаа. Нэгэнт өдөрт дор хаяж 100 тонн сүү гаргах ёстой. Эдийн засгийн хувьд слайд 23 Бүх бүтээгдэхүүний борлуулалтаас олсон нийт ашиг нь рубльтэй тэнцүү байна. Тиймээс бид дараахь асуудалд хүрнэ: хязгаарлалт дор Зорилгын функц нь шугаман бөгөөд хязгаарлалтууд нь тэгш бус байдлын системээр өгөгддөг тул энэ бодлого нь LLP юм. слайд 24 Шим тэжээл (өөх тос, уураг гэх мэт) агуулсан хоёр төрлийн бүтээгдэхүүн байдаг. Слайд 25 слайд 26 Шаардлагатай хамгийн бага шим тэжээлийг харгалзан хязгаарлалтын дагуу хоолны дэглэмийн нийт зардал Слайд 27 Асуудлын математик тайлбар: хязгаарлалтын системийг хангаж, зорилтот функцийг багасгах өдөр тутмын хоолны дэглэмийг бий болгох. Ерөнхийдөө хольцтой холбоотой асуудлын бүлэгт хүссэн шинж чанар бүхий хольцыг өгдөг тодорхой эхлэлийн материалын хамгийн хямд багцыг олох асуудлууд багтдаг. Үүссэн хольц нь тодорхой хэмжээгээр n өөр бүрэлдэхүүн хэсгүүдийг агуулсан байх ёстой бөгөөд бүрэлдэхүүн хэсгүүд нь өөрөө m эхлэлийн материалын бүрдэл хэсэг юм. Слайд 28 Тэмдэглэгээг танилцуулъя: -хольцонд орсон j-р материалын хэмжээ; - j төрлийн материалын үнэ; хольц дахь i-р бүрэлдэхүүн хэсгийн шаардагдах хамгийн бага агууламж юм. Коэффициентүүд нь j-р материалын нэгж дэх i-р бүрэлдэхүүн хэсгийн хувийн жинг харуулдаг Слайд 29 Зорилгын функц нь хольцын нийт өртөг бөгөөд функциональ хязгаарлалт нь хольц дахь бүрэлдэхүүн хэсгүүдийн агууламжийн хязгаарлалт юм: хольц нь заасан хэмжээнээс багагүй хэмжээгээр бүрэлдэхүүн хэсгүүдийг агуулсан байх ёстой. слайд 30 Оёдлын үйлдвэрт даавууг хэд хэдэн аргаар огтолж, хүссэн хувцсыг үйлдвэрлэх боломжтой. i-р төрлийн эд ангиудыг j-р зүсэх хувилбараар үйлдвэрлэе, энэ зүсэлтийн хувилбарт гарах хаягдлын хэмжээ нь хаягдал байна. Бодлогын математик загварыг гарга. Слайд 31 Шийдэл. j-р хувилбарын дагуу хэдэн зуун даавууг тайрсан гэж бодъё. Даавууг j-р сонголтын дагуу зүсэх үед i-р төрлийн хэсгүүдийг авдаг тул ашигласан даавуунаас зүсэх бүх сонголтуудын хувьд бүх зүсэх сонголтуудын нийт хог хаягдлын хэмжээг авна. Слайд 35 Def.4. Үндсэн буюу каноник LLP нь хязгаарлалтын системийг тэгшитгэлийн систем болгон харуулсан тохиолдолд зорилгын функцийн утгыг тодорхойлохоос бүрдэх ажил юм. слайд 36 Хэрэв бичлэгийн нэг хэлбэрээс нөгөө хэлбэрт шилжих нь ая тухтай байдал эсвэл ажлын утга учир шаардлагатай бол дараах байдлаар үргэлжлүүлнэ үү. Хэрэв та функцийн минимумыг олох шаардлагатай бол зорилгын функцийг (-1) үржүүлж хамгийн ихийг олох боломжтой. Тэгш бус хэлбэрийн хязгаарлалтыг зүүн талд нь сөрөг бус нэмэлт хувьсагчийг нэмснээр тэгш бус байдлын хязгаарлалтыг зүүн талаас нь хасах нэмэлт сөрөг бус хувьсагчийг тэгш бус байдлын хязгаарлалт болгон хувиргаж болно. Слайд 41 Туслах загвар нь m эерэг бүрэлдэхүүн хэсгүүдийг агуулж байвал доройтдоггүй гэж нэрлэдэг. Үгүй бол үүнийг доройтсон гэж нэрлэдэг. LLP-ийн зорилгын функц нь хамгийн их (хамгийн бага) утгыг авдаг төлөвлөгөөг оновчтой гэж нэрлэдэг.
Бүх слайдыг үзэх Оршил Шугаман программчлал нь үйл ажиллагааны судалгааны нэг салбар болох бараг дөчин жилийн түүхтэй. Компьютерийн технологийг нэвтрүүлсэн нь математикийн энэ чиглэлээр судалгаа хийхэд ихээхэн түлхэц өгсөн. Шугаман програмчлалын асуудлыг шийдвэрлэх хэд хэдэн алгоритмыг боловсруулж, дараагийн жилүүдэд гол төлөв том компьютерт зориулсан программууд, програм хангамжийн багцуудыг бий болгосон. Уран зохиолын дийлэнх хэсэг нь Манай улсад шугаман програмчлал 60-70-аад онд гарсан. Энэ чиглэлийн судалгаа (онолын болон хэрэглээний аль аль нь) одоогоор үргэлжилж байна. Шугаман програмчлалын аргууд нь үйл ажиллагааны судалгааны салбарын зарим асуудлыг шийдвэрлэхэд маш үр дүнтэй болох нь батлагдсан. Бид "програмчлал" гэдэг үгийг төлөвлөлт гэж ойлгодог бөгөөд энэ нь авч үзэж буй хэрэглээний мөн чанарыг тодорхойлдог. Шугаман програмчлалын гол санаанууд нь Дэлхийн 2-р дайны үед цэргийн ажиллагаа явуулах оновчтой стратеги хайхтай холбогдуулан үүссэн. Түүнээс хойш тэд үйлдвэрлэл, худалдаа, захиргааны салбарт өргөн хэрэглээг олж авсан - орон нутгийн болон үндэсний аль алинд нь. Эдгээр аргууд нь хязгаарлагдмал нөөцийг үр ашигтай ашиглахтай холбоотой олон (бүгд биш ч) асуудлыг шийдэж чадна. Математикийн арга, загваруудыг сайн мэддэг, өргөн тархсан бөгөөд янз бүрийн нэрээр ашигладаг - шийдвэр гаргахад математикийн аргууд; үйл ажиллагааны судалгааны аргууд; эдийн засаг, математикийн арга; эдийн засгийн кибернетикийн аргууд; оновчтой хяналтын арга, эдийн засаг, үйлдвэрлэлийн зохион байгуулалтад хэрэглээний математик гэх мэт Энэ сэдвээр олон хэвлэлд (илүү их бага өргөн хүрээтэй) тэдгээрийг янз бүрийн хослолоор авч үздэг. Үйл ажиллагааны судалгаа нь янз бүрийн зохион байгуулалтын тогтолцоог хамгийн үр дүнтэй удирдах аргуудыг боловсруулах, практикт хэрэглэх чиглэлээр ажилладаг шинжлэх ухааны салбар юм. Аливаа тогтолцоог удирдах нь тодорхой хууль тогтоомжид захирагдах үйл явц хэлбэрээр хэрэгждэг. Тэдний мэдлэг нь энэ үйл явцыг хэрэгжүүлэхэд шаардлагатай, хангалттай нөхцлийг тодорхойлоход тусалдаг. Үүнийг хийхийн тулд үйл явц, гадаад нөхцөл байдлыг тодорхойлсон бүх параметрүүдийг тоолж, хэмжих ёстой. Тиймээс үйл ажиллагааны судалгааны зорилго нь удирдлагын зохион байгуулалтын талаар гаргасан шийдвэрийн тоон үндэслэл юм. Аливаа загварчлалын зорилго нь объектыг эхлээд чанарын хувьд, дараа нь мэдээлэл хуримтлагдаж, загвар хөгжихийн хэрээр илүү нарийвчлалтай тоон түвшинд судлах явдал юм. Эдгээр санааг энгийн жишээгээр тайлбарлаж болно. "Магадлалын онол" арга нь "магадлал", "санамсаргүй үйл явдал", "санамсаргүй хэмжигдэхүүн", "санамсаргүй хэмжигдэхүүний математик хүлээлт (дундаж утга)" гэсэн ойлголтуудтай ажилладаг математик загваруудын өргөн ангиллын хувьд байсан (одоо ч хэвээр байна). XIX, XX зууны хил дээр ", "тархалт (тарсан)" гэх мэт. шинэ объект гарч ирнэ - "холболт хийх өргөдөл", "татгалзах", "холболт хүлээх хугацаа", "шилжүүлэх" болон системийн бусад шинж чанаруудтай холбоотой утсан холбооны систем. 20-иод онд. А.К.Эрланг энэ арга, объектыг холбосон; Үүний үр дүнд "захиалгын урсгал", "хүлээлтийн дундаж хугацаа", "үйлчилгээний дарааллын дундаж урт", "хүлээлтийн хугацааны зөрүү", "бүтэлгүйтэл" гэсэн ойлголттой ажилладаг телефон утасны сүлжээн дэх процессуудын математик магадлалын загварыг бий болгосон. магадлал" гэх мэт. Энэхүү шинжлэх ухааны чиглэлийн цаашдын хөгжил нь энэхүү загварын үзэл баримтлалын үндэс нь үр дүнтэй, дизайны өргөн боломжуудыг харуулсан. Энэхүү загвар нь нарийн төвөгтэй системийг судлах арга болгон хөгжүүлсэн - "дарааллын онол", нэр томъёо, үзэл баримтлалын үндэс нь утасны сүлжээнүүдийн холбооноос салж, онолын ерөнхий шинж чанарыг олж авсан. Одоо дарааллын онолыг бусад объектод (үйлдвэрлэлийн процесс, компьютерийн үйлдлийн систем, хөдөлгөөний урсгал гэх мэт) хэрэглэснээр шинэ загваруудыг бүтээх боломжтой. Тиймээс, нэг талаас, нэг төрлийн загвар, өөрөөр хэлбэл янз бүрийн объектыг нэг талаас нь авч үзэх арга замыг боловсруулж, нөгөө талаас объектыг илүү гүн гүнзгий мэддэг байх тусам илүү олон объектын загвар боловсруулдаг бол аргыг тодорхойлдог. . Үүний зэрэгцээ, загварын хоёрдмол шинж чанар нь ерөнхий ("арга"-аас) ба тусгай ("объект"-аас) үзэл баримтлалыг багтаасан загварчлалын үзэл баримтлалын баазын хоёрдмол байдалд хүргэдэг. Үйл ажиллагааны судалгаа нь практик зохион байгуулалтын (эдийн засгийн гэх мэт) асуудлыг шийдвэрлэхэд ашигладаг хэрэглээний математик аргуудын багц юм. Энэ бол шинжлэх ухааны нарийн төвөгтэй салбар юм. Түүний судалж буй асуудлын хүрээ хангалттай тодорхойлогдоогүй байна. Заримдаа үйл ажиллагааны судалгааг маш өргөн хүрээнд ойлгодог бөгөөд үүнд хэд хэдэн цэвэр математик аргууд, заримдаа эсрэгээр, маш явцуу байдлаар - эдийн засаг, математикийн загварыг ашиглан хатуу тодорхойлсон асуудлын жагсаалтыг шийдвэрлэх практик арга техник гэж ойлгодог. Үйл ажиллагааны судалгааны гол арга бол зорилготой үйлдлүүдийн (үйл ажиллагаа) системчилсэн дүн шинжилгээ, эдгээр үйл ажиллагааны боломжит үр дүнг бодитой (ялангуяа тоон) харьцуулсан үнэлгээ юм. Үйл ажиллагааны судалгааны асуудлын хамгийн чухал ангиллын нэг бол бараа материалын менежмент, нөөцийн хуваарилалт, хуваарилалтын асуудал (хуваарилалтын асуудал), дарааллын асуудал, тоног төхөөрөмжийг солих, захиалга, зохицуулалтын асуудал (хуваарийн онолыг оруулаад), зөрчилдөөн (жишээлбэл, тоглоом), хайлтын бодлого гэх мэт. Ашигласан аргуудын дунд математик програмчлал (шугаман, шугаман бус гэх мэт), дифференциал ба ялгаа тэгшитгэл, графикийн онол, Марковын процесс, тоглоомын онол, (статистик) шийдлийн онол, хэв маягийг таних онол, бусдын тоо. Үйл ажиллагааны судалгаа нь Дэлхийн 2-р дайны өмнөхөн Англид математикийн тусламжтайгаар техникийн асуудлыг шийдвэрлэхийн тулд радиолокаторын станцад хэсэг мэргэжилтнүүдийг байгуулж байх үед үүссэн гэж үздэг. Тэд асуудлыг шийдвэрлэх арга замуудын үр нөлөөг харьцуулах, оновчтой шийдлийг олоход анхаарлаа хандуулав. Төрөл бүрийн мэргэжлийн төлөөлөгчдийн энэ бүлэгт оролцох нь иж бүрэн буюу одоо хэлж байгаа шиг системчилсэн хандлагыг урьдчилан тодорхойлсон. Одоогийн байдлаар олон арван орны олон зуун судалгааны байгууллага, бүлгүүд энэ чиглэлээр ажиллаж байна. Үйл ажиллагааны судалгааны нийгэмлэгүүдийг Олон улсын холбоо (IFORS) зохион байгуулдаг. Оросын эрдэмтэд Л.В.Канторович, Н.П. Бусленко, Е.С. Вентцел, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин болон бусад олон. Үйл ажиллагааны судалгааг бий болгох, хөгжүүлэхэд гадаадын эрдэмтэд Р.Акоф, Р.Беллман, Г.Данзиг, Г.Кун, Ж.Нейман, Т.Саати, Р.Черчман, А.Кофман болон бусад эрдэмтэд ихээхэн хувь нэмэр оруулсан. Үйл ажиллагааны судалгааны аргууд нь аливаа математик аргуудын нэгэн адил шугаман бус процессыг шугаман загвараар, стохастик системийг детерминист системээр тусгаж, асуудлыг тодорхой хэмжээгээр хялбаршуулдаг. Тиймээс үйл ажиллагааны судалгааны тоон аргын үнэ цэнийг хэтрүүлж болохгүй. Үүнийг дутуу үнэлж болохгүй. , бүтэлгүйтсэн шийдвэрүүдийн жишээг дурдав. Энэ чиглэлээр Америкийн томоохон мэргэжилтэн өгсөн парадоксик тодорхойлолтыг мэддэг Т.А.Саати: "Үйл ажиллагааны судалгаа бол өөр аргаар бүр дорддог практик асуултуудад муу хариулт өгөх урлаг юм." ҮЙЛДВЭРЛЭЛИЙН ТЕХНОЛОГИ, АЖ АХУЙН ТӨВ ДУНДЫН КОЛЛЕЖ би зөвшөөрч байна орлогч Боловсролын захирал «» 200 Г . ДАСГАЛ курс дизайны хувьд "Математикийн арга" сэдвээр Оюутан: Сергеев Евгений Анатольевич. Төслийн сэдэв: "Шугаман програмчлал, симплекс аргаар асуудлыг шийдвэрлэх". ТАЙЛБАРЫН ТАЙЛБАР Даалгавар ба тэдгээрийн шийдэл: Нэгдүгээр даалгавар: Симплекс асуудлыг дараах аргаар шийд. F = 2X1 +3X2 → хамгийн их 3.1.2 Хоёрдугаар даалгавар: Тус компани нь хоёр төрлийн бүтээгдэхүүн үйлдвэрлэдэг. Түүхий эдийн төрөл, тэдгээрийн нөөц, түүхий эдийн хэрэглээний хэмжээ y. д.бүтээгдэхүүний төрөл тус бүр, бүтээгдэхүүний борлуулалтаас олсон ашгийг хүснэгтэд үзүүлэв. 3.1.3. Гурав дахь даалгавар: Тус компани 3 нэр төрлийн бүтээгдэхүүн үйлдвэрлэдэг бол 3 төрлийн түүхий эд ашигладаг. Түүхий эдийн нөөц, тэдгээрийн хэрэглээний хэмжээ, бүтээгдэхүүн бүрийн борлуулалтаас олсон ашгийг хүснэгтэд үзүүлэв. Ашиг нэмэгдүүлэхийн тулд үйлдвэрлэлийг хэрхэн төлөвлөх ёстой вэ? 3.1.4. Дөрөв дэх даалгавар: 4 төрлийн бүтээгдэхүүн үйлдвэрлэхэд 3 төрлийн түүхий эдийг ашигладаг. Түүхий эдийн нөөц, тэдгээрийн хэрэглээний хэмжээ, бүтээгдэхүүн бүрийн борлуулалтаас олсон ашгийг хүснэгтэд үзүүлэв. Ашиг нэмэгдүүлэхийн тулд үйлдвэрлэлийг хэрхэн төлөвлөх ёстой вэ? 3.
Дүгнэлт 4.
Ном зүй Циклийн комиссын дарга/ Баранов В.А. Курсын төслийн менежер/ Карпушкин А.Г. Даалгавар олгосон огноо: Дуусах огноо: « » 2007 « » 2007 он ЭНГИЙН АРГА Симплекс аргыг анх 1949 онд Америкийн эрдэмтэн Ж.Данзиг санал болгосон ч тэртээ 1939 онд уг аргын санааг Оросын эрдэмтэн боловсруулжээ. Л В.Канторович. Шугаман програмчлалын аливаа асуудлыг шийдвэрлэх боломжийг олгодог симплекс арга нь бүх нийтийнх юм. Одоогоор үүнийг компьютерийн тооцоололд ашиглаж байгаа боловч симплекс аргыг ашиглан энгийн жишээг гараар шийдэж болно. Симплекс аргыг хэрэгжүүлэхийн тулд - шийдлийг дараалан сайжруулах - гурван үндсэн зүйлийг эзэмших шаардлагатай бүрэлдэхүүн: Анхны зөвшөөрөгдөх аливаа зүйлийг тодорхойлох арга асуудлын үндсэн шийдэл; Шилдэг (илүү нарийвчлалтай, хамгийн муу биш) шийдэлд шилжих дүрэм; Олдсон шийдлийн оновчтой байдлыг шалгах шалгуур. Симплекс аргыг ашиглахын тулд шугаман програмчлалын асуудлыг каноник хэлбэрт оруулах ёстой, i.e. хязгаарлалтын системийг тэгшитгэлийн хэлбэрээр харуулах ёстой. Ердийн Жорданы үл хамаарах зүйлүүд n үл мэдэгдэх m шугаман тэгшитгэлийн системийг авч үзье a11 x1 + a12 x2 + … + a1n xn = b1, am1 x1 + am2 x2 + … + amn xn = bm. Бид энэ системийг хүснэгт хэлбэрээр бичдэг a11 … a1j … a1n ……………….. ai1 … aij … ain ……………….. am1 … amj … amn I шийдвэрлэх мөр, j шийдвэрлэх багана бүхий aij ≠ 0 шийдвэрлэх элемент бүхий өгөгдсөн хүснэгтэд хийгдсэн энгийн Jordan Elimination (OJI) алхам нь тэгшитгэлийг шийдвэрлэх үйлдэл юм. bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn xj-ийн хувьд энэ шийдлийг анхны системд орлуулж, шинээр олж авсан системийг шинэ хүснэгт хэлбэрээр бичнэ. Шинэ хүснэгт иймэрхүү харагдах эсэхийг шалгахад хялбар байдаг b11 b12 … a1j … b1n b21 b22 … a2j … b2n ……………….. Ai1 –ai2 … 1… -ain ……………….. bm1 bm2 … amj … bmn Энд brs = ars aij - arj ais (i ≠ r, j ≠ s), мөн хүснэгтийн бүх элементүүдийг aij -д хуваах ёстой. Тиймээс нэг Жорданы хасалт (JJI) алхам нь дараах 5 дүрмээс бүрдсэн схемийн дагуу анхны хүснэгтийг шинэ хүснэгт болгон хувиргадаг. 1) идэвхжүүлэх элементийг нэгээр сольсон 2) шийдвэрлэх баганын j үлдсэн элементүүд өөрчлөгдөөгүй хэвээр байна. 3) шийдвэрлэх мөрийн үлдсэн элементүүд i зөвхөн тэдгээрийн тэмдгүүдийг өөрчилдөг. 4) brs-ийн үлдсэн элементүүдийг brs = ars aij - arj ais томъёогоор тооцоолно. 5) шинэ хүснэгтийн бүх элементүүдийг aij шийдвэрлэх элементээр хуваана. Жишээ 1. Хүснэгтийн хувьд Жорданы үл хамаарах зүйлүүд нь санамсаргүй байдлаар авсан координатын хавтгайн декартын системээс цэгүүдийн координатууд нь тодорхой асуудлын хувьд илүү сонирхолтой онгоцны системээс хазайсан шинэ систем рүү шилжих боломжийг олгодог. Өөрчлөгдсөн Жорданы үл хамаарах зүйлүүд Хэрэв анхны тэгшитгэлийн систем ai1 x1 + ai2 x2 + … + ain xn = bi, энд i = 1,m, -ai1 (-x1) - ai2 (-x2) - ... - ain (-xn) = bi гэж бичих мөн ширээ хий Энэ нь 2 ба 3-р дүрмүүд дүрмээ өөрчилсөн цорын ганц өөрчлөлтөөр МУ-ын 1-5-р дүрмийн дагуу олж авсан болно. 1) зөвшөөрөгдсөн мөрийн үлдсэн элементүүд өөрчлөгдөөгүй хэвээр байна 2) шийдвэрлэх баганын үлдсэн элементүүд нь зөвхөн тэдгээрийн тэмдгүүдийг өөрчилдөг Системийг анхаарч үзээрэй 2X1 + 3X2 - 5X3 = 16 = b1, 3X1 - 2X2 + 4X3 = 36 = b2, 5X1 + 7X2 - 11X3 = 44 = b3. Үүнийг хүснэгт хэлбэрээр бичье Шугаман функцийн экстремум Шугаман програмчлалын ерөнхий бодлогыг авч үзье. LP-ийн тооцооллын аргууд нь дараах үндсэн теорем дээр суурилдаг. Теорем. Шугаман програмчлалын бодлого оновчтой шийдэлтэй бол (үргэлж хязгаарлагдмал талбайд, мөн Z функцийн хязгаарлагдмал байдлаас хамааран хязгааргүй талбайд), дараа нь энэ нь хязгаарлах тэгшитгэлийн системийн хамгийн багадаа нэг тулгуур шийдэлтэй давхцдаг. Энэ теоремын дагуу тэдгээрийн дотроос хүссэн оновчтой шийдлийг олохын тулд боломжит шийдлүүдийн хязгааргүй багцыг судлахын оронд зөвхөн хязгаарлагдмал тооны туслах шийдлүүдийг судлах шаардлагатай. Энэ теорем нь дор хаяж нэг дэмжлэгийн оновчтой шийдэл байдаг гэж заасан боловч асуудалд хэд хэдэн дэмжлэгийн оновчтой шийдлүүд (өөр оновчтой) байж болно. Тиймээс шугаман програмчлалын асуудлыг шийдвэрлэх бүдүүвч диаграмм нь дараах байдалтай байна. 1. ZhI-ийн тусламжтайгаар бид системийн бүх дэмжлэгийн шийдлүүдийг олох болно. a11 x1 + a12 x2 + … + a1n xn = b1 , ……................... ak1 x1 + ak2 x2 + … + akn xn = bk , ak+1,1 x1 + ak+1,2 x2 + … + ak+1n xn ≤ bk+1 , ……................... am1 x1 + am2 x2 + … + amn xn ≤ bm . 2. Харьцаагаар тодорхойлогдсон Z функцийн утгыг тус бүрээр нь тооцоол. Z = c1 x1 + c2 x2 + … + cn xn. 3. Бид тэднээс экстремаль Z-г сонгодог. Маш олон тооны лавлагаа шийдлүүд байж болох тул лавлагаа шийдлүүдийн дараалсан тооллогыг хийх шаардлагатай гэдгийг тэмдэглэх нь зүйтэй. Z функцийн монотон өөрчлөлтийн алхам бүр. Шийдвэрийг дараалан сайжруулах ийм санаа нь симплекс арга гэж нэрлэгддэг шугаман програмчлалын асуудлыг шийдвэрлэх үндсэн тооцооллын аргад шингэсэн болно. Бүрэн хүснэгтэд суурилсан симплекс арга Бүтээгдэхүүний оновчтой нэр төрлийг тодорхойлох асуудлын талаархи мэдэгдэл Тус үйлдвэр нь 350 ба 392 кг хэмжээтэй төмөр, ган материалын нөөцтэй, 408 машин цагийн тоног төхөөрөмж бүхий А ба В хоёр төрлийн бүтээгдэхүүн үйлдвэрлэх боломжтой. Хүснэгт хэлбэрээр үзүүлсэн өгөгдөл нь нэг бүтээгдэхүүн А ба В үйлдвэрлэхэд жагсаасан гурван төрлийн нөөц бүрийн зардлыг тодорхойлдог. Аж ахуйн нэгж хамгийн их ашиг олохын тулд А, В хэдэн бүтээгдэхүүн үйлдвэрлэх ёстойг тодорхойлох шаардлагатай. Бид шаардлагатай үл мэдэгдэх X1 ба X2-ийг танилцуулж, тухайн аж ахуйн нэгжийн үйлдвэрлэх ёстой А ба В бүтээгдэхүүний тоог илэрхийлдэг. Дараа нь математикийн хувьд асуудлыг дараах байдлаар томъёолж болно. Тэгш бус байдлын системийн сөрөг бус шийдлүүдийн багцын дунд 14X1 + 5X2 ≤ 350, (1.1) 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, функц болох шийдлийг ол Z = 10 X1 + 5 X2 хамгийн дээд үнэ цэнэдээ хүрдэг. Асуудлын геометрийн шийдэл Юуны өмнө тэгш бус байдлын системд тохирох боломжтой шийдлүүдийн мужийг байгуулъя. Үүнийг хийхийн тулд тэгш бус байдал бүрийг тэгшитгэлээр солино 14X1 + 5X2 = 350, (1-р шулуун шугам), 14X1 + 8X2 = 392, (2-р мөр), 6X1 + 12X2 = 408, (3-р шулуун шугам), хилийн шугам барих. X1 ≥ 0 ба X2 ≥ 0 гэдгийг харгалзан бид OABCD уусмалын олон өнцөгтийг бүрдүүлдэг хавтгайн сүүдэртэй хэсгийг олж авдаг (Зураг 1). Дараа нь бид 10X1 + 5X2 = 0 түвшний шугам ба харилцан перпендикуляр вектор (10; 5) байгуулна. Вектор нь шугаман функцийн хамгийн их өсөлтийн чиглэлийг өгдөг болохыг харуулахад хялбар байдаг. Үнэхээр Z0 \u003d 10X10 + 5X20 \u003d 10 * 0 + 5 * 0 \u003d 0, ZA \u003d 10X1A + 5X2A \u003d 10 * 0 + 5 * 34 \u003d 170, ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 гэх мэт. Бүх түвшний шугамуудаас бид хоёрыг сонгох ба тэдгээрийн нэг нь 0 цэгээр дамжиж Z функцийн мин утгыг өгдөг, нөгөө нь C цэгээр дамжин өнгөрч, түүнд зориулсан Z функц нь max утгыг авдаг. Эдгээр түвшний шугамыг лавлах шугам гэж нэрлэдэг. Цагаан будаа. 1 С цэг нь эхний ба хоёр дахь шугамаар үүсгэгддэг. Тиймээс тэгшитгэлийн системийг шийдэж байна 14Xl + 5X2 = 350, 14X1 + 8X2 = 392, С цэгийн координатыг ол X1 = 20, X2 = 14, харин Zmax \u003d 10 * 20 + 5 * 14 \u003d 270 рубль. Тиймээс хамгийн их ашиг 270 рубль байна. А төрлийн 20, В төрлийн 14 бүтээгдэхүүн үйлдвэрлэсэн бол хүлээн авна. Шугаман функцийн максимумыг олох Шугаман програмчлалын асуудлыг шийдвэрлэх симплекс арга нь тэгшитгэлийн системийн ижил (симплекс) хувиргалтыг дараалан хэрэглэхэд үндэслэсэн тохиромжтой тооцоолох алгоритмуудын багц болох дараалсан арилгахын өмнө дүн шинжилгээ хийсэн аргад тулгуурласан зарим нэмэлтүүд юм. Тэгш бус байдлын зүүн талд нэмэх 14X1 + 5X2 ≤ 350, 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, зарим сөрөг бус утга Yj ≥ 0 (i = 1, 2, 3), (1.2) тэгшитгэл буюу үндсэн хувьсагч гэж нэрлэгддэг бид тэдгээрийг тэгшитгэл болгон хувиргадаг. X1 + 5X2 + Y1 Түүгээр ч зогсохгүй тэгш бус байдлын (1.1) системийн шийдэл бүр нь тэгшитгэл (1.3) ба тэгш бус байдлын (1.2) системийн өвөрмөц шийдэлтэй тохирч байгааг харуулж болно. Y1, Y2, Y3 хувьсагч бүр нь зөвхөн нэг тэгшитгэлд багтдаг бөгөөд бидний чөлөөт гэж нэрлэдэг X1, X2 хувьсагчдаас хамаардаг. Систем (1.3) нь анхны зөвшөөрөгдөх үндсэн шийдэлтэй тохирч байна X1 = X2 = 0; Y1 = 350; Y2 = 392; Y3 = 408 ба Z = 0. Бид тэгшитгэлийн системийн анхны ижил хувирлыг (1.3) гүйцэтгэдэг. Бид Z эгнээний хамгийн жижиг сөрөг элементтэй харгалзах шийдвэрлэх баганыг сонгодог, учир нь өөрөөр тэнцүү нөхцөлд Z функц илүү их хэмжээгээр нэмэгдэх боломжтой гэдгийг онолын хувьд тогтоосон. . Сонгосон багана ба мөрийн огтлолцол дээр нягтралын дугаар байна. Бид эхний тэгшитгэлийг нарийвчлалын дугаарт хувааж, үүссэн тэгшитгэлийг бичнэ. Энэ тэгшитгэлийг 14, 6 ба -10-аар үржүүлж (1.3) системийн 2, 3, 4-р тэгшитгэлээс хасвал бид дараах систем (1.4)-д хүрнэ. X2 + 1/4 Y1 = 25, X2 - 6/14 Y1 + Y3 Заасан дүрмийн дагуу шийдвэрлэх тоог сонгох ийм ижил хувиргалтыг симплекс хувиргалт гэж нэрлэнэ. Тиймээс симплекс хувиргалтыг дараах дүрмийн дагуу гүйцэтгэнэ. 1. Z - эгнээний хамгийн бага сөрөг элементтэй тохирох идэвхжүүлэх баганыг сонгоно. 2. Тэгшитгэлийн баруун талын элементүүдийг шийдвэрлэх баганын харгалзах элементүүдэд хамгийн бага эерэг харьцаатай тохирох шийдвэрлэх мөрийг сонгосон. Шийдвэрлэх багана болон шийдвэрлэх мөрийн огтлолцол дээр шийдвэрлэх дугаар байна. 3. Зөвшөөрөгдсөн мөрийн элементүүдийг зөвшөөрөгдсөн тоогоор хуваана. 4. Бусад бүх эгнээний элементүүдийг дараах томъёогоор тооцоолно. (1.4) системээс бид хоёр дахь зөвшөөрөгдөх үндсэн шийдлийг олно Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, энэ нь Z = 250 функцийн шинэ нэмэгдсэн утгатай тохирч байна. Тиймээс дараалсан симплекс хувиргалтын үйл явц нь шийдлийг дараалан сайжруулах үйл явц юм. Үүнд: 1. Хэрэв Z - мөрөнд ядаж нэг сөрөг элемент байвал ба a) шийдвэрлэх баганад дор хаяж нэг эерэг элемент байгаа бол шийдлийг сайжруулах боломжтой; б) хэрэв шийдвэрлэх баганад эерэг элемент агуулаагүй бол Z функц тодорхой бус хугацаагаар нэмэгдэнэ. 2. Хэрэв Z - эгнээний бүх элементүүд сөрөг биш байвал оновчтой шийдэлд хүрсэн байна. Эдгээр нь оновчтой шийдлийн төлөвлөгөөг бий болгох хангалттай нөхцөл юм. (1.4) системд Z - эгнээний X2 дахь коэффициент сөрөг байгаа тул хоёр дахь багана шийдэгдэх болно. Хоёр дахь мөр нь зөвшөөрөгдөх болно гэдгийг бид олж мэдсэн. Дараа нь бид заасан дүрмийн дагуу (1.4) системийн симплекс хувиргалтыг хийнэ. X1 + 8/42 Y1 - 5/42 Y2 = 20, X2 - 1/3 Y1 + 1/3 Y2 = 14, 20/7 Y1 - 23/7 Y2 + Y3 = 120, 10/42 Y1 + 20/42 Y2 + Z = 270, (1.5) Z эгнээний бүх элементүүд сөрөг биш тул энэ төлөвлөгөө оновчтой байна. Энэ тохиолдолд Yl = Y2 = 0; X1 = 20; X2 = 14 ба Zmax = 270. Симплекс хувиргалтыг хийх нь нарийн төвөгтэй бөгөөд ихэвчлэн нэлээд төвөгтэй тооцоололтой холбоотой байдаг. Асуудлыг шийдвэрлэхийн тулд симплекс хүснэгт гэж нэрлэгддэг хүснэгтүүдийг ашиглан эдгээр тооцоог маш хялбарчилж болно. Системийн симплекс хувиргалт бүр нь нэг симплекс хүснэгтээс нөгөө рүү шилжих шилжилт болж буурдаг. Анхны тэгшитгэлийн системийн дагуу (1.3) бид анхны симплекс хүснэгтийг (Хүснэгт 1.1) байгуулав. Хүснэгт 1.1 Эхний багана нь үндсэн хувьсагчдын багана, хоёр дахь багана нь тэгшитгэлийн баруун талын чөлөөт коэффициентүүдийг (1.3), эхний мөрөнд бүх хувьсагчдыг, сүүлийн багана нь хяналтын багана, түүний доторх коэффициентүүд нь дараахтай тэнцүү байна. эгнээний бүх коэффициентүүдийн нийлбэр. Хүснэгтээс. 1.1 Бид (1.3) X1 = X2 = 0, Y1 = 350 системийн анхны зөвшөөрөгдөх шийдэлтэй байна. Y2 = 392, Y3 = 408, Z = 0, энэ нь OABCD боломжит шийдлүүдийн олон өнцөгтийн О (0,0) оройтой тохирч байна (Зураг 1). Хоёрдахь симплекс хүснэгт рүү (Хүснэгт 1.2) шилжих нь тэгшитгэлийн системийн симплекс хувиргалтыг энэ хэсэгт заасан дүрмийн дагуу гүйцэтгэдэг бол шийдвэрлэх хувьсагч X1 нь шийдвэрлэх хувьсагч Y1 оронд суурь руу ордог. 1.2. Хүснэгт 1.2 Хүснэгтийг бөглөсний дараа 1.2. Үүнийг бөглөх зөв эсэхийг шалгах шаардлагатай бөгөөд үүний тулд коэффициентийг мөрөөр нэгтгэн дүгнэж, энэ нийлбэр нь хяналтын баганын харгалзах нүднүүдийн коэффициентуудтай тэнцүү байх ёстой. Хүснэгтээс. 1.2 хоёр дахь хүчинтэй шийдэл нь X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258, Z = 250 байна. Энэ хүснэгт нь систем (1.4) болон лавлагааны шийдэлтэй тохирч байгааг харахад хялбар байдаг X1 = 25, X2 = 0 нь уусмалын олон өнцөгтийн D(25,0) оройтой тохирч байна. Z эгнээнд сөрөг элемент байгаа тул бид шийдлийг сайжруулж, симплекс хүснэгтийг эмхэтгэдэг. 1.3. Хүснэгт 1. 3
* Тэмдэглэл. Тооцооллыг хялбарчлахын тулд шинэ хүснэгтэд зөвшөөрөгдсөн баганын элементүүдийн оронд (зөвшөөрөгдсөн элементээс бусад) тэг байдаг гэдгийг санах нь зүйтэй. Хэрэв шийдвэрлэх мөрөнд тэг байгаа бол харгалзах багануудыг өөрчлөлтгүйгээр шинэ хүснэгтэд шилжүүлнэ. Z - мөрөнд сөрөг элемент байхгүй тул энэ шийдэл нь оновчтой байх болно. Таб. 1.3 нь тэгшитгэлийн системд (1.5) тохирч, оновчтой шийдэл Х1 = 20, OABCD зөвшөөрөгдөх шийдлийн олон өнцөгтийн X2 = 14 ба Zmax = 270 ба орой С (20,14). Эхний мөрөнд байгаа бүх хувьсагчдыг агуулсан ийм уртасгасан хүснэгтүүд нь хяналтын багана байгаа тул хүснэгтийг зөв бөглөх эсэхийг хянах, арифметик алдаанаас зайлсхийх боломжийг олгоно. Таслагдсан хүснэгтэд суурилсан симплекс арга Тэгшитгэлийн системийг (1.3) авч үзээд 1.4-р хүснэгтийн хэлбэрээр бичнэ үү Хүснэгт 1.4 Бид эхний баганад үндсэн хувьсагчдыг (BP), эхний мөрөнд чөлөөт хувьсагчдыг (SP) бичнэ. Дараа нь шинэ хүснэгт 1.5 руу шилжих нь дүрмийн дагуу хийгддэг. 1) SP ба АД-ыг солих 2) шийдвэрлэх элементийн оронд түүнд харилцан хамааралтай утга байна 3) бид шийдвэрлэх шугамын элементүүдийг шийдвэрлэх тоогоор хуваана 4) бид шийдвэрлэх баганын элементүүдийг шийдвэрлэх баганаар хувааж, тэмдгийг өөрчилнө 5) үлдсэн элементүүдийг "Шугаман функцийн хамгийн ихийг олох" бүлгийн 4-р дүрмийн дагуу (OGI-ийн тэгш өнцөгтийн дүрэм) олж авна. Бид 1.5 хүснэгтийг авна. Хүснэгт 1.6 Бид X1 =20, X2 = 14 гэсэн оновчтой Zmax = 270 төлөвлөгөөг авсан бөгөөд тоног төхөөрөмжийн нөөц нь 120 машин цагт хэтэрсэн байна. Шугаман програмчлалын асуудлыг шийдвэрлэх Хамгийн их зорилгын функцийг ол хязгаарлалт дор 14x + 5y ≤ 350 Програм ашиглан асуудлыг шийдвэрлэх Microsoft Excel. A3 ба B3-ийг x ба y хувьсагчдын утгуудад оноож үзье. C4 нүдэнд зорилгын функцийг оруулна уу A7:A9 нүдэнд бид хязгаарлалтын зүүн хэсгийг оруулав мөн B7:B9 нүднүүдэд - хязгаарлалтын зөв хэсгүүд. Үүний дараа командыг сонгоно уу Үйлчилгээ, Шийдэл хайж байна(Tools, Solver) болон нээгдэх харилцах цонхыг бөглөнө үү Шийдэл олох (Уусгагч) Зурагт үзүүлсэн шиг. 2. Товчлуурыг дарсны дараа Гүй(Шийдвэрлэх) цонх нээгдэнэ Шийдэл хайлтын үр дүн(Шийдвэрлэлтийн үр дүн), шийдэл олдсон тухай мэдээлдэг (Зураг 3). Цагаан будаа. 2. Шийдэл хайж байна Цагаан будаа. 3. Шийдлийн эрэл хайгуулын үр дүн Програм ашиглан асуудлын геометрийн шийдэл MATHCAD 2000. 14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70 7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49 x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34 10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C Цагаан будаа. 4. (x, y) → (20, 14) олох f(x, y): = 10x + 5y fmin := f(20, 14) Програмыг ашиглан асуудлын аналитик шийдэл MATHCAD 2000. MathCAD дахь асуудлын аналитик шийдэл нь илүү хялбар байдаг. Z(x, y): = 10x + 5y 14x + 5x ≤ 360 M:=Том болгох(z,x,y) M=(20,14)Z(M0,M1)=270 Сөрөг чөлөөт коэффициент байгаа тохиолдолд шугаман функцийг нэмэгдүүлэх асуудал Шугаман функцийн хамгийн ихийг ол хязгаарлалт дор X1 – X2 ≤ 3, 2X1 – 3X2 ≤ 6, X1 ≥ 0, X2 ≥ 0. Бид системийг маягтаар бичдэг Y1 = -X1 + X2 + 3 ≥ 0 Y2 = X1 + X2 - 5 ≥ 0 Y3 = -2X1 + 3X2 + 6 ≥ 0 Y4 = -X2 + 6 ≥ 0 Ширээ хийцгээе. Сөрөг элемент арилаагүй тул бид 2-р эгнээтэй үргэлжлүүлэн ажиллаж байна. Бид SHMZhI-ийг шийдвэрлэх элемент -2-оор хийдэг. Бид ширээ авдаг. Шугаман функцийг багасгах асуудал Шугаман функцийг хамгийн их болгох асуудалд багасгах асуудлыг багасгах Шугаман функцийн максимумыг олох асуудлын шийдлийг симплекс аргаар авч үзсэн W = c1 x1 + c2 x2 + … + cn xn. Гэсэн хэдий ч эдийн засгийн олон асуудалд шугаман функцийн хамгийн бага утгыг олох шаардлагатай байдаг. Үүний тулд үүнийг тавихад хангалттай W = -Z = -c1 x1 - c2 x2 - ... - cn xn зохих хязгаарлалтын дор үүссэн W функцийг хамгийн их байлгах асуудлыг шийднэ. Энэ нь тодорхой болохоор Шугаман функцийг багасгах хязгаарлалтыг биелүүлэхийн зэрэгцээ 7X1 + 2X2 ≥ 14, 5X1 + 6X2 ≤ 30, 3X1 + 8X2 ≥ 24, X1 ≥ 0, X2 ≥ 0. (Зураг 5) дээрх асуудлын геометрийн шийдэл ба энэ нь цэг дэх оновчтой шийдэлтэй тохирч байна C (48/11, 15/11) ба нэгэн зэрэг Zmin = -21/11. Зураг 5. Асуудлын геометрийн шийдэл Yi ≥ 0 тэгшлэх хувьсагч ба W = -Z = 2X1 - 5X2 → max функцийг танилцуулж, бид бодлогыг маягт дээр бичнэ. Y1 = 7X1 + 2X2 - 14, Y2 = -5X1 - 6X2 + 30, Y3 = 3X1 + 8X2 - 24, Бид энэ системийг хүснэгт хэлбэрээр бичдэг. Бид Y1 - мөрөнд сөрөг чөлөөт гишүүнээс салж, "-50/8" шийдвэрлэх элементтэй SHMZhI хийж, хүснэгтийг авна. W - эгнээ болон 1 - баганад сөрөг элемент байхгүй тул бид оновчтой шийдлийг авсан X1 = 48/11, X2 = 15/11, Wmax - 21/11 эсвэл Zmin = -Wmax = -21/11 , Практик хэсэг 1.
Симплекс аргыг ашиглан асуудлыг шийд. X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → хамгийн их Шийдэл X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0 X1 + X2 + X4 = 150 Хариулт: X1 = 75; X2 = 75; X3 = 0; X4 = 0. Даалгаврын дугаар 1. Тус компани нь хоёр төрлийн бүтээгдэхүүн үйлдвэрлэдэг. Түүхий эд материалын төрөл, тэдгээрийн нөөц, нэг c.u-д ногдох түүхий эдийн хэрэглээний хэмжээ. бүтээгдэхүүний төрөл тус бүр, бүтээгдэхүүний борлуулалтаас олсон ашгийг хүснэгтэд үзүүлэв. Шийдэл 2X1 + 2X2 ≤ 17 X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0 2X1 + X2 + X4 = 10 2X1 + 2X2 + X5 =17 Хариулт: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7. Даалгаврын дугаар 2. Тус компани гурван төрлийн түүхий эдийг ашиглан гурван төрлийн бүтээгдэхүүн үйлдвэрлэдэг. Түүхий эдийн нөөц, тэдгээрийн хэрэглээний хэмжээ, бүтээгдэхүүн бүрийн борлуулалтаас олсон ашгийг хүснэгтэд үзүүлэв. Аж ахуйн нэгжийн ашиг хамгийн их байхын тулд үйлдвэрлэлийг хэрхэн төлөвлөх ёстой вэ? Шийдэл 2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → хамгийн их 5X1 + 3X2 ≤ 900 2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0 X1 + X2 + X5 = 250 5X1 +3X2 + X6 = 900 X1 + 3X2 ≤ 20 F = 2X1 + X2 → хамгийн их 2X1 + 2X2 ≤ 17 (-1/3)(-1/3)(2/3) Хариулт: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5. Дүгнэлт Симплекс аргын хамгийн энгийн тайлбарууд дээр анхаарлаа хандуулцгаая. Симплекс аргын алгебрийн утга нь ижил алгебрийн хувиргалтыг хийснээр бид нэг боломжит шийдээс нөгөө алгебрийн тэгшитгэлийн систем рүү шилжиж, асуудлын оновчтой шийдэлд хүрдэг. Геометрийн үүднээс авч үзвэл симплекс аргын дагуу ижил төстэй хувиргалтууд нь гүдгэр уусмалын олон өнцөгтийн нэг оройноос хөрш зэргэлдээх, түүнээс дараагийнх, мөн энэ олон өнцөгтийн хажуугийн дагуух оновчтой орой руу дараалан шилжих хөдөлгөөн юм. . Симплекс аргын эдийн засгийн мөн чанар нь шийдлийг дараалан сайжруулах арга юм. Энэ арга нь үйл ажиллагааны үндсэн төлөвлөгөө болох эхлэлийн цэгийг сонгосны дараа аажмаар урагшилж, эцсийн дүндээ оновчтой төлөвлөгөөнд хүрэх боломжийг олгодог. Симплекс гэдэг нь n хэмжээст орон зайд нэг гипер хавтгайд ороогүй n + 1 оройтой гүдгэр олон өнцөгт хэлбэр юм. Симплекс нь n хэмжээст орон зайн эзэлхүүнийг агуулсан хамгийн энгийн олон өнцөгт учраас симплексийг тусдаа ангид хуваадаг. Хэрэв оновчтой шийдэл байгаа бол түүнийг хязгаарлагдмал тооны алхмуудын дараа заавал олох болно ("унадаг дугуй" гэх мэт олон тооны өгөөжтэй "муухай асуудал" гэж нэрлэгддэг асуудлаас бусад нь батлагдсан. ижил байрлалд, боломжтой). Шугаман програмчлал нь хувьсагчдын хоорондын шугаман хамаарлаар тодорхойлогддог экстремаль асуудлыг шийдвэрлэх онол, аргад зориулагдсан математик програмчлалын салбар юм. Математик програмчлал (оновчтой програмчлал) нь шугаман програмчлал, динамик програмчлал, гүдгэр програмчлал гэх мэт математикийн янз бүрийн арга, салбаруудыг нэгтгэсэн математикийн салбар юм. функц, хувьсагчдын утгууд нь хүлээн зөвшөөрөгдсөн утгын зарим мужид хамаарах ёстой. Ашигласан уран зохиолын жагсаалт 1) А.С.Шапкин, Н.П.Мазаева; Математикийн арга, судалгааны загвар үйл ажиллагаа, 2005. 2) Н.Ш. Кремер, Б.А.Путко, И.М. Тришин, М.Н. Фридман; Үйл ажиллагааны судалгаа эдийн засаг. - ЮНИТИ, 2002. Үзүүлэнг урьдчилан үзэхийг ашиглахын тулд Google акаунт (бүртгэл) үүсгэн нэвтэрнэ үү: https://accounts.google.com Шугаман програмчлалын хамгийн энгийн бодлогуудыг график аргаар шийдвэрлэх нь 2012.04.17. Хэрэв шугаман програмчлалын бодлогын хязгаарлалтын системийг хоёр хувьсагчтай шугаман тэгш бус байдлын системээр дүрсэлсэн бол ийм асуудлыг геометрийн аргаар шийдэж болно. Даалгавар. Радио релений 14 суваг (RRC), тропосферийн 9 суваг байдаг. Тэдгээр дээр A, B, C гэсэн 3 төрлийн мэдээллийг шилжүүлэх шаардлагатай. Түүнээс гадна А мэдээлэл 600 ам. доллар, В - 3000 ам. доллар, С - 5500 ам.доллартай тэнцэнэ. (Мэдээллийг утсаар ярих тоо, өгөгдөл дамжуулах гэх мэтээр ойлгож болно). Суваг тус бүрийн сувгийн боломж, засвар үйлчилгээний зардлыг хүснэгтэд үзүүлэв. Ашиглалтын зардал хамгийн бага байхын тулд шаардлагатай мэдээллийг дамжуулахад шаардлагатай хоёр төрлийн холбогдох сувгуудын тоог олох шаардлагатай. Мэдээллийн төрөл Харилцаа холбооны суваг Шаардлагатай мэдээллийн хэмжээ, c.u. Tropospheric RRS A 80 40 600 V - 1000 3000 C 300 800 5500 Нэг сувгийн засвар үйлчилгээний зардал, урэх. 3000 2000 ХХК-ийг шийдвэрлэх үе шатууд: ODR-ийг бий болгох. ODR - (c 1 ;c 2) -д хамаарах X 0 ямар нэгэн цэгт зорилгын функцийн градиент векторыг байгуул. c 1 x 1 + c 2 x 2 = h шулууныг байгуул, h нь дурын эерэг тоо, зурсан шугам нь уусмалын олон өнцөгтийг дайран өнгөрвөл зохимжтой. Олдсон шугамыг градиент векторын чиглэлд мөр нь ODR-ээс гарах хүртэл (хамгийн ихийг хайх үед) эсвэл эсрэг чиглэлд (минимумыг хайх үед) өөртэйгөө параллель шилжүүлнэ. Хязгаарын цэг дээр зорилгын функц нь хамгийн дээд цэгт (хамгийн бага) хүрдэг, эсвэл шийдлийн багц дээр функцийн хязгааргүй байдал тогтоогддог. Функцийн хамгийн их (хамгийн бага) цэгийн координатыг тодорхойлж, энэ цэг дэх функцийн утгыг тооцоол. Энэхүү боловсруулалтыг 9-р ангийн "Хоёр хувьсагчтай тэгш бус байдлын системүүд" сэдэвт ерөнхий хичээл (алгебр 9, Теляковский найруулсан) болон 10-р ангид энэ сэдвээр давтан хичээл болгон ашиглаж болно. ... Материал нь ахисан түвшний оюутнуудад зориулагдсан болно. Энэхүү програм нь үндсэн болон лавлагааны графикийг янз бүрийн аргаар эмхэтгэх, оновчтой шийдлийг олох алгоритмыг авч үздэг ... "Шугаман програмчлалын асуудлууд" сэдвээр математикийн хичээлд зориулсан ажлын номыг ижил нэртэй математикийн хичээлд (ахисан түвшний) зориулж боловсруулсан. хичээл, семинарт хоёуланд нь ашиглаж болно ... Тодорхойгүй байдлын дор шийдвэр гаргах Эхний хичээл нь m стратеги, хоёр дахь нь n стратегитай бол бид m x n тоглоомтой харьцаж байна гэж хэлнэ. m x n тоглоомыг авч үзье. Стратегийн багцыг өгье: эхний тоглогчийн хувьд (Аi), хоёр дахь тоглогчийн хувьд (Bj), өгөөжийн матриц, энд aij нь эхний тоглогчийн ашиг эсвэл хоёр дахь тоглогч Аi болон стратегийг сонгохдоо алдсан алдагдал юм. Bj, тус тус. Тоглогч бүр өөр өөр стратеги сонгох магадлал өндөр байдаг. шийдлийг сонгохдоо цэвэр стратегийг ашигладаг. Энэ тохиолдолд тоглоомын шийдэл нь цэвэр стратеги байх болно. Тоглогчдын ашиг сонирхол эсрэгээрээ байдаг тул эхний тоглогч ашиг орлогоо нэмэгдүүлэхийг эрмэлздэг бол хоёр дахь тоглогч эсрэгээрээ алдагдлаа багасгахыг хичээдэг. Тоглоомын шийдвэр нь тоглогч бүрийн хамгийн сайн стратегийг тодорхойлох явдал юм. Нэг тоглогчийн хамгийн сайн стратегийг сонгох нь хоёр дахь тоглогчийн гаргасан шийдвэрийн талаархи мэдээлэл бүрэн байхгүй тохиолдолд хийгддэг.
Шугаман програмчлал
ТХГН-т бууруулсан ажлуудын жишээ.
1. Нөөцийг оновчтой хуваарилах даалгавар.
Жишээ
Жишээ 2
Шийдэл
Холимог асуудал.
Хүснэгт
Шийдэл
Бодлогын эдийн засаг-математик загвар.
Таслах даалгавар
LP-ийн гол үүрэг
Слайдын тайлбар:
Сэдвийн талаар: арга зүйн боловсруулалт, танилцуулга, тэмдэглэл
Ачааж байна...