Шугаман програмчлалын загвар
1 Загварын математик тайлбар шугаман програмчлал
2 Шугаман програмчлалын загварыг хэрэгжүүлэх арга
3 Хос шугаман програмчлалын бодлого
Шугаман програмчлалын загварХэрэв судалж буй системд (объект) хувьсагч болон зорилгын функцэд хязгаарлалт байгаа бол (LP) үүсдэг. шугаман.
LP загварыг хоёр үндсэн төрлийн хэрэглээний асуудлыг шийдвэрлэхэд ашигладаг.
1) хүний үйл ажиллагааны аль ч салбарт - нийгэм, эдийн засаг, шинжлэх ухаан, техникийн болон цэргийн оновчтой төлөвлөлт. Жишээлбэл, үйлдвэрлэлийн оновчтой төлөвлөлтөөр: санхүүгийн, хөдөлмөрийн болон бусад нөөцийг хуваарилах, түүхий эдээр хангах, бараа материалын менежмент гэх мэт.
2) тээврийн асуудал (янз бүрийн төрлийн тээврийн оновчтой төлөвлөгөөг олох, янз бүрийн зориулалтаар объектуудад янз бүрийн хэрэгслийг хуваарилах оновчтой төлөвлөгөө гэх мэт).
Шугаман ПРОГРАМЧЛАЛЫН ЗАГВАРЫН МАТЕМАТИК ТОДОРХОЙЛОЛТ
Та хувьсагчийн сөрөг бус утгыг олох хэрэгтэй
тэгш ба тэгш бус байдлын хэлбэрийн шугаман хязгаарлалтыг хангах
,
Хаана 
- өгсөн тоо,
шугаман зорилгын функцийн экстремумыг өгнө
,
хэлбэрээр бичигдсэн өгөгдсөн тоонууд хаана байна
Хүчин төгөлдөр шийдэлямар ч цуглуулга гэж нэрлэдэг 
, нөхцөлийг хангаж байна.
Боломжит шийдлүүдийн хүрээ- боломжтой бүх шийдлүүдийн багц.
Хамгийн оновчтой шийдэл 
, Үүний төлөө 
.
Тэмдэглэл
1. Өгөгдсөн LP загвар нь ерөнхий. Мөн түүнчлэн СтандартТэгээд каноник LP загваруудын хэлбэрүүд.
2. Орших нөхцөл LP загварын хэрэгжилт:
- боломжтой шийдлүүдийн багц хоосон биш;
- зорилгын функц 
хязгаарлагдмал (хамгийн дээдийг хайх үед доод тал нь дээрээс, доод хэмжээг хайх үед доороос).
3.LP нь хоёр теорем дээр суурилдаг
Теорем 1. Цөөн хэдэн Гхэлбэрийн хязгаарлалтын системээр тодорхойлогддог гүдгэр хаалттай багц ( гүдгэр олон өнцөгтбулангийн цэгүүдтэй - оргилууд.)
Теорем 2.
Шугаман хэлбэр 
, гүдгэр олон өнцөгт дээр тодорхойлогдсон
j=1,2,…,с
i=s+1,s+2,…, м,
Энэ олон өнцөгтийн оройн аль нэгэнд экстремумд хүрдэг.
Энэ теоремыг шугаман хэлбэрийн экстремумын теорем гэж нэрлэдэг.
Вейерштрассын теоремын дагуу оновчтой шийдэл нь өвөрмөц бөгөөд дэлхийн экстремум юм.
Ерөнхий аналитик арга байдаг LP загварыг хэрэгжүүлэхэд - симплекс арга. Шугаман програмчлалын асуудлыг шийдвэрлэхэд ихэнхдээ шийдэл байдаггүй. Энэ нь дараах шалтгааны улмаас тохиолддог.
Эхний шалтгааныг жишээгээр тайлбарлая
Энэ шалтгааны улмаас хязгаарлалт нь нийцэхгүй байна гэж тэд хэлж байна. Боломжит шийдлүүдийн бүс нь хоосон багц юм.
Хоёрдахь шалтгааныг дараах жишээгээр харуулав.
Энэ тохиолдолд боломжит шийдлүүдийн хүрээ нь дээрээс хязгаарлагдахгүй. Боломжит шийдлүүдийн хүрээ хязгаарлагдахгүй.
Шугаман програмчлалын уламжлалыг дагаж бид LP асуудлыг эдийн засгийн тайлбарыг өгөх болно. Бидний мэдэлд өгье мнөөцийн төрөл. Нөөцийн төрөл jтэнцүү байна. Эдгээр нөөц нь үйлдвэрлэлд шаардлагатай nбарааны төрөл. Эдгээр барааны тоо хэмжээг тэмдэгээр тэмдэглэе 
тус тус. Нэгжийн төрөл бизардал . Барааны төрөл үйлдвэрлэл биүнэт зүйлсээр хязгаарлагдах ёстой 
тус тус. Бүтээгдэхүүний төрлийн нэгжийг үйлдвэрлэхэд бинөөцийн төрөл зарцуулагдаж байна j. Бүтээгдэхүүн үйлдвэрлэх ийм төлөвлөгөөг тодорхойлох шаардлагатай байна ( 
) ингэснээр тэдний нийт зардал хамгийн бага байх болно.
Бодит объектуудын үйл ажиллагааг оновчтой болгоход ашигладаг шугаман програмчлалын асуудлууд нь олон тооны хувьсагч, хязгаарлалтуудыг агуулдаг. Энэ нь график аргыг ашиглан тэдгээрийг шийдвэрлэх боломжгүй болгодог. Олон тооны хувьсагч, хязгаарлалттай үед алгебрийн аргуудыг ашигладаг бөгөөд энэ нь давтагдах тооцооллын процедур дээр суурилдаг. Шугаман програмчлалд анхан шатны хэрэгжих боломжтой шийдийг бүтээх арга, нэг давталтаас нөгөөд шилжих нөхцлөөр ялгаатай алгебрийн олон аргуудыг боловсруулсан. Гэсэн хэдий ч эдгээр бүх аргууд нь ерөнхий онолын зарчмууд дээр суурилдаг.
Онолын үндсэн зарчмуудын нийтлэг байдал нь шугаман програмчлалын асуудлыг шийдвэрлэх алгебрийн аргууд нь бие биетэйгээ ихээхэн төстэй байдаг. Ялангуяа тэдгээрийн бараг аль нь ч шугаман програмчлалын асуудлыг стандарт (каноник) хэлбэрт шилжүүлэхийг шаарддаг.
LP асуудлыг шийдэх алгебрийн аргууд нь үүнийг багасгахаас эхэлдэг стандарт (каноник) хэлбэр:
,
,
би=1,..,n;j=1,..,м.
Шугаман програмчлалын аливаа асуудлыг стандарт хэлбэрт оруулж болно. Ерөнхий загварыг каноник загвартай харьцуулах нь LP асуудлыг стандарт хэлбэрт оруулахын тулд нэгдүгээрт, тэгш бус байдлын системээс тэгш байдал руу шилжих, хоёрдугаарт, бүх хувьсагчдыг хувиргах шаардлагатай гэж дүгнэх боломжийг олгодог. сөрөг бус байна.
Тэгш бус байдлын хязгаарлалтын зүүн талд сөрөг бус үлдэгдэл хувьсагчийг нэмж, зүүн талаас сөрөг бус үлдэгдэл хувьсагчийг хасах замаар тэгш бус байдалд шилжинэ. Жишээлбэл, тэгш бус байдал 
стандарт хэлбэрт шилжих үед энэ нь тэгш байдал руу хувирдаг 
, тэгш бус байдал 
- тэгш байдал руу 
. Энэ тохиолдолд үлдэгдэл хувьсагч ба илүүдэл хувьсагч хоёулаа сөрөг биш байна.
Тэгш бус байдлын баруун тал нь сөрөг биш гэж үздэг. Үгүй бол тэгш бус байдлын хоёр талыг "-1"-ээр үржүүлж, тэмдгийг нь эсрэгээр нь өөрчлөх замаар үүнийг хийж болно.
Хэрэв шугаман програмчлалын анхны бодлогод хувьсагч нь тэмдгээр хязгаарлагдахгүй бол түүнийг сөрөг бус хоёр хувьсагчийн зөрүүгээр илэрхийлж болно. 
, Хаана 
.
Хувьсагчийн чухал шинж чанар 
Боломжит аливаа шийдлийн хувьд зөвхөн нэг нь эерэг утгыг авч чадна. Энэ нь хэрэв гэсэн үг 
, Тэр 
мөн эсрэгээр. Тиймээс үүнийг үлдэгдэл гэж үзэж болно - илүү хувьсагч гэж үзэж болно.
ЖишээШугаман програмчлалын бодлогыг дараах байдлаар өгье.
,
.
Үүнийг стандарт хэлбэрт оруулах шаардлагатай. Анхны асуудлын эхний тэгш бус байдал нь тэмдэгтэй тул үлдэгдэл хувьсагчийг оруулах шаардлагатай гэдгийг анхаарна уу. Үүний үр дүнд бид авдаг.
Хоёр дахь тэгш бус байдал нь тэмдэгтэй бөгөөд стандарт хэлбэрт шилжүүлэхийн тулд илүүдэл хувьсагчийг оруулах шаардлагатай бөгөөд энэ үйлдлийг гүйцэтгэсний дараа бид .
Үүнээс гадна хувьсагч нь тэмдгээр хязгаарлагдахгүй. Тиймээс зорилгын функц болон хязгаарлалтын аль алинд нь ялгаагаар солигдох ёстой 
. Орлуулалтыг хийсний дараа бид анхны бодлоготой тэнцэх шугаман програмчлалын бодлогыг стандарт хэлбэрээр олж авна.
.
Стандарт хэлбэрээр бичигдсэн шугаман програмчлалын бодлого нь системийн шийдэл болох векторуудын багц дээрх зорилгын функцийн экстремумыг олох бодлого юм. шугаман тэгшитгэлсөрөг бус байх нөхцлийг харгалзан. Мэдэгдэж байгаагаар шугаман тэгшитгэлийн систем нь шийдэлгүй, нэг шийдэлтэй эсвэл хязгааргүй тооны шийдтэй байж болно. Зорилгын функцийг оновчтой болгох нь зөвхөн системтэй тохиолдолд л боломжтой юм хязгааргүй байдаголон шийдэл. Шугаман тэгшитгэлийн систем нь тууштай байвал (үндсэн матрицын зэрэглэл нь өргөтгөсөн зэрэгтэй тэнцүү), үндсэн матрицын зэрэглэл нь тооноос бага бол хязгааргүй тооны шийдлүүдтэй байдаг. үл мэдэгдэх.
Хязгаарлалтын системийн матрицын зэрэглэлийг тэнцүү болго м. Энэ нь матрицад дор хаяж нэг минор байна гэсэн үг мдараалал нь тэгтэй тэнцүү биш байна. Ерөнхий байдлыг алдалгүйгээр бид насанд хүрээгүй нь матрицын зүүн дээд буланд байрладаг гэж үзэж болно. Үүнд хувьсагчдын дугаарлалтыг өөрчлөх замаар үргэлж хүрч болно. Энэ нь тэг биш бага зэрэг цолтой михэвчлэн үндсэн гэж нэрлэдэг. Анхнаасаа л систем бүтээцгээе мсистемийн тэгшитгэлийг дараах байдлаар бичнэ.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Хамгийн энгийн нь шугаман детерминистик загвар гэж нэрлэгддэг загварууд юм. Эдгээр нь хяналтын хувьсагчдын шугаман хэлбэрээр тодорхойлогддог ( X):
W=a 0 + а 1 x 1 + … + a k x k
хэлбэрийн шугаман хязгаарлалтын дор
б 1 j x 1 + б 2 j x 2 + … + b kj x k ³ б ж , j = 1,…, q 1 ;
в 1 j x 1 + в 2 j x 2 + … + c kj x k = в ж , j = 1,…, q 2 ;
г 1 j x 1 + г 2 j x 2 + … + d kj x k £ d j , j = 1,…, q 3 .
Хязгаарлалтын нийт тоо m = q 1 + q 2 + q 3 хувьсагчийн тооноос хэтэрч болно (м> к). Үүнээс гадна хувьсагчид эерэг байх нөхцөлийг ихэвчлэн нэвтрүүлдэг ( x i ³ 0).
Шугаман загварын хариуны гадаргуу нь гиперплан. Жишээлбэл, дараах хэлбэрийн хоёр хувьсагчтай шугаман загварыг авч үзье.
W=–2x 1 –3x 2 (2.2)
дараах хязгаарлалтын дагуу
|
x 1 – 4x 2 £4;
–2x 1 + x 2 £ 2;
X 1 ³ 0; x 2 ³ 0.
Зөвшөөрөгдөх утгуудын хүрээ (тодорхойлолтын домэйн) OABCDЗагварын хувьд (2.2) хязгаарлалт (2.3) -аар үүсгэгддэг (Зураг 2.2). Хариултын гадаргуу нь хавтгай олон өнцөгт юм OA"B"C"D"(Зураг 2.2, б).
Хязгаарлалтын тодорхой харьцааны хувьд боломжит шийдлүүдийн багц байхгүй (хоосон) байж болно. Ийм багцын жишээг Зураг дээр үзүүлэв. 2.3. Шууд АСТэгээд НарДээрхээс хүлээн зөвшөөрөгдөх утгуудын хүрээг хязгаарлах. Гурав дахь хязгаарлалт нь зөвшөөрөгдөх утгын хүрээг шулуун шугамын доороос тасалдаг AB.Тиймээс гурван хязгаарлалтыг хангасан ерөнхий бүс байхгүй.
Шугаман загварууд нь маш энгийн байдаг тул нэг талаас асуудлыг ихээхэн хялбаршуулж, нөгөө талаас энгийн, энгийн загваруудыг боловсруулах боломжийг олгодог. үр дүнтэй аргуудшийдлүүд.
DLA-г судлахдаа шугаман загварыг бараг ашигладаггүй бөгөөд бараг зөвхөн асуудлын ойролцоо тайлбарт ашигладаг.
Шугаман загваруудыг шугаман бус загваруудыг алхам алхмаар ойртуулахад ашиглаж болно (асуудлыг шугаман болгох). Энэ техник нь судалж буй орон зайн жижиг хэсгүүдийг судлахад онцгой үр дүнтэй байдаг. Шугаман бус хариу урвалын гадаргуугийн салангид хэсгүүдийг шугаман загвараар дүрслэх нь шугаман тактик бүхий аргууд гэж нэрлэгддэг оновчлолын аргын томоохон бүлэгт суурилдаг.
Шугаман загварыг судлах нь хэцүү биш юм. Ялангуяа хувьсагч бүрийн нөлөөлөл нь маягтын загварын шинж чанарт нөлөөлдөг
W=a 0 + а 1 x 1 + а 2 x 2 + …+ a k x k
түүний коэффициентээр тодорхойлно:
, би = 1,…, к.
Шугаман загварын хамгийн оновчтойг олох ВҮр дүнтэй симплекс аргыг боловсруулсан.
Гарсан зардлын багц гэж үздэг хамгийн энгийн зардлын загварууд заримдаа шугаман болж буурдаг.
Ийм загварын жишээ бол сонгодог юм тээврийн зардлын загвар (тээврийн асуудал)(Зураг 2.4).
Боломжтой күйлдвэрлэлийн цэгүүд
(би = 1,…, к) Мөн мхэрэглээний цэгүүд
(j = 1,…, м) зарим бүтээгдэхүүний. Тус бүрд үйлдвэрлэсэн бүтээгдэхүүний хэмжээ күйлдвэрлэлийн оноо тэнцүү байна a i; тус бүрд шаардагдах бүтээгдэхүүний тоо хэмжээ мхэрэглээний оноо тэнцүү байна б ж.
Нийт үйлдвэрлэл, хэрэглээний тэгш байдлыг дараахь байдлаар тооцно.
-аас тээвэрлэж буй бүтээгдэхүүний тоо хэмжээ бидахь үйлдвэрлэлийн цэг jхэрэглээний цэг нь тэнцүү байна x ij; Энэ бүтээгдэхүүний нэг нэгжийг тээвэрлэх зардал - ij-тэй.
Тээврийн нийт зардал ХАМТ S өгөгдсөн шугаман загвар:
дараах хязгаарлалтын дагуу
Шугаман загварт мөн шугаман дифференциал тэгшитгэл (ердийн эсвэл хэсэгчилсэн дериватив) хэлбэрийн загварууд орно.
Шугаман энгийн дифференциал тэгшитгэл n-р захиалга нь маягттай
Анхны нөхцөлийг дараах байдлаар бичнэ
Шугаман хэсэгчилсэн дифференциал тэгшитгэл нь хэлбэртэй байна
Хэсэгчилсэн дифференциал тэгшитгэл гэж тодорхойлсон загвар нь анхны ба хилийн нөхцөл(F функцийн тодорхойлолтын домэйны хил дээрх нөхцөл т)).
2.3. Protozoa судалгаа математик загвар
хийн турбин хөдөлгүүрийн ажиллагаа
Хийн турбин хөдөлгүүр (GTE) нь орчин үеийн нисэх онгоцны гол цахилгаан станц юм.
Хийн турбин хөдөлгүүрийн хэлхээ нь Зураг дээр үзүүлсэн хэлбэртэй байна. 2.5.
 |
Энд 1
- оролтын диффузор; 2
- компрессор; 3
- шатаах камер; 4
- турбин;
5
- гаралтын цорго.
Хийн турбин хөдөлгүүрийн үйл ажиллагааны мөчлөг нь дараахь үе шатуудыг агуулна.
1) Хурдтай гүйх ВДиффузороор дамжин өнгөрөх агаарын урсгал нь компрессор руу ордог.
2) Турбинтай ижил босоо тэнхлэг дээр эргэлддэг компрессор нь шаталтын камерт орж буй агаарыг шахдаг.
3) Шатаах камерт түлш (керосин) байнга шахагддаг бөгөөд энэ нь шахсан агаартай холилддог.
4) Шаталтын улмаас үүссэн хий нь турбин руу ордог бөгөөд энэ нь түүнийг хурдасгахад хүргэдэг В.
5) Энэ хурдаар хий нь цоргооор дамжин агаар мандалд ордог.
Үүний улмаас В > В, татах хүч үүсдэг Р, энэ нь агаарын хөлөг агаар мандалд нисэх боломжийг олгодог.
Хөдөлгүүрийн хяналтын савааг (EC) хөдөлгөж шатаах камерт түлш шахах хурдыг өөрчлөх замаар түлхэлтийн хүчийг өөрчилдөг. Нислэгийн үед өөрөө явагч бууны дохиогоор тохируулагчийг гараар эсвэл идэвхжүүлэгчийн тусламжтайгаар тохируулагчийн тодорхой өнцөгт шилжүүлдэг. Тохируулагч d утгыг нэмэгдүүлэх нь хүчийг нэмэгдүүлэхэд хүргэдэг Р, мөн буурах нь энэ хүчний бууралт юм.
GTE бол нарийн төвөгтэй юм техникийн систем, үүнд ихээхэн хэмжээний физик, химийн процесс явагддаг. Хөдөлгүүр нь бүх төрлийн автоматжуулалтын төхөөрөмж, турбины ирийг эргүүлэх, хөргөх систем гэх мэт тоноглогдсон. Байгалийн, математик тайлбарХийн турбин хөдөлгүүрийн ажиллагаа нь хэсэгчилсэн дифференциал тэгшитгэл, энгийн дифференциал тэгшитгэл, трансцендентал функц, алгоритм зэрэг нэлээд төвөгтэй байх болно. тоон системхөдөлгүүрийн хяналт. Ийм загварыг хийн турбин хөдөлгүүрийн дизайны процесст ашигладаг.
Нислэгийн удирдлагын асуудлыг шийдвэрлэхийн тулд түлхэлтийн хүчний хамаарлыг илэрхийлдэг хийн турбин хөдөлгүүрийн илүү энгийн загварыг ашигладаг. Р d өнцгөөс тохируулагч тохируулагч хазайлт. Татах хүчийг өөрчлөх үйл явцыг ердийн дифференциал тэгшитгэлээр дүрсэлсэн болно.
, (2.11)
Энд t > 0 нь хөдөлгүүрийн цагийн тогтмол хэмжээ бөгөөд энэ нь дизайны шинж чанараас гадна орчны температур, чийгшил болон бусад гадаад хүчин зүйлээс хамаарна; к[кг/град] – пропорциональ коэффициент.
(2.11) тэгшитгэлийн анхны нөхцөлийг дараах байдлаар бичнэ
Р(0) = Р 0 . (2.12)
Иймд (2.11) тэгшитгэлийн хамт анхны нөхцөл(2.12) байна энгийн дифференциал тэгшитгэл хэлбэрээр бичигдсэн хийн турбин хөдөлгүүрийн үйл ажиллагааны хамгийн энгийн математик загвар 1--р захиалга.
Пропорциональ байдлын коэффициентийг тодорхойлох кТуршилтын өгөгдлийн үндсэн дээр бүтээгдсэн жолооны өнцгөөс түлхэлтийн хамаарлын тохируулгын графикийг ашигладаг. Графикийн налуугийн тангенс нь хүссэн коэффициенттэй тэнцүү байна.
 |
(2.11) тэгшитгэлийг анхны нөхцөлтэй (2.12) нэгтгэх нь түлхэлтийн хүч цаг хугацааны явцад хэрхэн өөрчлөгдөж байгааг олж мэдэх боломжийг олгодог (Зураг 2.6).
тохируулагч хазайсан үед түлхэлт Рнэмэгдэж, дараа нь тодорхой хязгаарын утгаар тогтворждог, i.e. Хийн турбин хөдөлгүүр нь инерцийн объект юм.
Хүч татах хүчний хязгаар(2.11)-ээс түүний өөрчлөлтийн хувь нь тэг байх үед бид дараахь зүйлийг олж авна.
. (2.13)
Өсөх хугацаамоторын цагийн тогтмол t-ийн утгаас хамаарна. Энэ үйл явц нь тогтвортой гэж тооцогддог t = tам, түлхэлт нь түлхэлтийн хүчний хамгийн их утгын таван хувийн коридорт орох үед (Зураг 2.6). t их байх тусам хөдөлгүүр илүү инерцитэй байдаг тул илүү их байдаг там
Зураг дээр. t = 0.5 үед тохируулагч хазайлтын өнцгөөс хамааран зүтгүүрийн хүчний үйлдлийг Зураг 2.7-д үзүүлэв.
Хөөрөх үеийн түлхэлтийн хүч нь тохируулагчийг 10°-аар хазайлгахад гурав дахь секундэд тогтвортой байдалд хүрч, 3390 кг-д хүрдэг. Хөөрснөөс хойш 10 секундын дараа тохируулагчийг 20° хазайхад түлхэх хүчийг 6780 кг, арван секундын дараа 30° хазайхад түлхэх хүчийг 10170 кг болгож тохируулдаг. Татах хүчний хязгаарлах утга нь
14270 кг.
Холбогдох мэдээлэл.
Практикт шугаман програмчлалын асуудлын хязгаарлалтыг ихэвчлэн тэгшитгэлээр бус харин тэгш бус байдлаар тодорхойлдог.
Тэгш бус байдлын хязгаарлалттай бодлогоос шугаман програмчлалын үндсэн бодлого руу хэрхэн шилжиж болохыг үзүүлье.
Хувьсагчдад тавьсан хязгаарлалтууд нь шугаман тэгш бус байдлын хэлбэртэй байдаг хувьсагчидтай шугаман програмчлалын бодлого байг. Тэдгээрийн заримд нь тэгш бус байдлын тэмдэг нь бусдаас ялгаатай байж болно (хоёр талын тэмдгийг зүгээр л өөрчилснөөр хоёр дахь төрөл нь эхнийх рүү буурдаг). Тиймээс бид бүх тэгш бус байдлын хязгаарлалтыг стандарт хэлбэрээр тавьдаг.
Тэгш бус байдлыг (4.1) хангах сөрөг бус утгуудын багцыг олох шаардлагатай бөгөөд үүнээс гадна шугаман функцийг багасгах болно.
Ийм байдлаар тавьсан асуудлаас шугаман програмчлалын үндсэн асуудал руу шилжихэд хялбар байдаг. Үнэн хэрэгтээ дараахь тэмдэглэгээг танилцуулъя.
Бидний "нэмэлт" гэж нэрлэх зарим шинэ хувьсагч хаана байна. Нөхцөлүүдийн дагуу (4.1) эдгээр нэмэлт хувьсагч нь сөрөг биш байх ёстой.
Тиймээс бид дараахь томъёогоор шугаман програмчлалын асуудалтай тулгараад байна: тэгшитгэлийн системийг (4.3) хангах хувьсагчдын сөрөг бус утгыг олж, эдгээр хувьсагчдын шугаман функцийг нэгэн зэрэг багасгах.
Таны харж байгаагаар шугаман програмчлалын үндсэн асуудал (LPLP) бидний өмнө цэвэр хэлбэрээр байна. Тэгшитгэл (4.3) нь чөлөөт хувьсагчаар илэрхийлэгдэх үндсэн хувьсагчдын хувьд аль хэдийн шийдэгдсэн хэлбэрээр өгөгдсөн.Нийт хувьсагчийн тоо нь "анхны" болон "нэмэлт"-тэй тэнцүү байна. L функцийг зөвхөн "анхны" хувьсагчид (түүн дэх "нэмэлт" хувьсагчдын коэффициентүүд нь тэгтэй тэнцүү) илэрхийлдэг.
Тиймээс бид тэгш бус хязгаарлалттай шугаман програмчлалын асуудлыг шугаман програмчлалын үндсэн асуудал болгон бууруулсан боловч их тоохувьсагч нь асуудалд анх байснаасаа.
Жишээ 1. Тэгш бус байдлын хязгаарлалттай шугаман програмчлалын асуудал байна: нөхцөлийг хангасан хувьсагчдын сөрөг бус утгыг ол.
ба шугаман функцийг багасгах
Энэ асуудлыг OPLP хэлбэрт оруулах шаардлагатай байна.
Шийдэл. Бид тэгш бус байдлыг (4.4) стандарт хэлбэрт оруулдаг;
Бид нэмэлт хувьсагчуудыг танилцуулж байна:
Даалгавар нь хувьсагчдын сөрөг бус утгыг олох явдал юм
тэгшитгэлийг хангах (4.6) ба шугаман функцийг багасгах (4.5).
Бид тэгш бус байдлын хязгаарлалттай шугаман програмчлалын бодлогоос тэгш байдлын хязгаарлалтын бодлого (ICP) руу хэрхэн шилжиж болохыг харуулсан. Урвуу шилжилт нь үргэлж боломжтой байдаг - OLP-ээс тэгш бус байдлын хязгаарлалттай асуудал хүртэл. Хэрэв эхний тохиолдолд бид хувьсагчдын тоог нэмсэн бол хоёр дахь тохиолдолд бид үүнийг бууруулж, үндсэн хувьсагчдыг устгаж, зөвхөн чөлөөт хувьсагчдыг үлдээх болно.
Жишээ 2. Тэгш байдлын хязгаарлалт (LPLP) бүхий шугаман програмчлалын асуудал байна:
ба багасгах функц
Үүнийг тэгш бус байдлын хязгаарлалттай шугаман програмчлалын бодлого болгон бичих шаардлагатай.
Шийдэл. -ээс хойш бид хоёр хувьсагчийг үнэгүй гэж сонгодог. Хувьсагчдыг чөлөөт гэж сонгох боломжгүй гэдгийг анхаарна уу, учир нь тэдгээр нь тэгшитгэлийн эхнийхтэй холбоотой байдаг (4 7): тэдгээрийн аль нэгнийх нь утга нөгөөгийнх нь утгаар бүрэн тодорхойлогддог ба чөлөөт хувьсагч нь бие даасан байх ёстой.
Үүнтэй ижил шалтгаанаар хувьсагчдыг чөлөөтэй гэж сонгох боломжгүй (тэдгээрийг хоёр дахь тэгшитгэлээр холбосон). Чөлөөт хувьсагчдыг сонгоод бусад бүх зүйлийг түүгээр илэрхийлье.
Нөхцөлүүдийг (4 9) тэгш бус байдлаар сольж болох тул:
Шугаман L функцийн илэрхийллийг чөлөөт хувьсагчдад шилжүүлж, тэдгээрийн илэрхийлэл (4.9)-ийг L-д болон оронд орлуулъя. бид авах болно.
ХОЛБООНЫ БОЛОВСРОЛЫН ГАЗАР
Холбооны улсын боловсролын байгууллага "ПСКОВ БАРИЛГА, ЭДИЙН ЗАСГИЙН коллеж"
"Математикийн арга" сэдэв
Шугаман програмчлалын асуудал
Курсын ажил
315-ПО бүлгийн оюутан
Андреев Дмитрий Александрович
Курсын ажлын дарга
Васильева Наталья Анатольевна
Псков 2009 он
Оршил
I бүлэг Шугаман програмчлал
§ 1 Шугаман програмчлалын бодлогын ерөнхий томъёолол
§ 2 Шугаман програмчлалын бодлогын математик загвар
§ 3 Шугаман програмчлалын бодлогын каноник хэлбэр
Бүлэг ΙΙ Симплекс аргыг ашиглан асуудлыг шийдвэрлэх
§ 1 Асуудлын талаархи мэдэгдэл
§ 2 Бодлогын математик загвар гаргах
§ 3 Симплекс аргыг ашиглан асуудлыг шийдвэрлэх алгоритмууд
§ 4 Гауссын аргыг ашиглан анхан шатны жишиг шийдлийг бүтээх
§ 5 Асуудлын шийдэл
Дүгнэлт
Уран зохиол
Оршил
Одоогийн байдлаар үндэсний эдийн засгийн салбар дахь төлөвлөлт, менежментийн олон асуудлууд, түүнчлэн хувийн хэрэглээний томоохон асуудлуудыг математик програмчлалын аргаар шийдэж байна. Оновчлолын асуудлыг шийдвэрлэх чиглэлээр хамгийн хөгжсөн аргууд бол шугаман програмчлалын аргууд юм. Эдгээр аргууд нь худалдааны эргэлтийг төлөвлөх гэх мэт арилжааны үйл ажиллагааны өргөн хүрээний ажлыг хангалттай нарийвчлалтайгаар дүрслэх боломжийг олгодог; хотын жижиглэнгийн худалдааны сүлжээг байрлуулах; хот, бүс нутагт бараа нийлүүлэх төлөвлөлт; ханган нийлүүлэгчидтэй худалдааны аж ахуйн нэгжүүдийг хавсаргах; барааг оновчтой тээвэрлэх зохион байгуулалт; худалдааны ажилчдыг албан тушаалд хуваарилах; зохистой хоол хүнс худалдан авах ажлыг зохион байгуулах; Нөөцийн хуваарилалт; хөрөнгийн хөрөнгө оруулалтын төлөвлөлт; салбар хоорондын холболтыг оновчтой болгох; арилжааны тоног төхөөрөмжийг солих; хязгаарлагдмал орон зайн нөхцөлд барааны оновчтой нэр төрлийг тодорхойлох; оновчтой ажиллах горимыг бий болгох.
Шугаман програмчлалын бодлогод үр ашгийн шалгуур ба хязгаарлалтын систем дэх функцууд шугаман байна.
Математикийн програмчлалын бодлого нь цаг хугацааны хувьсагчтай, үр ашгийн шалгуурыг цаг хугацааны үйлдлүүдийн урсгалыг тодорхойлсон тэгшитгэлээр илэрхийлдэг бол ийм бодлого нь динамик програмчлалын бодлого юм.
Эдийн засгийн олон загварт тогтмол болон хувьсах хүчин зүйлсийн хоорондын хамаарлыг шугаман гэж үзэж болно.
Арилжааны үйл ажиллагаанд математик програмчлалын аргыг ашиглах нь бизнесмэн, эдийн засагч, санхүүчээс шаардлагатай мэдээллийг цуглуулж, дараа нь математикийн хамт бодлого боловсруулах явдал юм. Математик програмчлалын аргуудыг компьютер дээр стандарт програмын багц хэлбэрээр аль хэдийн хэрэгжүүлсэн байдаг тул тэдгээрт хандах нь ихэвчлэн энгийн, автоматжуулсан бөгөөд ямар нэгэн онцгой бэрхшээл учруулдаггүй.
Дараа нь загварын үйл ажиллагаа нь мэдээллийг цуглуулах, боловсруулах, боловсруулсан мэдээллийг компьютерт оруулах, боловсруулсан хуваарийн хөтөлбөрт үндэслэн тооцоолол хийх, эцэст нь тооцооллын үр дүнг (хэрэглэгчдэд ээлтэй хэлбэрээр) гаргах зэрэг орно. үйлдвэрлэлийн үйл ажиллагаа.
I бүлэг Шугаман програмчлал
§ 1 Шугаман програмчлалын бодлогын ерөнхий томъёолол
Шугаман програмчлал нь математик програмчлалын нэг салбар бөгөөд хэт туйлшралын асуудлыг шийдвэрлэх аргуудыг судалдаг. шугаман хамааралхувьсагч ба шугаман зорилгын функцын хооронд. Шугаман програмчлалын асуудлыг шийдэхийн тулд тухайн асуудлын математик загварыг эмхэтгэж, шийдвэрлэх аргыг сонгодог.
Арилжааны үйл ажиллагааны асуудлын томъёоллыг шугаман програмчлалын математик загвар хэлбэрээр, хэрэв зорилгын функцийг шугаман хэлбэрээр дүрсэлж, хязгаарлагдмал нөөцтэй хамаарлыг шугаман тэгшитгэл эсвэл тэгш бус байдлаар дүрсэлж болно. . Нэмж дурдахад нэмэлт хязгаарлалтыг нэвтрүүлсэн - хувьсагчдын үнэ цэнэ нь сөрөг биш байх ёстой, учир нь тэдгээр нь эргэлт, ашиглалтын хугацаа, зардал болон эдийн засгийн бусад үзүүлэлтүүд зэрэг тоон үзүүлэлтүүдийг илэрхийлдэг.
Эдийн засгийн асуудлын геометрийн тайлбар нь тэдгээрийн бүтцийг төсөөлөх, шинж чанарыг тодорхойлох, илүү нарийн төвөгтэй шинж чанарыг судлах арга замыг нээж өгдөг. Хоёр хувьсагчтай шугаман програмчлалын асуудлыг үргэлж графикаар шийдэж болно. Гэсэн хэдий ч гурван хэмжээст орон зайд ийм шийдэл нь илүү төвөгтэй болж, гурваас дээш хэмжээтэй орон зайд график шийдэл нь ерөнхийдөө боломжгүй юм. Хоёр хувьсагчийн тохиолдол нь ямар ч практик ач холбогдолгүй боловч түүнийг авч үзэх нь шугаман програмчлалын асуудлын шинж чанарыг тодруулж, түүнийг шийдвэрлэх санааг төрүүлж, шийдвэрлэх арга, тэдгээрийг практик хэрэгжүүлэх арга замыг геометрийн хувьд тодорхой болгодог.
§ 2 Шугаман програмчлалын бодлогын математик загвар
Асуудлыг шийдэхийн өмнө бид түүний математик загварыг зохиодог.
Математик загвар нь шугаман зорилгын функц ба хувьсагчийн шугаман хязгаарлалтаас бүрдэх харилцааны багц юм.
Математик загварыг эмхэтгэх зарчим.
1. Даалгаврын хувьсагчдыг сонгоно уу.
Асуудлын хувьсагч нь тоо хэмжээ юм
Энэ нь асуудалд тодорхойлсон эдийн засгийн үйл явцыг бүрэн тодорхойлдог. Ихэвчлэн X = () вектор хэлбэрээр бичдэг 
)
2. Асуудлыг хязгаарлах системийг бий болгох.
Хязгаарлагдмал эдийн засгийн нөхцлөөс улбаатай, асуудлын хувьсагчид хангагдах тэгшитгэл ба тэгш бус байдлын багцыг хязгаарлалтын систем гэнэ.
Ерөнхийдөө систем нь хэлбэрээр бичигдсэн байдаг
3. Зорилгын функцийг тогтоо.
Зорилгын функц нь даалгаврын чанарыг тодорхойлдог Z(X) функц бөгөөд экстремумыг олох ёстой. Ерөнхийдөө зорилгын функцийг Z(X) = гэж бичнэ
Тэр. Математик загвар нь асуудлын хувьсагчдыг олох шиг харагдаж байна
хязгаарлалтын тогтолцоог хангах: 
болон сөрөг бус байдал
0 (j = ), энэ нь Z(Y) = зорилгын функцийн экстремумыг өгдөг
Шугаман програмчлалын асуудлын зөвшөөрөгдөх шийдэл нь хязгаарлалт ба нөхцөлт сөрөг бус байдлын тогтолцоог хангасан хувьсах утгуудын аливаа багц юм.
Зөвшөөрөгдөх шийдлүүдийн багц нь асуудлын зөвшөөрөгдөх шийдлүүдийн хүрээг бүрдүүлдэг (ADP).
Оновчтой шийдэл нь зорилгын функц нь туйлын цэгт хүрсэн асуудлыг шийдвэрлэх боломжтой шийдэл юм.
§ 3 Шугаман програмчлалын бодлогын каноник хэлбэр
Бодлогын математик загвар нь каноник хэлбэртэй байх ёстой.
Хэрэв хязгаарлалтын систем нь зөвхөн тэгшитгэлээс бүрдэх ба бүх хувьсагч нь сөрөг бус нөхцөлийг хангаж байвал асуудал нь канон хэлбэртэй байна.
Хэрэв системд дор хаяж нэг тэгш бус байдал байгаа эсвэл сөрөг биш байх нөхцөлөөр аливаа хувьсагч хязгааргүй байвал асуудал нь стандарт хэлбэртэй байна. Асуудлыг каноник хэлбэрт оруулахын тулд та дараахь зүйлийг хийх хэрэгтэй.
Тэгш бус байдлаас тэгшитгэл рүү дараах байдлаар шилжинэ: тэгш бус байдлын зүүн талд бид тэгш бус байдлын (+1) коэффициент бүхий нэмэлт хувьсагчийг оруулав.
) ба (-1) тэгш бус байдлын хувьд () нэмэлт хувьсагчийг зорилтот сөрөг бус үзүүлэлтээр ногдуулахгүй, дараа нь үүнийг сөрөг бус хоёр хувьсагчийн зөрүүгээр солино, өөрөөр хэлбэл: = – ( 
Каноник хэлбэрийн ерөнхий үзэл бодол:
Бүлэг ΙΙ Симплекс аргыг ашиглан асуудлыг шийдвэрлэх
Симплекс арга нь төлөвлөгөөг (шийдвэрийг) дараалан сайжруулах арга бөгөөд хамгийн үр дүнтэй бөгөөд шугаман програмчлалын аливаа асуудлыг шийдвэрлэхэд ашигладаг.
Аргын нэр нь Латин simplecx - энгийн учираас гаралтай. Эхний хувилбараас эхлэн асуудлыг шийдэх боломжтой шийдлүүдийн бүс нь хамгийн энгийн хэлбэртэй байв. Аргын санааг Оросын математикч Л.В.Контарович санал болгосон. 1939 онд, дараа нь энэ санааг 1949 онд Ж.Данзиг боловсруулж, хөгжүүлсэн.
Симплекс арга нь оновчтой шийдлийг олох эсвэл энэ нь хязгаарлагдмал тооны алхамаар байхгүй гэдгийг батлах боломжийг олгодог.
§ 1 Асуудлын талаархи мэдэгдэл
Үйлдвэрлэлийн процесст Ι, ІΙ, ІΙІ гэсэн 3 төрлийн машин ашигладаг. Үүний зэрэгцээ түүхий эд, хөдөлмөрийн нөөцийг зарцуулж, нэмэлт зардлыг харгалзан үздэг.
Шугаман програмчлалын аливаа бодлогыг каноник хэлбэрийн шугаман програмчлалын бодлого болгон бууруулж болно. Үүнийг хийхийн тулд ерөнхий тохиолдолд та хамгийн их байлгах асуудлыг багасгахын тулд багасгах чадвартай байх хэрэгтэй; тэгш бус байдлын хязгаарлалтаас тэгш байдлын хязгаарлалт руу шилжиж, сөрөг бус нөхцөлийг дагаж мөрддөггүй хувьсагчдыг орлуулах. Тодорхой функцийг нэмэгдүүлэх нь эсрэг тэмдгээр авсан ижил функцийг багасгахтай тэнцүү ба эсрэгээр.
Шугаман програмчлалын бодлогыг каноник хэлбэрт оруулах дүрэм дараах байдалтай байна.
- хэрэв анхны асуудалд шугаман функцийн максимумыг тодорхойлох шаардлагатай бол та тэмдгийг өөрчилж, энэ функцийн хамгийн бага утгыг хайх хэрэгтэй;
- хэрэв хязгаарлалтын баруун тал сөрөг байвал энэ хязгаарлалтыг -1-ээр үржүүлнэ;
- хэрэв хязгаарлалтуудын дунд тэгш бус байдал байгаа бол сөрөг бус нэмэлт хувьсагчдыг оруулснаар тэдгээрийг тэгш байдал болгон хувиргана;
- ямар нэг хувьсагч байвал x jТэмдгийн хязгаарлалтгүй бол түүнийг (зорилгын функц болон бүх хязгаарлалтад) хоёр шинэ сөрөг бус хувьсагчийн хоорондох зөрүүгээр солино.
x 3 = x 3 + — x 3 — , Хаана x 3 + , x 3 — ≥ 0 .
Жишээ 1. Шугаман програмчлалын асуудлыг каноник хэлбэрт оруулах:
мин L = 2x 1 + x 2 - x 3;
2х 2 - x 3 ≤ 5;
x 1 + x 2 – x 3 ≥ -1;
2х 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.
Хязгаарлалтын системийн тэгшитгэл бүрт тэгшлэх хувьсагчдыг оруулъя x 4 , x 5 , x 6. Систем нь тэгшитгэлийн хэлбэрээр бичигдэх бөгөөд хязгаарлалтын системийн нэг ба гурав дахь тэгшитгэлд хувьсагчдыг оруулна. x 4 , x 6зүүн талд "+" тэмдгээр, хоёр дахь тэгшитгэлд хувьсагчийг оруулна x 5"-" тэмдгээр оруулна.
2х 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2х 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.
Каноник хэлбэрийн чөлөөт нэр томъёо нь эерэг байх ёстой бөгөөд үүнийг хийхийн тулд сүүлийн хоёр тэгшитгэлийг -1-ээр үржүүлнэ.
2х 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 – x 6 = 3.
Шугаман програмчлалын бодлого бичих каноник хэлбэрээр хязгаарлалтын системд багтсан бүх хувьсагч сөрөг байх ёстой. Ингэж бодъё x 1 = x 1 ' - x 7 , Хаана x 1 ‘ ≥ 0, x 7 ≥ 0 .
Энэ илэрхийллийг хязгаарлалтын систем болон зорилгын функцэд орлуулж, хувьсагчдыг индексийн дарааллаар нэмэгдүүлэх замаар бичвэл бид каноник хэлбэрээр үзүүлсэн шугаман програмчлалын бодлогыг олж авна.
L min = 2x 1' + x 2 - x 3 - 2x 7;
2х 2 - x 3 + x 4 = 5;
-x 1 ‘ — x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ‘ + x 2 – x 6 + 2x 7 = 3;
x 1 ‘ ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.
Каноник LP асуудлын үндсэн төлөвлөгөөний оновчтой нөхцөл. Симплекс арга ба түүний конвергенц.
Симплекс арга нь нийтийн,Учир нь энэ нь танд бичигдсэн шугаман програмчлалын бараг бүх асуудлыг шийдэх боломжийг олгодог каноник хэлбэр.
Симплекс аргын санаа төлөвлөгөөг тогтмол сайжруулах,Энэ нь анхны лавлагааны шийдлээс эхлэн, дараалсан чиглэсэн хөдөлгөөнасуудлын лавлах шийдлүүдээс оновчтой шийдэл хүртэл.
Бодлогын хувьд энэ хөдөлгөөний үед зорилгын функцын утга хамгийн их хэмжээгээр буурахгүй.
Дэмжих шийдлүүдийн тоо хязгаарлагдмал байдаг тул хязгаарлагдмал тооны алхмуудын дараа бид оновчтой дэмжлэгийн шийдлийг олж авдаг.
Лавлах шийдэл нь сөрөг бус үндсэн шийдэл юм.
Энгийн аргын алгоритм
1. Бодлогын математик загвар нь байх ёстой каноник. Хэрэв энэ нь каноник биш бол түүнийг канон хэлбэрт оруулах ёстой.
2. Анхны лавлагааны шийдлийг олж, оновчтой эсэхийг шалгана уу.
Үүнийг хийхийн тулд симплекс хүснэгт 1-ийг бөглөнө үү.
Хязгаарлалтын систем ба зорилгын функцын өгөгдлийн дагуу бид 1-р шатны хүснэгтийн бүх мөрийг бөглөнө.
Асуудлыг шийдвэрлэх үед дараах тохиолдлууд гарч болзошгүй дээд тал нь:
1. Хэрэв симплекс хүснэгтийн сүүлийн эгнээний бүх коэффициентүүд Dj³ 0, дараа нь олдсон
шийдэл оновчтой.
2 Хэрэв дор хаяж нэг коэффициент байвал Dj £ 0, харин харгалзах хувьсагчийн хувьд нэг эерэг үнэлгээний хамаарал байхгүй, дараа нь шийдэл Бид даалгавраа зогсооно, учир нь F(X) ® ¥ ,өөрөөр хэлбэл зорилгын функц нь боломжит шийдлүүдийн хүрээнд хязгаарлагдахгүй.
Хэрэв сүүлчийн эгнээний ядаж нэг коэффициент сөрөг байвал харгалзах хувьсагчийн хувьд байна дор хаяж нэг эерэг үнэлгээ өгөх хандлагатай бол та хөдлөх хэрэгтэй өөр лавлах шийдэл рүү.
Э хэрэвСүүлийн эгнээнд хэд хэдэн сөрөг коэффициент байна үндсэн хувьсагчийн багана руу(BP) үүнийг танилцуулж байна хувьсагч, энэ нь тохирч байна үнэмлэхүй утгын хамгийн том сөрөг коэффициент.
5. Хэрэв хамгийн багадаа нэг коэффициент Dk< 0 , Тэр к - tyбагана хүлээн авна хөтлөгчийн хувьд.
6. төлөө тэргүүлэх шугамБид тохирохыг нь хүлээн зөвшөөрдөг хамгийн багачөлөөт гишүүдийн харьцаа биэерэг коэффициентүүд рүү тэргүүлэх, k – тэр нэгбагана.
7. Тэргүүлэх мөр, баганын уулзварт байрлах элементийг дуудна тэргүүлэх элемент.
Симплекс хүснэгт 2-ыг бөглөх :
· үндсэн баганыг тэг ба нэгээр дүүргэ
· Тэргүүлэх мөрийг тэргүүлэгч элементэд хувааж дахин бичнэ
· Хэрэв тэргүүлэгч мөрөнд тэг байвал харгалзах багануудыг дараагийн симплекс хүснэгт рүү шилжүүлж болно
· Бид "тэгш өнцөгт" дүрмийг ашиглан үлдсэн коэффициентүүдийг олно
Бид шалгадаг шинэ лавлагааны шийдлийг олж авдаг оновчтой болгохын тулд:
Хэрэв сүүлчийн эгнээний бүх коэффициентууд Dj³ 0, дараа нь шийдэл олдлоо дээд тал нь.
Хэрэв тийм биш бол 8-р алхам гэх мэт симплекс хүснэгтийг бөглөнө үү.
Хэрэв зорилгын функц F(X)олохыг шаарддаг хамгийн бага утга, дараа нь шалгуур асуудлын оновчтой байдалбайна эерэг бус коэффициентүүдД j бүхний хувьд j = 1,2,…n.
Симплекс аргын конвергенц. LP асуудлууд дахь доройтол. Аливаа тооцооллын алгоритмын хамгийн чухал шинж чанар нь нэгдэл, өөрөөр хэлбэл түүнийг хэрэглэх явцад (өгөгдсөн нарийвчлалтайгаар) хүссэн үр дүнг хязгаарлагдмал тооны алхмаар (давталт) авах боломж юм.
Харьцааны хамгийн бага утгууд ижил байх тохиолдолд r (2-р хэсэг") утгыг сонгох үе шатанд симплекс аргын нэгдэлтэй холбоотой асуудал үүсч болохыг харахад хялбар байдаг.
T (q) хүснэгтийн хэд хэдэн эгнээнд нэгэн зэрэг хүрэх болно. Дараа нь дараагийн давталт дээр b(β(q+1)) баганад тэг элемент агуулагдана.
⇐ Өмнөх12345Дараагийн ⇒
Нийтэлсэн огноо: 2015-11-01; Уншсан: 4190 | Хуудасны зохиогчийн эрхийг зөрчсөн
Studopedia.org - Studopedia.Org - 2014-2018 (0.002 сек)…
Хамгийн оновчтой шийдэл - асуудал - шугаман програмчлал
Хуудас 1
Шугаман програмчлалын асуудлын оновчтой шийдэл нь хамгийн багадаа k n, - m хувьсагчид тэгтэй тэнцүү байх лавлах цэгүүдийн аль нэгэнд хүрдэг.
Шугаман програмчлалын асуудлын оновчтой шийдлийг ашигласнаар L нь тогтмол байх DS-ийн зөвшөөрөгдөх өөрчлөлтийг олж болно.
Шугаман програмчлалын асуудлын оновчтой шийдэл байгаа бол үндсэн оновчтой шийдэл байна.
Шугаман програмчлалын асуудлын оновчтой шийдэл нь n хэмжээст орон зайд олон талт хэлбэртэй, шугаман хязгаарлалтын системээр тодорхойлогддог хяналттай хувьсагчдын зөвшөөрөгдөх утгын бүсийн хил дээр байрладаг нь батлагдсан.
z нь m хязгаарлалттай шугаман програмчлалын асуудлын оновчтой шийдэл учраас энэ шийдэл нь хамгийн ихдээ m хатуу эерэг хувьсагчийг агуулна.
Шугаман програмчлалын асуудлын оновчтой шийдэл нь шугаман хязгаарлалтын системээр тодорхойлогддог / хэмжээст орон зайд олон талт хэлбэртэй, хяналттай хувьсагчдын зөвшөөрөгдөх утгын бүсийн хил дээр байрладаг нь батлагдсан. Орой бүрийн координатыг тэгшитгэлийн системийг (хязгаарлалт) шийдвэрлэх замаар тодорхойлох ба n хяналттай хувьсагч ба m хязгаарлалт байгаа тохиолдолд m тэгшитгэлийн системийг шийдвэрлэх шаардлагатай. Cpt n (m - n) хослол нь төрөл нэмэгдэхийн хэрээр маш хурдан ургадаг тул шийдлийг олохын тулд маш олон тооны тооцоолол шаардагддаг бөгөөд компьютерт ч хүрдэггүй.
Тиймээс D 1-ийн хувьд шугаман програмчлалын асуудлын оновчтой шийдэл нь автоматаар бүхэл тоо болж хувирдаг.
1-р хэсэгт үзүүлсэнчлэн шугаман програмчлалын асуудлын оновчтой шийдэл нь бүхэл тоо байх албагүй бөгөөд үүний зэрэгцээ бүхэл тоон шийдлийг шаарддаг олон асуудал байдаг. Эдгээр асуудлуудын зарим нь бүхэл тооны програмчлалын бодлого биш мэт боловч тэдгээрийг томъёолж болно.
Шугаман програмчлалын асуудлын үндсэн шийдэл бүр оновчтой шийдэл биш гэдэг нь ойлгомжтой. Гэсэн хэдий ч доройтоогүй асуудлын оновчтой шийдэл нь тэгшитгэлийн системд (VIII, 42) үргэлж суурь байх ёстой бөгөөд ингэснээр олох асуудал байх ёстой. оновчтой шийдэлЗөвхөн тэгшитгэлийн системийн үндсэн шийдлүүдийг хайхаас бүрддэг (VIII, 42), тэдгээрийн дотроос оновчтой нь олддог.
Шугаман програмчлалын асуудлын үндсэн шийдэл бүр оновчтой шийдэл биш гэдэг нь ойлгомжтой. Гэсэн хэдий ч доройтдоггүй асуудлын оновчтой шийдэл нь тэгшитгэлийн системийн (VIII42) суурь шийдэл байх ёстой бөгөөд ингэснээр оновчтой шийдлийг олох ажил нь зөвхөн тэгшитгэлийн системийн (VIII42) үндсэн шийдлүүдийг хайхаас бүрддэг. ), тэдгээрийн хамгийн оновчтой нь олддог.
3-р алхамыг хэд хэдэн удаа давтсаны дараа шугаман програмчлалын асуудлыг шийдэх олон хувилбарын оновчтой шийдлүүд гарч ирж болно.
Шугаман програмчлалын асуудал
Энэ төрлийн дугуйг заримдаа тасралтгүй доройтол гэж нэрлэдэг. Харамсалтай нь энэ үзэгдэл нь ихэвчлэн өндөр хэмжээст дунд PI асуудалд тохиолддог. Мөн нэгдмэл байдалд хүрэхийн тулд олон мянган давталт хийх шаардлагатай бага хэмжээст бодлого (10-аас илүүгүй хувьсагч ба тэгшитгэл) олон жишээ байдаг.
Эдгээр тохиолдолд симплекс аргыг ашигладаг бөгөөд энэ нь шугаман програмчлалын асуудлын оновчтой шийдлийг тодорхойлох давталтын (алхам алхмаар) процедур юм. Симплекс аргыг ашиглан тооцоолол нь хэрэгжих боломжтой шийдлийг тодорхойлж, дараа нь бусад боломжит шийдлүүдийг хайж, тэдгээрийг сайжруулах боломжийг шалгана. Нэг шийдэлээс нөгөөд шилжих нь шинэ сайжруулалт хийх боломжгүй болтол үргэлжилнэ. Өргөн тархсан стандарт компьютерийн програмууд, шугаман програмчлалын бодлого хэлбэрээр төлөөлүүлж болох удирдлагын асуудлыг шийдвэрлэхийн тулд симплекс аргыг ашигладаг.
Хэрэв шугаман хязгаарлалтын систем нь тусгай бүтэцтэй бол, жишээлбэл, сүлжээний загварыг бүрдүүлдэг бол 2-р алхам дээр шугаман програмчлалын асуудлын оновчтой шийдлийг олох үед энэ нөхцөл байдлыг ашиглаж болно.
Пропорциональ хуваарилалтын санааг И.И.Дикинийн санал болгосон хоёр үе шаттай тооцооллын алгоритм хэлбэрээр хэрэгжүүлсэн бөгөөд шугаман програмчлалын оновчтой шийдлүүдийн багцын харьцангуй дотоод цэгийг бий болгохын тулд дотоод цэгийн аргын шинж чанарыг үндсэндээ ашигладаг. асуудал. Энэ шинж чанар нь (2.3.2) - (2.3.4) тэгш бус байдлын дагуух хилийн утгыг зөвхөн бусад оновчтой шийдлийн хувьд эдгээр хилийн утгыг агуулсан хувьсагчдын хувьд хүрнэ гэсэн үг юм.
Хуудас: 1 2
Шугаман програмчлалын асуудлыг шийдвэрлэх график арга
Хоёр хувьсагчийн хувьд ZLP-ийг стандарт хэлбэрээр авч үзье.
(10)
Тэгш бус байдлын систем (10) тууштай байг (дор хаяж нэг шийдэлтэй). Энэ системийн аливаа тэгш бус байдал нь хилийн шугамтай хагас хавтгайг геометрийн хувьд тодорхойлдог 
Сөрөг бус нөхцөлүүд нь харгалзах хилийн шугам бүхий хагас хавтгайг тодорхойлдог Тэгээд.
Систем нь тууштай байдаг тул гүдгэр олонлогууд шиг огтлолцдог хагас хавтгай нь гүдгэр олонлог бөгөөд цэгүүдийн цуглуулга болох нийтлэг хэсгийг бүрдүүлдэг бөгөөд тус бүрийн координат нь энэ системийн шийдэл юм. Эдгээр бүх цэгүүдийн багцыг нэрлэдэг уусмалын олон өнцөгт.Энэ нь цэг, сегмент, туяа, шулуун шугам, битүү олон өнцөгт эсвэл хязгааргүй олон өнцөгт талбай байж болно.
ZLP-ийг геометрийн аргаар шийдвэрлэх нь координатууд нь зорилгын функцэд хамгийн их (хамгийн бага) утгыг өгдөг шийдлийн олон өнцөгт цэгийг хайж олох явдал юм. Түүнээс гадна олон өнцөгтийн бүх цэгүүд нь зөв шийдэл юм.
гэж нэрлэгддэг зүйлийг авч үзье түвшний шугамзорилгын функц z, өөрөөр хэлбэл, энэ функц ижил тогтмол утгыг авах шугам: эсвэл 
График аргаар шугаман програмчлалын асуудлыг шийдвэрлэх алгоритм (хувьсагчийн тоо).
1. Хязгаарлалтад тохирох хавтгай дээрх боломжит шийдлүүдийн олон өнцөгт мужийг байгуулав. Дараа нь градиент векторыг байгуулна
зорилгын функц zаль ч үед хэрэгжих боломжтой шийдлүүдийн бүс нутаг.
2. Шулуун шугам (функцийн түвшний шугам z), градиент векторт перпендикуляр, боломжит шийдлүүдийн мужаас гарах хүртэл хамгийн их асуудлын үед градиент векторын чиглэлд (мөн хамгийн бага асуудлын хувьд эсрэг чиглэлд) өөртэйгөө параллель хөдөлдөг. Бүс нутгийн хязгаарын цэг (эсвэл цэгүүд) нь оновчтой цэгүүд юм.
3. Оновчтой цэгийн координатыг олохын тулд огтлолцол нь энэ цэгийг бүрдүүлж буй шулуун шугамд тохирох тэгшитгэлийн системийг шийдэх шаардлагатай.
LP бодлогын үндсэн төрлүүдийг томъёолох, тэдгээрийн математик загварыг бий болгох
Энэ цэг дэх зорилгын функцын утга нь оновчтой байх бөгөөд цэгийн координат нь өөрөө LP асуудлыг шийдэх шийдэл болно. .
Жишээ.Асуудлыг геометрийн аргаар шийд:
Бүх боломжит шийдлүүдийн олон өнцөгтийг байгуулъя OABCDба зорилгын функцийн чиглэлийн вектор (Зураг 1). Градиент векторын чиглэл нь зорилгын функц өсөх чиглэлийг заана. Харж байгаа асуудал бол максимумыг олох тул бид векторт перпендикуляр шулууныг энэ векторын чиглэлд өөртэйгөө параллель хөдөлгөж, энэ шугам нь боломжит шийдлүүдийн мужаас гарах хүртэл хөдөлнө. Бүс нутгийн хил дээр, манай тохиолдолд цэг дээр ХАМТ, мөн асуудлын шийдэл байх болно. Цэг ХАМТшугамын огтлолцол дээр байрладаг ба . Үүний үр дүнд түүний координатыг эдгээр тэгшитгэлийн системийг шийдэх замаар тодорхойлно.
хаанаас, өөрөөр хэлбэл. цэг ХАМТкоординаттай (6, 4).
Хамгийн их (зорилгын функцийн хамгийн их утга) нь дараахтай тэнцүү байна. Хариулт:оновчтой шийдэлтэй, жишээлбэл. Эхний бүтээгдэхүүнээс 6, хоёр дахь бүтээгдэхүүнээс 4 ширхэгийг үйлдвэрлэснээр хамгийн их ашиг хүртэх боломжтой.
ОРШИЛ
Орчин үеийн эдийн засгийн онол нь микро болон макро түвшний аль алинд нь математик загвар, аргуудыг байгалийн, зайлшгүй элемент болгон агуулдаг. Математикийг эдийн засагт ашиглах нь нэгдүгээрт, эдийн засгийн хувьсагч ба объектуудын хоорондын хамгийн чухал, чухал холболтыг тодорхойлж, албан ёсоор тайлбарлах боломжийг олгодог. нарийн төвөгтэй объектөндөр түвшний хийсвэрлэлийг агуулдаг. Хоёрдугаарт, тодорхой томъёолсон анхны өгөгдөл, харилцааг дедуктив аргыг ашиглан хийсэн байртай ижил хэмжээгээр судалж буй объектод тохирсон дүгнэлтийг гаргаж болно. Гуравдугаарт, математик, статистикийн аргууд нь объектын тухай шинэ мэдлэгийг индуктив байдлаар олж авах боломжийг олгодог: одоо байгаа ажиглалттай хамгийн нийцэж байгаа хувьсагчдын хамаарлын хэлбэр, параметрүүдийг үнэлэх. Эцэст нь, дөрөвдүгээрт, математикийн хэлийг ашиглах нь эдийн засгийн онолын заалтуудыг үнэн зөв, нягт нямбай илэрхийлэх, түүний үзэл баримтлал, дүгнэлтийг боловсруулах боломжийг олгодог.
Эдийн засагт хэрэглэгддэг математик загваруудыг загварчилж буй объектын шинж чанар, загварчлалын зорилго, ашигласан хэрэглүүртэй холбоотой хэд хэдэн шинж чанараар нь ангилж болно: микро ба макро эдийн засгийн загвар, онолын болон тэнцвэрт байдал, статистик ба динамик.
Оновчлолын аргын мөн чанар нь тодорхой нөөцийн хүртээмжид үндэслэн бидний сонирхож буй үзүүлэлтийн хамгийн дээд хэмжээг (хамгийн бага) хангах тэдгээрийг ашиглах (тараах) аргыг сонгох явдал юм.
Математик програмчлалын (төлөвлөлт) бүх үндсэн хэсгүүдийг эдийн засгийн оновчлолын арга болгон ашигладаг.
Хэт их (хамгийн их эсвэл хамгийн бага) хяналтын болон төлөвлөлтийн асуудлыг судлах, тэдгээрийг шийдвэрлэх аргачлалыг боловсруулахтай холбоотой математикийн салбарыг гэнэ. математик програмчлал.
Ерөнхийдөө экстремаль бодлогын математик томъёолол нь зорилгын функцийн хамгийн том эсвэл хамгийн бага утгыг тодорхойлохоос бүрдэнэ. 
үүнийг өгсөн 
,
хаана болон өгөгдсөн функцууд ба зарим бодит тоонууд.
Зорилгын функц, хязгаарлалтын төрлөөс хамааран математик програмчлалыг шугаман болон шугаман бус гэж хуваадаг. Ихэнх
Математик програмчлалын судлагдсан салбар бол шугаман програмчлал юм.
Тодорхойлолт.
Шугаман програмчлалын асуудал (3 хуудасны 1-р хуудас)
Шугаман програмчлал - шугаман хязгаарлалтад хамаарах үл мэдэгдэх шугаман функцийн туйлын (хамгийн ба хамгийн бага) утгыг ашиглах, олох аргын шинжлэх ухаан.
Энэхүү шугаман функцийг зорилтот функц гэж нэрлэдэг ба тэгшитгэл буюу тэгш бус байдлын хэлбэрийн хязгаарлалтыг хязгаарлалтын систем гэж нэрлэдэг.
Тодорхойлолт. Зорилгын функц ба түүний хязгаарлалтын математик илэрхийлэл гэж нэрлэдэг эдийн засгийн асуудлын математик загвар.
Шугаман програмчлалын зарим асуудлыг (LPP) авч үзье.
1. Нөөц ашиглалтын асуудал (үйлдвэрлэлийн төлөвлөлтийн асуудал).
Төрөл бүрийн бүтээгдэхүүн үйлдвэрлэх зориулалттай 
компани гурван янз бүрийн төрөлтүүхий эд. Нэг бүтээгдэхүүн үйлдвэрлэх түүхий эдийн хэрэглээний стандарт 
, түүнчлэн нийт тоо
Аж ахуйн нэгжийн ашиглаж болох төрөл бүрийн түүхий эдийг хүснэгтэд үзүүлэв.
Аж ахуйн нэгжийн үйлдвэрлэсэн бүх бүтээгдэхүүний нийт өртөг хамгийн их байх бүтээгдэхүүний үйлдвэрлэлийн төлөвлөгөө гаргах.
Энэ бодлогын математик загварыг бүтээцгээе.
Бүтээгдэхүүний шаардлагатай гарцыг бүтээгдэхүүнээр, бүтээгдэхүүнээр,
дамжуулан - бүтээгдэхүүн.
Түүхий эдийн төрөл бүрийн зардлын стандарт байдаг тул бид бүх төрлийн түүхий эдийг үйлдвэрлэхэд шаардагдах нийт өртөгийг олох боломжтой. Хүснэгтээс харахад I төрлийн түүхий эдийн нийт хэмжээ, II - байх болно. 
,
III - 
. Мөн түүхий эдийн санд хязгаарлалт байдаг тул түүхий эдийн төрөл бүрийн нийт хэмжээ нь нийт түүхий эдийн хэмжээнээс хэтрэхгүй байх ёстой, өөрөөр хэлбэл.
Бид дараах тэгш бус байдлын системийг олж авна
(1)
Эдийн засгийн хувьд хувьсагч 
Зөвхөн сөрөг бус утгыг авч болно:
(2)
Энэ төрлийн бүх бүтээгдэхүүний өртөг нь байх болно 
– 
– 
Үүний дагуу аж ахуйн нэгжийн үйлдвэрлэсэн бүтээгдэхүүний нийт өртөг (3) болно.
Бид олох хэрэгтэй 
энэ функц. Тиймээс (1) системийн бүх сөрөг бус шийдлүүдийн дотроос (3) функц хамгийн их утгыг авах нэгийг олох шаардлагатай.
Энэ асуудлыг түүхий эд (нөөц)-ийн төрлийг ашиглан бүтээгдэхүүн үйлдвэрлэх тохиолдолд хялбархан ерөнхийд нь авч үзэж болно.
-ээр тэмдэглэе 
- үйлдвэрлэхээр төлөвлөж буй бүтээгдэхүүний тоо, 
– нөөц – нөөцийн төрөл, – тодорхой хэрэглээ – үйлдвэрлэлийн нөөц – th бүтээгдэхүүн. – нэгж бүтээгдэхүүний борлуулалтаас олох ашиг – төрөл.
Дараа нь ерөнхий томъёололд нөөцийг ашиглах асуудлын эдийн засаг-математик загвар нь дараах хэлбэртэй болно: ийм төлөвлөгөө олох. 
хязгаарлалтын үндсэн системийг хангасан гаралт 
нэмэлт хязгаарлалтын систем
Үүнд зорилгын функц байна 
хамгийн их утгыг авдаг.
Сэтгэгдэл. ZLP-ийн математик загварыг бий болгохын тулд дараахь зүйлийг хийх шаардлагатай.
– хувьсах тэмдэглэгээг нэвтрүүлэх;
– эдийн засгийн судалгааны зорилгод үндэслэн объектив функцийг бий болгох;
– асуудлын эдийн засгийн үзүүлэлтүүдийг ашиглах хязгаарлалт, тэдгээрийн тоон хэлбэрийг харгалзан хязгаарлалтын тогтолцоог бичнэ үү.
Шугаман програмчлалын асуудлын шийдэл нь хэмжээст вектор орон зай дахь аналитик геометрийн үзэл баримтлалд суурилдаг.
Ерөнхий ZLP-ийг каноник хэлбэрт оруулах.
ZLP-ийн ерөнхий үзэл баримтлал нь дараах байдалтай байна.
(1)
(2)
(3)
Энд (1) хамаарал нь зорилгын функц, (2) үндсэн хязгаарлалтын систем, (3) нэмэлт хязгаарлалтын систем юм.
(2) ба (3) харилцаа нь хязгаарлалтын бүрэн системийг бүрдүүлдэг.
Үндсэн хязгаарлалтын системийг каноник хэлбэрт оруулах нь хэлбэрийн тэгш бус байдлын хувьд "+1", тэгш бус байдлын хувьд "-1" коэффициент бүхий нэмэлт сөрөг бус хувьсагчдыг оруулах замаар хийгддэг. Нэмэлт хувьсагчдыг 0 коэффициент бүхий зорилгын функцэд оруулсан болно.
Тодорхойлолт . Хэрэв үндсэн хязгаарлалтын системийг тэгшитгэлээр илэрхийлсэн бол ZLP-ийг каноник хэлбэрээр өгсөн гэж нэрлэдэг.
Тодорхойлолт. Дараах нөхцөл хангагдсан тохиолдолд PLP-ийг стандарт каноник хэлбэрээр өгнө гэж хэлнэ.
1) үндсэн хязгаарлалтын системийг тэгшитгэлээр илэрхийлсэн бөгөөд тэдгээр нь бүгд шугаман хамааралгүй;
2) тэгшитгэлийн тоо нь хувьсагчийн тооноос бага;
3) зорилгын функцийг багасгах асуудлыг шийдсэн;
4) үндсэн хязгаарлалтын системийн баруун тал нь сөрөг биш;
5) бүх хувьсагч нь сөрөг биш байна.
Шугаман програмчлалын асуудлыг шийдвэрлэх ихэнх аргуудад хязгаарлалтын систем нь хувьсагчдын сөрөг бус байдлын тэгшитгэл ба байгалийн нөхцлөөс бүрддэг гэж үздэг.
Гэсэн хэдий ч олон асуудлын загвар үүсгэх үед хязгаарлалтууд нь тэгш бус байдлын систем хэлбэрээр голчлон үүсдэг тул тэгш бус байдлын системээс тэгшитгэлийн систем рүү шилжих чадвартай байх шаардлагатай.
Үүнийг дараах байдлаар хийж болно.
Шугаман тэгш бус байдлыг авч үзье
мөн түүний зүүн талд тодорхой утгыг нэмж, тэгш бус байдал нь тэгш байдал болж хувирна
Түүнээс гадна энэ утга нь сөрөг биш юм.
Жишээ
Шугаман програмчлалын бодлогыг каноник хэлбэрт оруул:
Шийдэл:
Зорилгын функцийн максимумыг олох бодлого руу шилжье.
Үүнийг хийхийн тулд бид зорилгын функцийн коэффициентүүдийн тэмдгүүдийг өөрчилдөг.
Хязгаарлалтын системийн хоёр ба гурав дахь тэгш бус байдлыг тэгшитгэл болгон хувиргахын тулд сөрөг бус нэмэлт хувьсагч x 4 x 5 (математик загварт энэ үйлдлийг D үсгээр тэмдэглэсэн) оруулна.
Хоёр дахь тэгш бус байдлын зүүн талд x 4 хувьсагчийг "+" тэмдгээр оруулав, учир нь тэгш бус байдал нь "≤" хэлбэртэй байна.
Гурав дахь тэгш бус байдлын зүүн талд x 5 хувьсагчийг "-" тэмдгээр оруулав, учир нь тэгш бус байдал нь "≥" хэлбэртэй байна.
Х 4 х 5 хувьсагчдыг зорилгын функцэд коэффициентээр оруулна. тэгтэй тэнцүү.
Бид асуудлыг каноник хэлбэрээр бичдэг.
Шугаман ПРОГРАМЧЛАЛЫН АСУУДЛЫГ ШИЙДЭХ ЭНГИЙН АРГА
Энэ арга нь шугаман програмчлалын асуудлын жишиг шийдлүүдийг зорилготойгоор тоолох арга юм. Энэ нь хязгаарлагдмал тооны алхамаар оновчтой шийдлийг олох эсвэл оновчтой шийдэл байхгүй гэдгийг тогтоох боломжийг олгодог.
Шугаман програмчлалын асуудлыг шийдвэрлэх симплекс аргын алгоритм
Симплекс аргыг ашиглан асуудлыг шийдэхийн тулд та дараахь зүйлийг хийх ёстой.
1. Асуудлыг каноник хэлбэрт оруул
Сэдэв 8. Шугаман програмчлал
Анхны дэмжлэгийн шийдлийг "нэгж суурь"-аар олоорой (хэрэв дэмжлэгийн шийдэл байхгүй бол хязгаарлалтын тогтолцооны үл нийцэлээс болж асуудал шийдэлгүй болно)
3. Лавлагаа шийдэлд үндэслэн векторын задралын тооцоог тооцоолж, симплекс аргын хүснэгтийг бөглөнө үү.
4. Хэрэв оновчтой шийдлийн өвөрмөц байдлын шалгуур хангагдсан бол асуудлын шийдэл дуусна.
5. Хэрэв оновчтой шийдлийн цогц байх нөхцөл хангагдсан бол бүх оновчтой шийдлийг энгийн тооллогоор олно.
Симплекс аргыг ашиглан асуудлыг шийдэх жишээ
Жишээ 1
Симплекс аргыг ашиглан асуудлыг шийд:
Функцийн утгыг багасгах
F = 10×1 – 4×3 хамгийн их
Тэгш бус байдлын хэлбэрээр хязгаарлалт байгаа тохиолдолд
Бид асуудлыг каноник хэлбэрт оруулдаг.
Үүнийг хийхийн тулд бид эхний тэгш бус байдлын хязгаарлалтын зүүн талд +1 коэффициент бүхий x 5 нэмэлт хувьсагчийг оруулав. Хувьсагч x 5 нь зорилтот функцэд тэгийн коэффициенттэй (өөрөөр хэлбэл үүнийг оруулаагүй болно) багтсан болно.
Бид авах:
F = 10×1 – 4×3+0∙x5 хамгийн их
Тэгш бус байдлын хэлбэрээр хязгаарлалт байгаа тохиолдолд
Бид анхны тусламжийн шийдлийг олдог. Үүний тулд бид чөлөөт (шийдвэрлэгдээгүй) хувьсагчдыг тэг x1 = x3 = 0 гэж тэнцүүлнэ.
Бид B1 = (A4, A5, A6) нэгж суурьтай X1 = (0,0,0,5,9/15,6) лавлагаа шийдлийг олж авна.
Бид жишиг шийдэлд үндэслэн нөхцөлийн векторуудын өргөтгөлийн тооцоог томъёогоор тооцоолно.
Δ k = C b X k - c k
· C b = (c 1 , c 2 , … , c m) - үндсэн хувьсагчдын зорилгын функцийн коэффициентийн вектор.
· X k = (x 1k , x 2k , … , x mk) - жишиг шийдлийн суурийн дагуу харгалзах вектор А k тэлэлтийн вектор.
· C k - х k хувьсагчийн зорилгын функцийн коэффициент.
Суурьд орсон векторуудын тооцоо үргэлж тэгтэй тэнцүү байна.
Лавлагааны шийдэл, тэлэлтийн коэффициент ба нөхцөл векторуудын өргөтгөлийн тооцоог жишиг шийдэлд үндэслэн симплекс хүснэгтэд бичнэ.
Тооцооллыг тооцоолоход хялбар болгох үүднээс хүснэгтийн дээд хэсэгт зорилгын функцийн коэффициентүүдийг бичсэн болно. "B" эхний баганад лавлагааны шийдлийн суурьт орсон векторуудыг бичнэ. Эдгээр векторуудыг бичих дараалал нь хязгаарлалтын тэгшитгэл дэх зөвшөөрөгдөх үл мэдэгдэх тоотой тохирч байна. Хүснэгтийн "C b" хоёр дахь баганад үндсэн хувьсагчдын зорилгын функцийн коэффициентүүдийг ижил дарааллаар бичнэ. "C b" баганад зорилгын функцийн коэффициентүүдийг зөв зохион байгуулснаар суурьт багтсан нэгж векторуудын тооцоо үргэлж тэгтэй тэнцүү байна.
"A 0" баганад Δ k-ийн тооцоо бүхий хүснэгтийн сүүлчийн мөрөнд Z(X 1) лавлагааны шийдлийн зорилгын функцийн утгуудыг бичнэ.
Хамгийн их асуудалд А 1 ба А 3 векторуудын хувьд Δ 1 = -2, Δ 3 = -9 гэсэн тооцоолол сөрөг байдаг тул анхны дэмжлэгийн шийдэл нь оновчтой биш юм.
Дэмжлэгийн шийдлийг сайжруулах теоремын дагуу хэрэв хамгийн их асуудалд дор хаяж нэг вектор сөрөг үнэлгээтэй байвал зорилгын функцийн утга илүү байх шинэ дэмжлэгийн шийдлийг олох боломжтой.
Хоёр векторын аль нь зорилгын функцэд илүү их өсөлт үзүүлэхийг тодорхойлъё.
Зорилгын функцийн өсөлтийг дараах томъёогоор олно.
Бид эхний ба гурав дахь баганын θ 01 параметрийн утгыг томъёогоор тооцоолно.
Бид l = 1-ийн хувьд θ 01 = 6, l = 1-ийн хувьд θ 03 = 3-ийг авна (Хүснэгт 26.1).
Эхний векторыг суурьт оруулахдаа бид зорилгын функцийн өсөлтийг олдог
ΔZ 1 = - 6*(- 2) = 12,
ба гурав дахь вектор ΔZ 3 = - 3*(- 9) = 27.
Иймээс оновчтой шийдэлд илүү хурдан хандахын тулд эхний мөрөнд θ 03 параметрийн хамгийн багад хүрсэн тул A6 суурийн эхний векторын оронд А3 векторыг жишиг шийдлийн сууринд оруулах шаардлагатай. l = 1).
Бид Жорданы хувиргалтыг X13 = 2 элементээр гүйцэтгэдэг бөгөөд бид хоёр дахь лавлагааны шийдлийг олж авдаг
X2 = (0,0,3,21,42,0)
суурь B2 = (A3, A4, A5).
(Хүснэгт 26.2)
А2 вектор Δ2 = - 6 сөрөг оноотой тул энэ шийдэл нь оновчтой биш юм.
Уусмалыг сайжруулахын тулд A2 векторыг жишиг шийдлийн үндэс болгон нэвтрүүлэх шаардлагатай.
Бид баазаас гаргаж авсан векторын тоог тодорхойлно. Үүнийг хийхийн тулд бид хоёр дахь баганын хувьд θ 02 параметрийг тооцоолно, энэ нь l = 2-ийн хувьд 7-той тэнцүү байна.
Үүний үр дүнд бид баазаас хоёр дахь суурь вектор А4-ийг гаргаж авдаг.
Бид Жорданы хувиргалтыг x 22 = 3 элементээр гүйцэтгэдэг бөгөөд бид гурав дахь дэмжлэгийн шийдлийг олж авдаг
X3 = (0.7,10,0.63,0)
B2 = (A3, A2, A5) (Хүснэгт 26.3).
Энэ шийдэл нь цорын ганц оновчтой шийдэл юм, учир нь суурьт ороогүй бүх векторуудын хувьд эерэг тооцоолол байдаг
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Хариулт: max Z(X) = 201 X = (0.7,10,0.63).
⇐ Өмнөх123456789Дараа нь ⇒
муж боловсролын байгууллагаилүү өндөр
Мэргэжлийн боловсрол
"Н.Е. Бауманы нэрэмжит Москвагийн Улсын Техникийн Их Сургууль"
Калуга салбар
"Симплекс аргыг ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх"
Ажлын зорилго: Шууд ба хос шугаман програмчлалын асуудлыг шийдвэрлэх симплекс аргыг судалж, практикт ашиглаж сурах.
Онолын хэсэг.
Шугаман програмчлалын бодлогын математик томъёолол.
Математикийн програмчлалын асуудлыг авч үзэх практикаас харахад тэдгээрийг шийдвэрлэх бараг боломжгүй юм. Асуудлын тусдаа ангиудыг (төрөл) авч үзэхийг зөвлөж байна. Ийм анги бүрийн хувьд зөвхөн энэ ангиллын бодлогод тохирох шийдлийн алгоритмыг томъёолж болно. Математик програмчлалын хамгийн хөгжсөн бодлого бол шугаман програмчлалын (LP) бодлого юм.
Шугаман програмчлалын бодлогод зорилгын функц нь шугаман байх ба хязгаарлалтын нөхцөл нь шугаман тэгшитгэл ба шугаман тэгш бус байдлыг агуулна. Хувьсагч нь сөрөг бус байдлын шаардлагад хамаарах эсвэл хамаарахгүй байж болно. Шугаман програмчлалын ижил бодлогыг янз бүрийн хэлбэрээр бичиж болно. Хэрэв бүх хязгаарлалтууд тэгш бус байдлын хэлбэртэй байвал асуудлыг стандарт хэлбэрээр бичнэ. Хэрэв түүний бүх хязгаарлалтыг эс тооцвол
тэгш байдлыг илэрхийлдэг бол шугаман програмчлалын бодлогыг каноник хэлбэрээр бичнэ.
Шугаман програмчлалын асуудлын ерөнхий ойлголт
,
Хязгаарлалт:
1. Бүх хязгаарлалтын баруун тал нь сөрөг биш байх ёстой 
. Хэрэв коэффициентүүдийн аль нэг нь байвал< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;
2. Бүх хязгаарлалтыг тэгш байдлын хэлбэрээр үзүүлэх ёстой тул тэгш бус байдлаас тэгш байдал руу шилжихдээ нэмэлт хувьсагчийн аппаратыг ашигладаг.
Хэрэв эхний хязгаарлалтууд нь зарим нөөцийн хэрэглээг ("" тэмдэг) тодорхойлдог бол хувьсагчид 
нөөцийн үлдэгдэл буюу ашиглагдаагүй хэсэг гэж тайлбарлах ёстой. Энэ тохиолдолд энэ нь үлдэгдэл хувьсагч бөгөөд "+" тэмдгээр тэгшитгэлд оруулна.
Хэрэв эхний хязгаарлалт нь зарим нөөцийн илүүдлийг ("" тэмдэг) тодорхойлдог бол илүүдэл хувьсагчийг нэвтрүүлнэ. 
"-" тэмдэг.
Хувьсагч:
Бүх хувьсагч нь сөрөг биш байх ёстой, i.e. 
.
Хэрэв хувьсагч нь тэмдгийн хязгаарлалтгүй бол түүнийг сөрөг бус хоёр хувьсагчийн зөрүүгээр илэрхийлэх ёстой: , энд . Энэхүү орлуулалтыг энэ хувьсагчийг агуулсан бүх хязгаарлалт, мөн зорилгын функцийн илэрхийлэлд ашиглах ёстой.
Хэрэв ийм хувьсагч нь оновчтой шийдэлд орвол
Зорилго функц:
Томруулах эсвэл багасгах.
Тэгш ба тэгш бус байдлын хэлбэрийн хязгаарлалтын систем нь гүдгэр олон талт гүдгэр олонлогийг бүрдүүлдэг. Энэ багц нь хязгаарлагдмал эсвэл хязгааргүй байж болно. Шугаман програмчлалын бодлогын зорилгын функц нь мөн гүдгэр функц юм. Тиймээс шугаман програмчлалын бодлого нь гүдгэр програмчлалын бодлогын онцгой тохиолдол юм.
Шугаман програмчлалын бодлогын хязгаарлалтын системийг тэгш байдлын хэлбэрээр авч үзье
(1)
Шугаман тэгшитгэлийн систем (1) нь дор хаяж нэг шийдэлтэй байвал нийцтэй байна. Хэрэв тэгшитгэлийн аль нэгийг бусдын шугаман хослолоор илэрхийлж чадвал (1) системийг илүүдэл гэж нэрлэдэг.
(1) системд хувьсагчийн тоо (үл мэдэгдэх n) нь хязгаарлалтын тооноос их байна m. Энэ системийн зэрэглэл нь m-тэй тэнцүү (систем нь илүүдэлгүй) бөгөөд (1) систем нь тогтвортой байна гэж бид үзэж байна. Дараа нь нийт тооноос m хувьсагч суурь хувьсагчийг бүрдүүлэх ба үлдсэн хувьсагчдыг үндсэн бус гэж нэрлэнэ.Хэрэв тэгшитгэлийн систем шийдэлтэй бол энэ нь мөн үндсэн шийдэлтэй байна.Тэгшитгэлийн системийн шийдэл (1) Хэрэв бүх бүрэлдэхүүн хэсэг нь сөрөг биш бол түүнийг зөвшөөрөгдөх гэж нэрлэдэг.Хэрэв шугаман тэгшитгэлийн систем нь зөвшөөрөгдөх шийдэлтэй бол энэ нь мөн үндсэн зөвшөөрөгдөх шийдэлтэй байна.(1) системийн бүх зөвшөөрөгдөх шийдүүдийн багц нь гүдгэр олонлог, өөрөөр хэлбэл олонлог юм. Шугаман програмчлалын шийдлийн шийдэл нь гүдгэр байна.Энэ олонлог нь хавтгай (гипер хавтгай)-аар үүсгэгддэг тул гүдгэр олон талт хэлбэртэй байна.Үндсэн зөвшөөрөгдөх шийдэл нь гүдгэр олон өнцөгтийн (түүний нүүр эсвэл орой) туйлын цэгтэй тохирч байна. Шугаман програмчлалын асуудлын оновчтой шийдэл байгаа бол үндсэн оновчтой шийдэл байна.
Шугаман програмчлалын бодлогын зорилгын функц нь хавтгайн тэгшитгэл (эсвэл гурваас дээш хувьсагчийн тоогоор гипер хавтгай) юм. Шугаман програмчлалын бодлогын зорилгын функц нь гүдгэр олон өнцөгтийн орой дээр эсвэл түүний аль нэг нүүрэн дээр хамгийн их эсвэл хамгийн бага утгад хүрдэг. Тиймээс шугаман програмчлалын асуудлын шийдэл нь гүдгэр олон өнцөгтийн орой дээр байрладаг бөгөөд үүнийг олохын тулд нөхцөлөөр тодорхойлогдсон гүдгэр олон өнцөгтийн орой дээрх зорилгын функцын утгыг тооцоолох шаардлагатай. асуудлын хязгаарлалт.
График аргаар шугаман програмчлалын асуудлыг шийдвэрлэх.
Математик загварыг бий болгоход бэрхшээлтэй байдаг нь хувьсагчдыг тодорхойлж, дараа нь зорилго, хязгаарлалтыг тэдгээр хувьсагчдын математик функц болгон илэрхийлэхэд оршино. Хэрэв загвар нь зөвхөн хоёр хувьсагчтай бол шугаман програмчлалын асуудлыг графикаар шийдэж болно. Гурван хувьсагчийн хувьд график шийдэл нь тодорхой бус болж, хувьсагчийн том утгууд нь бүр боломжгүй болдог. Гэсэн хэдий ч график шийдэл нь шугаман програмчлалын асуудлыг шийдвэрлэх ерөнхий аргыг боловсруулах үндэс суурь болох дүгнэлтийг гаргах боломжийг олгодог.
График аргыг ашиглах эхний алхам бол боломжит шийдлүүдийг геометрийн хэлбэрээр илэрхийлэх явдал юм. Бүх загварын хязгаарлалтыг нэгэн зэрэг хангасан зөвшөөрөгдөх шийдлийн бүсийг (ADA) байгуулах. Хүлээн авснаас хойш график шийдэлхувьсагчийг хэвтээ тэнхлэгийн дагуу болон босоо тэнхлэгийн дагуу зурна. ODD-ийг бүрдүүлэхдээ хувьсагчдын сөрөг бус байдлын нөхцлийг биелүүлэх хэрэгцээтэй холбоотой хүлээн зөвшөөрөгдөөгүй шийдлүүдийг олж авахаас урьдчилан сэргийлэх шаардлагатай. Барилга угсралтын ажил эхлэхээс өмнө ODR-ийг байрлуулах квадрантуудыг тодорхойлох шаардлагатай. Квадрантууд нь хувьсагчдын тэмдгээр тодорхойлогддог ба . Хувьсагчдын сөрөг бус байх нөхцөл нь тэдгээрийн зөвшөөрөгдөх утгуудын хүрээг эхний квадрат хүртэл хязгаарладаг. Хэрэв хувьсагч нь тэмдгээр хязгаарлагдахгүй бол тухайн бүсийг эхний ба хоёрдугаар квадратаар, хэрэв бол эхний ба дөрөв дэх квадратаар хязгаарлана. Хавтгай дээрх шийдлийн орон зайн бусад хил хязгаарыг "=" тэмдгээр сольсон тохиолдолд хязгаарлалтын тэгшитгэлийг ашиглан хийсэн шулуун шугамаар дүрсэлсэн болно. Энэ тохиолдолд дараахь зүйлийг анхаарч үзэх хэрэгтэй: бүх хязгаарлалтын баруун тал нь сөрөг биш байх ёстой. . Ямар нэгэн хязгаарлалт байвал< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.
Барилга угсралтын үр дүнд уусмалын орон зайг тодорхойлсон олон өнцөгтийг олж авна. Хэрэв хязгаарлалтын аль нэг нь "=" тэмдэгтэй бол ODD нь сегмент болж буурдаг.
Уусмалын олон өнцөгтийн муж эсвэл хил хязгаарт хамаарах цэг бүрт бүх хязгаарлалтууд хангагдсан тул эдгээр цэгүүдэд тохирох бүх шийдлүүд хүчинтэй байна. Шийдлийн орон зайд хязгааргүй тооны ийм цэгүүд агуулагддаг боловч үүнээс үл хамааран оновчтой шийдлийг олох боломжтой. Үүнийг хийхийн тулд хувьсагчдын хавтгайд зорилгын функцийн градиентийг байгуулах шаардлагатай. Хамгийн оновчтой цэгийг тодорхойлох нь шийдвэрлэх шаардлагатай асуудлаас хамаарна.
Хэрэв зорилгын функц нь хамгийн их байлгах бодлогыг тодорхойлсон бол оновчтой цэг нь градиентийг нэмэгдүүлэх чиглэлд, хэрэв багасгах бодлого тодорхойлогдсон бол зорилгын функцийн градиент буурах чиглэлд байрлана. Оновчтой цэгийг тодорхойлохын тулд бид зорилгын функцийг градиентийг хүлээн зөвшөөрөгдөөгүй шийдлийн бүсэд шилжүүлэх хүртэл нэмэгдүүлэх (бууруулах) чиглэлд шилжүүлнэ.
Шийдлийн орон зайн оновчтой цэгийг олсны дараа түүний координат ба түүний доторх зорилгын функцийн утгыг тодорхойлно. Оновчтой цэгийн сонголтын зөв эсэхийг шийдлийн олон өнцөгтийн орой дээрх зорилгын функцийг тооцоолох замаар шалгаж болно. ZLP-д боломжит шийдлүүдийн бүс нь үргэлж гүдгэр олонлог байдаг, өөрөөр хэлбэл. Ийм олонлог бөгөөд энэ олонлогт хамаарах дурын хоёр цэгийн хамт эдгээр хоёр цэгийг холбосон хэрчим нь мөн ижил олонлогт хамаарна. Аливаа функц нь градиентынхаа чиглэлд хамгийн хурдан нэмэгддэг.
Шугаман програмчлалын бодлогыг симплекс аргыг ашиглан шийдвэрлэх.
Шууд даалгавар.
Шугаман програмчлалын асуудлыг каноник хэлбэрээр авч үзье.
Функцийн хамгийн их (хамгийн бага)-ийг ол 
нөхцөлд
Энэ асуудлыг шийдэх гарц байгаа гэж үзэж байна. Оновчтой шийдлийг олохын тулд хэрэгжих боломжтой үндсэн шийдлүүдийг олж, тэдгээрээс оновчтой үндсэн шийдлийг сонгох шаардлагатай.
Симплекс арга нь шугаман програмчлалын асуудлыг шийдвэрлэх алгебрийн арга юм. Тооцооллын явцад уусмалын олон талт (SDP) оройнуудыг дараалан гүйлгэж, орой бүр дээр оновчтой байх нөхцлийг шалгана. Түүнчлэн, зэргэлдээ орой руу шилжих бүр нь зорилгын функцийг сайжруулж дагалддаг.
Симплекс аргын тооцооллын процедур.
LLP-ийг шийдэх график аргын хувьд оновчтой шийдэл нь шийдлийн орон зайн булангийн (туйлын) цэгүүдийн аль нэгэнд үргэлж тохирдог. Энэ үр дүн нь симплекс аргыг бүтээх үндэс суурь болдог. Симплекс арга нь шийдлийн орон зайн тодорхой геометрийн дүрслэлгүй байдаг.
Симплекс арга нь эхний боломжтой булангийн цэгээс эхлэн оновчтой шийдийн цэгийг олох хүртэл дараалсан шилжилтийг нэг туйлын цэгээс нөгөөд шилжүүлэх дараалсан процессыг хэрэгжүүлдэг.
Үүнд: – каноник хэлбэрээр үзүүлсэн LLP-ийн нийт хувьсагчийн тоо; - анхны хувьсагчийн тоо; - хязгаарлалтын тоо, - нэмэлт хувьсагчийн тоо, дараа нь 
.
Уусмалын олон талт орой бүр нь - тэгээс өөр хувьсагч ба () - тэг хувьсагчтай.
Тэггүй хувьсагчийг үндсэн, тэг хувьсагчийг үндсэн бус гэж нэрлэдэг.
Тэгш байдлын системийг зорилгын функцын тэгшитгэлээр нэмж оруулаад, энэ нь аливаа оройн суурь дээр үргэлж байдаг үндсэн хувьсагч байна гэж үзье.
Шийдлийг олж авахын тулд анхны зөвшөөрөгдөх үндэслэлийг эмхэтгэсэн бөгөөд үүнд суурь хувьсагчдыг нэгж вектор хэлбэрээр харуулах ёстой. Энэ нь өгөгдсөн оройг төлөөлж буй тэгшитгэлүүд нь үндсэн хувьсагч бүрийг 1-тэй тэнцүү коэффициенттэй зөвхөн нэг мөрөнд багтаах ёстой гэсэн үг юм.
ST(0) эхний алхам дээр симплекс хүснэгтийг бүрдүүлэх анхны зөвшөөрөгдөх үндэслэлийг сонгохдоо анхны хувьсагч нь тэгтэй тэнцүү бөгөөд үндсэн бус байна; оруулсан нэмэлт хувьсагчдаас нэгтэй тэнцүү коэффициент бүхий хувьсагчдыг сонгоно. (2) - (4) тэнцүү хувьсагч нь үндсэн бөгөөд 0-тэй тэнцүү коэффициент бүхий - мөрөнд багтсан болно. Симплекс хүснэгтийг бөглөхийн тулд зорилгын функцийг хэлбэрт шилжүүлэх шаардлагатай. 
. Тиймээс бид эцэст нь:
Симплекс хүснэгтийг бүрдүүлэхдээ дараах дүрмийг баримтална уу.
хамгийн зүүн талын баганад үндсэн хувьсагч ба ;
хамгийн баруун талын баганад хязгаарлалтын баруун хэсгүүдийг агуулна;
Эхний мөрөнд тодорхой дарааллаар хувьсагчдыг агуулна.
эхлээд, дараа нь үндсэн бус хувьсагч, үндсэн хувьсагч нь баруун талын (RF) өмнөх баганад байрладаг. Коэффицентүүдийг ST(0) дээр бичье:
| ХЭРВЭЭ | |||||||
| 1 | 0 | 0 | 0 | 0 | |||
| 0 | 1 | 0 | 0 | ||||
| 0 | 0 | 1 | 0 | ||||
| 0 | 0 | 0 | 1 |
Аль ч оройн оновчтой байдлыг одоогийн симплекс хүснэгтийн эгнээний үндсэн бус хувьсагчдын коэффициентээр тодорхойлно.
Хамгийн их болгох бодлогын хувьд – мөр дэх үндсэн бус хувьсагчдын бүх коэффициентүүд сөрөг биш (>0) байвал энэ орой нь оновчтой болно;
Багасгах асуудлын хувьд – мөр дэх үндсэн бус хувьсагчдын бүх коэффициент эерэг биш байвал энэ орой нь оновчтой болно.< 0).
Хэрэв хамгийн их болгох (багаруулах) асуудалд – эгнээний нэг үндсэн бус хувьсагч нь коэффициенттэй байвал.<0(>0), тэгвэл одоогийн цэг нь оновчтой биш бөгөөд суурийг өөрчлөх шаардлагатай. Үүнийг хийхийн тулд – мөрөнд хамгийн сөрөг (эерэг) коэффициенттэй үндсэн бус хувьсагчийг сонгоно. Сонгосон суурь бус хувьсагчийг шинэ суурьт оруулах тул орсон хувьсагч гэж нэрлэдэг. Баазаас гаргаж авах суурь хувьсагчийг хасагдсан хувьсагч гэнэ.
Оруулсан хувьсагчийг оруулсны дараа зэргэлдээ орой руу шилжих үед эхлээд "0" болж хувирдаг үндсэн хувьсагч нь хасагдсан хувьсагч байх болно.
Оруулсан хувьсагчийн баганыг идэвхжүүлэх багана гэж нэрлэнэ.
Оруулсан хувьсагчийн мөрийг зөвшөөрөх тэмдэгт мөр гэж нэрлэнэ.
Шийдвэрлэх багана ба мөрийн огтлолцол нь шийдвэрлэх элементийг (RE) тодорхойлно.
Хасагдсан хувьсагчийг тодорхойлохын тулд:
бүх үндсэн хувьсагчийн баруун талыг (мөрөөс бусад) шийдвэрлэх баганын харгалзах эерэг коэффициентээр хуваах;
гарсан харьцаанаас хамгийн багаг нь сонгоно.
"0" ба сөрөг утгатай хуваах боломжгүй, учир нь энэ нь огтлолцох орой байхгүй эсвэл ODR-ийн гаднах оройд хүргэдэг.
Зэргэлдээ орой руу шилжихийн тулд ST(0) ба ST(1) хоорондын холболтыг тодорхойлох шилжилтийн B(0) матрицыг үүсгэх шаардлагатай: ST(1) = B(0) ST(0).
(n - 1) баганатай n хэмжигдэхүүнтэй дурын квадрат матрицын хувьд нэгжийн нэгж векторууд нь нэгж матрицын нэгж векторуудын дагуу байрласан ба үндсэн диагональ дээр тэгээс өөр элементтэй дурын нэг багана, урвуу матрицдараах дүрмийн дагуу олно.
j баганын элемент бүрийг RE-д хувааж, шийдвэрлэх элементээс бусад тэмдгийг эсрэгээр нь өөрчилдөг.
Хиймэл анхны суурь. М - арга.
Хэрэв анхны хязгаарлалт нь тэгш байдлын "=" хэлбэрээр бичигдсэн эсвэл "" тэмдэгтэй бол зөвшөөрөгдөх анхны үндсэн шийдлийг нэн даруй олж авах боломжгүй, учир нь асуудлыг стандарт хэлбэрээр бичихдээ нэмэлт хувьсагчийг оруулсны дараа Үүссэн тэгшитгэлүүд нь нэгжийн орд хэлбэрээр анхны зөвшөөрөгдөх үндэслэлийг бүрдүүлэхийг зөвшөөрөхгүй бол хувилбар үүсч болно.
Энэ тохиолдолд анхны зөвшөөрөгдөх үндэслэлийг олохын тулд нэмэлт хиймэл хувьсагчдыг нэвтрүүлдэг. Хиймэл хувьсагч нь асуудлын агуулгатай холбоогүй бөгөөд зөвхөн холбогдох тооцооллын схем нь бүх хиймэл хувьсагч тэгтэй тэнцүү байх оновчтой шийдлийг өгөх тохиолдолд л тэдгээрийг нэвтрүүлэхийг зөвшөөрнө.
R хувьсагч нь ODR-ийн аль нэг орой руу цааш шилжих боломжийн үүднээс анхны зөвшөөрөгдөх үндэслэлийг тодорхойлдог. Зорилгын функцэд зохиомол хувьсагчийг ашиглахын тулд торгууль М-ийг нэвтрүүлсэн. Хамгийн их болгох бодлогод M нь сөрөг байна (M)<<0), в задаче минимизации М положительное (М>>0).
М шинж чанар: Анхны ZLP-ийн хувьсагч бүрийн авч чадах ямар ч утгыг тодорхойлох эцсийн утгатай нэмэх (хасах) үед түүний утга (М хувьсагчийн) өөрчлөгдөхгүй, тухайлбал,
Томъёо (1.2), хувьсагчийн сөрөг бус байдлын хязгаарлалт (тийм, үгүй) - томьёо (1.3) (1.1) i = 1,... m (1.2) (1.3) Шугаман програмчлалын асуудлыг шийдвэрлэх алгоритм нь тэдгээрийг авчрахыг шаарддаг. зорилгын функц байх үед каноник хэлбэрт оруулах томъёолол ...
Bluetooth
