Шугаман програмчлалын загварын математик тайлбар. Шугаман математик загварын хэлбэрүүд ба тэдгээрийн хувиргалт Шугаман програмчлалын загварын ерөнхий дүр төрх

1.

2. ашиглах заавар дэвсгэр. эдийн засаг дахь загварууд.

Математик загварууд нь эдийн засгийн тогтолцооны үл мэдэгдэх параметрүүдийн оновчтой утгыг тодорхойлох боломжийг олгодог бөгөөд энэ нь шийдвэр гаргах үйл явцад чухал ач холбогдолтой юм. Математик програмчлал нь сонгон шалгаруулах үйл явцыг оновчтой болгох боломжийг олгодог аппаратаар хангадаг хамгийн сайн сонголтуудэдийн засгийн систем дэх удирдлагын үйл явц дахь төлөвлөгөө.

Математик статистик, оновчлолын арга, эдийн засгийн аргуудад ашигладаг. кибернетик, туршилтын асуудлууд.

Эдийн засаг дахь нарийн төвөгтэй үйл явц, үзэгдлийг судлахдаа загварчлалыг ихэвчлэн ашигладаг - судалж буй объектын авч үзсэн шинж чанаруудын тодорхой тодорхой дүрслэл. Үүний мөн чанар нь судалж буй үзэгдлийг өөр цаг хугацаа, орон зайн масштабын загвар ашиглан туршилтын нөхцөлд хуулбарлаж байгаа явдал юм. Загвар гэдэг нь судалж буй системийн тодорхой шинж чанарыг судлахын тулд хуулбарласан тусгайлан бүтээсэн объект юм. Математик загварчлал нь судалж буй объектын талаархи мэдээллийг олж авах хамгийн төгс бөгөөд нэгэн зэрэг үр дүнтэй арга юм. Энэ нь эдийн засагт дүн шинжилгээ хийх хүчирхэг хэрэгсэл юм. Баригдсан загвар нь авч үзэж буй үзэгдэлд хангалттай байх үед загвар ашиглан хийсэн судалгааны үр дүн практик сонирхол татахуйц байх болно. бодит байдлыг тусгахад хангалттай.

2. математик програмчлал нь шинжлэх ухаан болох, түүний бүтэц. Оновчлолын асуудал. Эдийн засгийн асуудлыг шийдвэрлэхэд сонгодог оновчлолын аргыг хэрэглэхэд тулгарч буй бэрхшээлүүд.

Математик програмчлалхөгжиж буй хэрэглээний математикийн салбар юм онолын үндэслэлба туйлын асуудлыг шийдвэрлэх арга.

Математик програмчлал нь хэд хэдэн хэсгүүдээс бүрддэг бөгөөд тэдгээрийн гол нь дараахь зүйл юм.

1. Шугаман програмчлал.Энэ хэсэгт үл мэдэгдэх хувьсагчдыг нэгдүгээр зэрэглэлийн математик харилцаанд оруулсан бодлогууд орно.

2. Шугаман бус програмчлал.Энэ хэсэгт зорилгын функц ба (эсвэл) хязгаарлалтууд нь шугаман бус байж болох асуудлуудыг багтаасан болно.

3. Динамик програмчлал.Энэ хэсэгт шийдвэрлэх үйл явцыг тусдаа үе шатанд хувааж болох ажлууд багтсан болно.

4. Бүхэл тоон програмчлал.Энэ хэсэгт үл мэдэгдэх хувьсагч нь зөвхөн бүхэл тоон утгыг авч болох асуудлуудыг багтаасан болно.

5. Стохастик програмчлал.Энэ хэсэгт даалгавруудыг багтаасан болно санамсаргүй хэмжигдэхүүнзорилгын функц буюу хязгаарлалтуудад.

6. Параметр програмчлал.Энэ хэсэгт зорилгын функц эсвэл хязгаарлалтын үл мэдэгдэх хувьсагчийн коэффициентүүд зарим параметрээс хамаардаг асуудлуудыг багтаасан болно.

Математикийн програмчлалын асуудлыг шийдэхийн тулд экстремум олох сонгодог аргыг ашиглахад хэцүү байдаг, учир нь математикийн програмчлалын асуудлуудад зорилгын функц нь үл мэдэгдэх хувьсагчдын хүлээн зөвшөөрөгдсөн утгуудын бүсийн хил дээр туйлын утгад хүрдэг бөгөөд деривативууд байдаггүй. хилийн цэгүүд дээр. Зөвшөөрөгдөх цэгүүдийг бүрэн тоолох нь тэдний тоо их байгаа тул боломжгүй юм.

3. Математик загварын тухай ойлголт, дэвсгэрийн төрлүүд. загварууд

Математик загварбодит үзэгдэл, үйл явцыг математикийн тэмдэг, илэрхийллээр бичсэн хийсвэрлэл юм. Эдийн засгийн үйл явц, үзэгдлийн математик загваруудыг эдийн засаг, математик загвар гэнэ

Загваруудыг дараахь байдлаар хуваана.

1. шугаман, бүх хамаарлыг шугаман харилцаагаар дүрсэлсэн,

2. шугаман бус, шугаман бус харилцаа байдаг;

3. стохастик, судалж буй үйл явцын санамсаргүй шинж чанарыг харгалзан үзэх,

4. детерминист, бүх параметрийн дундаж утгыг харгалзан үздэг.

5. динамикСудалгаанд хамрагдаж буй системүүдийг хэд хэдэн хугацаанд хөгжүүлж буй загварууд,

6. статик, үүнд цаг хугацааны хүчин зүйлийг тооцдоггүй.

7. оновчлолхамааран сонголт хийх загварууд экстремизмзарим шалгуур,

8. оновчтой бус, үүнд оновчтой байдлын шалгуур байхгүй.

9. макро загварууд(бүх өрхөд)

10. микро загварууд(эдийн засгийн бие даасан холбоосууд эсвэл үйл явц).

Математик загварын төрлүүд: шугаман, шугаман бус, квадрат, бүхэл тоо, дискрет, параметрийн, шугаман бутархай, динамик, стохастик

4. Математик програмчлалын асуудлын ерөнхий тодорхойлолт.

Математик програмчлалын асуудлын ерөнхий мэдэгдлийг авч үзье.

Математик програмчлалын ерөнхий асуудал бол зорилгын функцийн оновчтой утгыг тодорхойлох явдал бөгөөд хувьсагчдын утгууд нь зөвшөөрөгдөх утгын тодорхой хязгаарт хамаарах ёстой. Математикийн тодорхойлолт оновчтой шийдэлолон хувьсагчийн функцийн экстремумыг (макс эсвэл мин) олоход илэрхийлэгддэг

Z = f(x1, x2, …, xn)

эдгээр хувьсагчийн өөрчлөлтийн өгөгдсөн мужид

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

Энд Ri нь ≥, =, ≤ тэмдгүүдийн нэг юм.

5. Үйлдвэрлэлийн төлөвлөгөөг оновчтой болгох асуудал. Эдийн засгийн томъёолол, бодлогын математик загварыг бий болгох.

Эдийн засгийн тохиргоо:

Тус компани үйлдвэрлэдэг nхэрэглэж буй бүтээгдэхүүний нэр төрөл мтүүхий эдийн төрөл. Үйлдвэрлэлийн нэгжийг үйлдвэрлэхийн тулд тодорхой хэмжээний түүхий эдийг нэг буюу өөр төрлийн түүхий эдийг ашигладаг. Аж ахуйн нэгжид төрөл бүрийн түүхий эд хязгаарлагдмал байдаг. Үйлдвэрлэлийн нэгжийг борлуулснаар компани тодорхой ашиг олдог. Аж ахуйн нэгж хамгийн их ашиг хүртэх ийм үйлдвэрлэлийн төлөвлөгөөг олох шаардлагатай байна.

Математик тохиргоо:

j = 1, n төрлийн бүтээгдэхүүний индексийг j гэж үзье

i - нөөцийн төрлийн индекс i = 1, м

болон ij нь түүхий эдийн зардал юм би-үйлдвэрлэлийн нэгжийг үйлдвэрлэх төрөл ж-р төрөл;

Аi - i-р төрлийн нөөцийн боломжит эзлэхүүний өгөгдсөн хязгаар;

Pj - j-р төрлийн үйлдвэрлэлийн нэгжийг борлуулснаас олсон ашиг;

xj нь j-р төрлийн гаралтын хэмжээ.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → хамгийн их

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Хоолны дэглэмийн үүрэг. Эдийн засгийн томъёолол, асуудлын математик загварыг бий болгох.

Эдийн засгийн тохиргоо

Зарим фермүүд мал тэжээдэг. Таргалахад ашигладаг nтэжээлийн төрөл. Шим тэжээлийн агууламж (кальци, фосфор гэх мэт) нь төрөл бүрийн тэжээлийн нэгж бүрт мэдэгддэг. Амьтдыг зөв хооллохын тулд тогтоосон хэмжээнээс багагүй шим тэжээлийг хэрэглэх шаардлагатай. Тэжээлийн нэгж бүрийн өртөг нь мэдэгдэж байна. Малын тэжээлийн хоолны дэглэмийг тодорхойлох шаардлагатай бөгөөд үүнд таргалалтын нийт зардал хамгийн бага байх болно.

Математик тохиргоо:

j - тэжээлийн төрлийн индекс, j = 1, n

i – шим тэжээлийн төрлийн индекс, i = 1, м

Аi - i-р төрлийн шим тэжээлийн өдөр тутмын хэрэгцээ;

Сj нь j-р төрлийн тэжээлийн нэгжийн өртөг юм.

Үл мэдэгдэх хувьсагчдыг танилцуулъя:

хj - малын тэжээлийн өдөр тутмын хэмжээ j-р хараххатуу.

Оруулсан тэмдэглэгээний хувьд даалгавар өгсөндараа нь бичих болно

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ ба mnxn ≥Am

xj ≥ 0, j = 1, n

7. Тээврийн даалгавар . Эдийн засгийн томъёолол, асуудлын математик загварыг бий болгох.

Эдийн засгийн тохиргоо :

Боломжтой мнэгэн төрлийн бүтээгдэхүүн нийлүүлэгчид болон nэнэ бүтээгдэхүүний хэрэглэгчид. Үйлдвэрлэлийн нэгжийг нийлүүлэгч бүрээс хэрэглэгч бүрт хүргэхэд мэдэгдэж буй нэгж зардал. Нийлүүлэгчийн нөөц хязгаарлагдмал. Хэрэглэгч бүрийн бүтээгдэхүүний хэрэгцээг бас мэддэг.

Бүтээгдэхүүнийг нийлүүлэгчээс хэрэглэгчдэд хүргэх ийм төлөвлөгөөг тодорхойлох шаардлагатай бөгөөд үүнд тээврийн нийт зардал хамгийн бага байх болно.

Математик тохиргоо :

Өгөгдсөн параметрүүдийн тэмдэглэгээг танилцуулъя.

j – хэрэглэгчийн индекс, j = 1, n

i – нийлүүлэгчийн индекс, i = 1, m

Аi - i-р ханган нийлүүлэгчээс авах боломжтой бүтээгдэхүүний хэмжээ;

Bj - j-р хэрэглэгчийн бүтээгдэхүүний эрэлтийн хэмжээ;

Cij нь нэгж бүтээгдэхүүнийг i-р ханган нийлүүлэгчээс j-р хэрэглэгч хүртэл тээвэрлэх нэгжийн зардал юм.

Үл мэдэгдэх хувьсагчдыг танилцуулъя:

хij - i-р ханган нийлүүлэгчээс j-р хэрэглэгч хүртэлх бүтээгдэхүүнийг тээвэрлэх хэмжээ.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → мин

Даалгаврын хязгаарлалт.

I. Нийлүүлэгч бүрээс та бэлэн байгаа тоо хэмжээнээс илүүгүй бүтээгдэхүүнийг буцааж авах боломжтой.

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Хэрэглэгч бүрийн бүтээгдэхүүний хэрэгцээг хангах ёстой

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Сөрөг бус нөхцөл: xij ≥0, i = 1, m ; j = 1, n

Математикийн мэдэгдлийг атираат хэлбэрээр бичих нь ихэвчлэн тохиромжтой байдаг.

, i = 1, м , j = 1, n

8. Даалгавар эсвэл даалгавар сонгох асуудал. Эдийн засгийн томъёолол, асуудлын математик загварыг бий болгох.

Эдийн засгийн тохиргоо :

Боломжтой nажлын төрөл ба nжүжигчид. Жүжигчин бүр ямар ч ажлыг гүйцэтгэх боломжтой, гэхдээ зөвхөн нэг ажил. Гүйцэтгэгч бүрийн ажил бүрийг гүйцэтгэх зардлыг тогтоодог. Гүйцэтгэгчдийг ажил гүйцэтгэхэд шаардагдах нийт зардал хамгийн бага байхаар хуваарилах шаардлагатай.

Математик тохиргоо .

Өгөгдсөн параметрүүдийн тэмдэглэгээг танилцуулъя.

i – ажлын индекс, i = 1, m

j - гүйцэтгэгчдийн индекс, j = 1, n

Cij нь i-р ажлыг j-р гүйцэтгэгчээр гүйцэтгэх зардал юм.

Үл мэдэгдэх хувьсагчдыг танилцуулъя. Энэ бодлогод үл мэдэгдэх хувьсагч нь зөвхөн 0 эсвэл 1 гэсэн хоёр утгыг авч болно. Ийм хувьсагчдыг null хувьсагч гэж нэрлэдэг.

1 - хэрэв j-р гүйцэтгэгч i-р ажилд томилогдсон бол;

0 - өөрөөр.

Оруулсан тэмдэглэгээний хувьд энэ асуудлыг дараах байдлаар бичиж болно.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → мин

I бүлэг хязгаарлалтууд.

Бүтээл болгонд зөвхөн нэг гүйцэтгэгч томилогдох ёстой.

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. хязгаарлалтын бүлэг.

Гүйцэтгэгч бүр зөвхөн нэг ажлыг гүйцэтгэх боломжтой:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = ( 0,1) i = 1, n ; j = 1, n

9. Материалыг огтлох асуудал. Эдийн засгийн томъёолол, асуудлын математик загварыг бий болгох.

Эдийн засгийн тохиргоо .

Ижил хэмжээтэй түүхий эдийг зүсэх зориулалтаар нийлүүлдэг. Нийт хог хаягдал нь хамгийн бага байхын тулд үүнийг тодорхой хэмжээгээр өгөгдсөн хэмжээтэй хоосон зайд хуваах шаардлагатай.

Математик тохиргоо .

Тэмдэглэгээг танилцуулъя:

i бол хоосон зайны индекс,

Аi - i-р төрлийн хоосон зайны шаардлагатай тоо;

j - зүсэх сонголтуудын индекс,

Cj - j хувилбарын дагуу анхны материалын нэгжийг огтлох үед хог хаягдлын хэмжээ;

ба ij нь j хувилбарын дагуу анхны материалын нэгжийг огтлох үед i-р төрлийн хоосон зайны тоо юм.

Үл мэдэгдэх хувьсагчийн тэмдэглэгээг танилцуулъя.

xj - j хувилбарын дагуу зүссэн түүхий эдийн хэмжээ.

Оруулсан тэмдэглэгээний хувьд энэ асуудлыг дараах байдлаар бичиж болно.

z \u003d С1x1 + С2х2 + ... + Сnxn → мин

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, n

Математик загварыг ашиглах нь түүхий эдийг 20% хүртэл хэмнэх боломжийг олгодог.

Зүсэх математик загварыг хоёр үе шаттайгаар бүтээдэг.

Эхний шатанд зүсэх сонголтуудыг бүтээдэг бөгөөд үүний үр дүнд n сонголтын тоо, төрөл бүрийн хоосон зайны тоог дараах байдлаар олж авна. янз бүрийн сонголтуудогтлох (aij), түүнчлэн хог хаягдлын үнэ цэнэ (Cj).

Эх сурвалжийн нэгжийг огтлох хувилбаруудыг барих ажлыг дараах хүснэгт хэлбэрээр гүйцэтгэв.

сонголтын дугаар

Хоосон i1

i2 хоосон

хоосон im

Хоосон зайг хэмжээнээсээ өсөхгүй дарааллаар байрлуулна. Хувилбаруудыг бүтээх ажлыг бүрэн тоолох аргаар гүйцэтгэдэг.

10. LP асуудлын загварын ерөнхий хэлбэр, түүний онцлог

ХХК-ийн ерөнхий хэлбэр нь:

z \u003d С1x1 + ... + Сnxn макс (мин)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

Ерөнхий хэлбэрээр R1 , R2 ,…, Rm тэмдэг бүр нь ≥, = эсвэл ≤ гэсэн тэмдгүүдийн аль нэгийг илэрхийлнэ.

LP асуудлын загварын ерөнхий хэлбэр нь дараах онцлогтой.

1. Хязгаарлалтын системийг тэгшитгэл (хатуу нөхцөл) ба тэгш бус байдал (хатуу бус нөхцөл) хэлбэрээр үзүүлэв.

2. Бүх хувьсагчдад сөрөг бус нөхцөл ногдуулдаггүй

3. Зорилгын функц нь хамгийн их эсвэл хамгийн бага руу чиглэдэг.

11. LP асуудлын загварын стандарт хэлбэр, түүний онцлог

Стандарт хэлбэр нь дараах байдалтай байна.

Зорилгын z функцийн хамгийн их буюу хамгийн бага утгыг ол:

z = С1x1 + … + Сnxn → макс (мин) (1)

Дараахь хязгаарлалттай.

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

LP асуудлын загварын стандарт хэлбэрийн онцлогууд нь дараах байдалтай байна.

1. хязгаарлалтын тогтолцоог тэгш бус байдлын (хатуу бус нөхцөл) хэлбэрээр үзүүлэв.

2. сөрөг бус нөхцөлийг бүх хувьсагчдад ногдуулдаг

3. зорилгын функц нь max эсвэл min байх хандлагатай

12. LP асуудлын загварын каноник хэлбэр, түүний онцлог

Каноник хэлбэр нь:

Зорилгын z функцийн минимумыг ол:

z = С1x1 + … + Сnxn → мин

Дараахь хязгаарлалттай.

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Каноник хэлбэрийн шинж чанарууд нь дараах байдалтай байна.

1. Хязгаарлалтын системийг тэгшитгэл (хатуу нөхцөл) хэлбэрээр үзүүлэв.

2. Сөрөг бус нөхцөл нь бүх хувьсагчид хамаарна

3. Зорилгын функц нь хандлагатай

Зарим эх сурвалжид каноник хэлбэрээр танилцуулсан LP асуудлын зорилгын функц нь хамгийн их хандлагатай байдаг. Энэ нь хамгийн их зорилгын функцэд зориулж боловсруулсан алгоритмын дагуу асуудлыг шийдвэрлэхэд хялбар байх үүднээс хийгддэг.

13. Боломжит, зөвшөөрөгдөх, оновчтой үндсэн ажлын төлөвлөгөө, LP даалгаврын ODZ

Тодорхойлолт 1.Асуудлын бүх хязгаарлалтыг хангасан үл мэдэгдэх хувьсагчдын утгууд шугаман програмчлал, гэж нэрлэдэг зөвшөөрөгдөх хувьсах утгууд эсвэл төлөвлөгөө .

Тодорхойлолт 2.Шугаман програмчлалын асуудлын бүх төлөвлөгөөний багцыг хувьсагчийн зөвшөөрөгдөх утгын домэйн гэж нэрлэдэг ( ОДЗ ).

Тодорхойлолт 3.Зорилгын функц нь ODZ дээр хамгийн бага (эсвэл хамгийн их) утгыг авдаг шугаман програмчлалын асуудлын төлөвлөгөөг гэж нэрлэдэг. оновчтой .

14. LP даалгаврын бичлэгийн төрөл: өргөтгөсөн, атираат, матриц, вектор.

LP асуудлын загваруудыг янз бүрийн хэлбэрээр бичиж болно.

1. Загварын бичлэгийн өргөтгөсөн харагдац

Z = c1 X1 + c2 X2 + … + cn Xn → мин

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Хураасан харагдац:

,

Xj ≥ 0, j = 1, n.

3. Матриц хэлбэрээр LP бодлогын загвар:

X ≥ 0

Хаана

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

өглөөний 1 цаг 2 … цаг X3 цаг

4. Вектор хэлбэрийн LP бодлогын загвар:

Хаана

X1 a11 a12 a1n a1

X2 , a21 , a22 , a2n , a2

… … … … …

Хn 1 цаг 2 цаг 2 цаг

15. LP асуудлын стандарт ба ерөнхий хэлбэрээс каноник хэлбэрт шилжих.Холболтын теорем

Ерөнхий эсвэл стандарт хэлбэрээс каноник хэлбэрт шилжихийн тулд дараах аргуудыг ашигладаг.

1. Хувьсах хөрвүүлэлт. Хэрэв зарим Xk хувьсагч эерэг биш (Xk ≤ 0) байвал шинэ Xk "хувьсагч гарч ирэх ба Xk " = –Xk . Мэдээжийн хэрэг, Xk " ≥ 0. Үүний дараа хязгаарлалт, зорилгын функц бүрт Xk хувьсагчийг [-ээр солино. – Xk "].

Хэрэв зарим Xt хувьсагч ямар нэгэн утгыг авч чадвал түүнийг сөрөг бус хоёр хувьсагчийн Xt' ба Xt'' зөрүүгээр солино, өөрөөр хэлбэл xt = Xt' – Xt'', Xt' 0 ≥ ба Xt'' ≥ 0.

2. Хязгаарлалтын хувиргалт.Загварын хязгаарлалтуудын аль нэг нь тэгш бус байдлын хэлбэртэй байвал зүүн талаас нь нэмэх (тэгш бус байдал ≤ төрлийн бол) эсвэл хасах (тэгш бус байдал ≥ төрлийн бол) тэгш бус байдал руу хөрвүүлнэ. Эдгээр хувьсагчдыг балансын хувьсагч гэж нэрлэдэг. Тэнцвэрийн хувьсагчдыг 0 коэффициент бүхий зорилгын функцэд оруулна. Үлдэгдэл хувьсагч нь индексийн утгыг аль хэдийн байгаа утгуудын дараа дарааллаар авдаг. Жишээлбэл, хязгаарлалтын систем нь 5 хувьсагчтай бол эхний балансын хувьсагч нь X6, хоёр дахь нь X7 гэх мэт болно.

16. ZLP загварын каноник хэлбэрээс стандарт руу шилжих

Каноник хэлбэрээс стандарт хэлбэрт шилжихийн тулд тус бүр

тэгшитгэлийг тэгш бус байдлын системээр солих:

Өөр нэг арга бол тэгшитгэлийн системийг тусгай хэлбэрт оруулж, зарим хувьсагчийг цаашид арилгах явдал юм.

Жордан-Гаусын аргыг ашиглан тэгшитгэл бүрийн үндсэн хувьсагчийг сонгоно. Ийм сонголт нь эквивалент (анхан шатны) Гауссын хувиргалтын тусламжтайгаар хийгддэг. Үүнд:

a) аливаа тэгшитгэлийг тэгээс өөр тогтмол тоогоор үржүүлэх;

б) бусад тэгшитгэлийн дурын тэгшитгэлийг дурын тогтмолоор үржүүлэх.

Матриц эсвэл хүснэгт хэлбэрээр хувиргахаас өмнө шугаман тэгшитгэлийн анхны системийг бичих нь тохиромжтой.

Бид асуудлыг стандарт хэлбэрээр бичдэг.

17. Хагас хавтгайн гипер хавтгай, тулгуур гиперплангийн тухай ойлголт.

18. Геометр. LP асуудлууд дахь хязгаарлалтын тогтолцоо ба зорилгын функцийн тайлбар

19. Гүдгэр олонлог: багцын туйлын (булангийн) цэгүүд. Гүдгэр олон өнцөгт

ТодорхойлолтӨгөгдсөн олонлогт хамаарах дурын хоёр цэгийн хамт тэдгээрийг холбосон хэрчмийг агуулж байвал М олонлогийг гүдгэр гэж нэрлэдэг.

гүдгэр багц

ТодорхойлолтМ олонлогийн x цэг нь өгөгдсөн олонлогт бүхэлд нь хамаарах ямар ч хэрчмийн дотоод биш бол булангийн эсвэл туйлын цэг гэж нэрлэдэг.

Теорем 1. Сегментийн аль ч цэгийг түүний булангийн цэгүүдийн гүдгэр хослолоор дүрсэлж болно.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 А ба В булангийн цэгүүдийн гүдгэр хослол

λ1 + λ2 = 1

Теорем 2. Гүдгэр битүү багцын дурын цэгийг түүний булангийн цэгүүдийн гүдгэр хослолоор төлөөлж болно.

20. LP асуудлыг шийдвэрлэх график аргын алгоритм

1. Анхны LPP нь стандарт хэлбэрээр байгаа эсэхийг шалгадаг, хэрэв үгүй ​​бол даалгаврыг стандарт хэлбэрт шилжүүлэх шаардлагатай.

2. Үл мэдэгдэх хувьсагчийн тоог шалгана. Хэрэв энэ тоо гурваас дээш байвал асуудлыг график аргаар шийдвэрлэх боломжгүй (ийм асуудлыг шийдэх өөр үр дүнтэй аргууд байдаг).

3. ZLP-ийн хувьсагчийн зөвшөөрөгдөх утгын бүсийг барьж байна.

4. Хөтөч векторыг барьж байна в .

5. Анхны изоцелийг ODZ-ээр (чиглэлийн вектортой перпендикуляр) зурдаг.

6. Анхны изокоэлийн сэтгэцийн хөдөлгөөнийг векторын чиглэлд явуулдаг в, хэрэв зорилгын функцийн хамгийн их утгыг тодорхойлсон бол, эсвэл эсрэг чиглэлд, түүний хамгийн бага утгыг тодорхойлсон бол изообьектив нь ODZ-ийн лавлагаа болох хүртэл. Лавлах изокоэл ба ОДЗ-ийн огтлолцох цэгүүд нь асуудлын оновчтой цэгүүд байх болно.

7. Оновчтой цэгийн координатыг тодорхойлохын тулд харгалзах шугаман тэгшитгэлийн системийг шийдэх шаардлагатай.

8. Зорилгын функцийн оновчтой утгыг олохын тулд хувьсагчдын оновчтой утгыг зорилгын функцэд орлуулж, түүний утгыг тооцоолох шаардлагатай.

20. график алгоритм. LP асуудлыг шийдвэрлэх арга

График аргын алгоритм.

1. Асуудлын хязгаарлалтын тогтолцооны нөхцөл бүрийг дараалан барьж байгуулснаар ODZ-ийн барилгын ажлыг гүйцэтгэдэг.

2. Зориулалтын функцын хувьсагчдын коэффициентээр чиглүүлэх вектор С-ийг байгуулна.

3. Анхны изокоэлийг эх үүсвэрээр чиглэлийн векторт перпендикуляр татна.

4. Зорилгын функцын хамгийн их утга тодорхойлогдвол C векторын утгыг нэмэгдүүлэх чиглэлд, хамгийн бага утга нь тодорхойлогдвол эсрэг чиглэлд изогоал болох хүртэл эхний изогоалыг оюун ухаанаар хөдөлгөдөг. ODZ-ийн лавлагаа. Лавлах изокоэл ба ОДЗ-ийн огтлолцох цэгүүд нь асуудлын оновчтой цэгүүд байх болно.

5. Оновчтой цэгийн координатыг тодорхойлохын тулд тэдгээрийн огтлолцол дээр хамгийн оновчтой цэг байрлах нөхцлүүдийн харгалзах шугаман тэгшитгэлийн системийг шийдэх шаардлагатай.

6. Зорилгын функцийн оновчтой утгыг олохын тулд оновчтой цэгийн координатыг зорилгын функцэд орлуулж, утгыг нь тооцоолох шаардлагатай.

23. LP бодлогын зөвшөөрөгдөх утгын хүрээ ба зорилгын функцийн талаархи теоремууд

ODZ теорем. LP асуудлын зөвшөөрөгдөх шийдлүүдийн домэйн нь гүдгэр олонлог (n хэмжээст орон зайд хаалттай, хязгаарлагдсан) юм.

Теорем 2. Шугаман програмчлалын бодлогын зорилгын функцийн тухай.

LLP-ийн зорилгын функц нь хувьсагчдын хүлээн зөвшөөрөгдсөн утгын бүсийн булангийн аль нэг цэг дээр оновчтой утгыг авдаг. Хэрэв зорилгын функц нь хэд хэдэн булангийн цэг дээр оновчтой утгыг авдаг бол эдгээр булангийн цэгүүдийн гүдгэр хослол болох дурын цэг дээр ижил утгыг авна.

24. Булангийн цэгийн тухай теорем. Хангалттай ба шаардлагатай нөхцөл

25. LP бодлогын шийдлийн шинж чанарын тухай теоремын үр дүн, дүгнэлт. Суурь шугамын тухай ойлголт.

Теоремоос гарах үр дагавар.

Тодорхойлолт. Төлөвлөгөө = (х1,х2,…,хn) эерэг координатууд нь шугаман бие даасан векторуудтай тохирч байгааг гэнэ. PLP үндсэн төлөвлөгөө .

Үр дагавар 1. Лавлагаа төлөвлөгөө нь m-ээс ихгүй эерэг координаттай байна.

Хэрэв энэ нь яг m эерэг координаттай бол ийм дэмжлэгийн загварыг доройтдоггүй, өөрөөр хэлбэл доройтдог гэж нэрлэдэг.

Үр дагавар 2. ODZ-ийн булангийн цэг бүр нь жишиг төлөвлөгөө юм.

27. Симплекс аргын алгоритм.

Симплекс аргаар LP асуудлыг шийдвэрлэхдээ дараах дарааллыг гүйцэтгэх шаардлагатай.

1. LP асуудал нь каноник хэлбэрээр байгаа эсэхийг шалгана. Хэрэв тийм биш бол анхны загварыг каноник хэлбэрт шилжүүлэх шаардлагатай болно.

2. Анхны жишиг төлөвлөгөө болон зорилгын функцийн утгыг энэхүү жишиг төлөвлөгөөнд сонгосон.

3. Анхны симплекс хүснэгтийг байгуулав.

4. Индексийн шугам дахь оновчтой байдлын үнэлгээний утгыг шалгана. Хэрэв эерэг тооцоо байхгүй бол оновчтой шийдлийг бичиж, алгоритм ажлаа дуусгана. Үгүй бол 5-р зүйл биелэгдэнэ.

5. Үндэслэлд векторыг оруулсан бөгөөд энэ нь хамгийн том эерэг үнэлгээтэй тохирч байна. Энэ баганыг идэвхжүүлэх багана гэж нэрлэдэг.

6. 0 томъѐогоор тооцсон симплекс харьцаатай тохирч байгаа баазаас вектор гарна< Ө ≤ . Данная строка называется разрешающей строкой.

7. Шинэ симплекс хүснэгт бүтээгдсэн. B ба C B багана нь зохих ёсоор өөрчлөгдөнө.Хүснэгтийн үлдсэн хэсгийг өмнөхөөс Гауссын хувиргалтаар дүүргэж, индексийн мөрийг m+1 мөр гэж тооцож, мөн Гауссын хувиргалтыг ашиглан өөрчилсөн. Бид энэ алгоритмын 4-р зүйлийн хэрэгжилтийг үргэлжлүүлнэ.

Хүснэгт бүрийг барьсны дараа та өмнөх догол мөрөнд өгсөн тооцооллыг тооцоолох томъёог ашиглан тооцооллын зөв эсэхийг шалгаж болно.

28. Симплекс аргаар асуудлыг шийдвэрлэх үндэслэлийг сонгох, анхны жишиг төлөвлөгөөг байгуулах.

29. Энгийн хүснэгтүүд, тэдгээрийн дүүргэлт. Индекс эгнээний коэффициентийг тооцоолох томъёо.

30 . Шугаман програмчлалын бодлогын төлөвлөгөөний оновчтой байдлын теорем нь асуудлыг симплекс аргаар шийдвэрлэх оновчтой байдлын үнэлгээний теоремын үр дагавар юм.

Теорем 1: Хэрэв систем дэх À j векторын хувьд

X 1 + a 1 м +1 X м +1 + a 1 м +2 X м +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 м +1 X м +1 + a 2 м +2 X м +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

Z j – c j > 0 харьцаа биелэгдсэн бол X B0 төлөвлөгөө оновчтой биш бөгөөд X B1 төлөвлөгөөнд Z (X B1) ≤ Z (X B0) байхаар шилжих боломжтой.

Энд Z j = (С, Ā j) нь векторуудын скаляр үржвэр юм.

C нь Z зорилгын функцийн үндсэн хувьсагчид дахь коэффициентуудаас бүрдэх вектор юм

À j нь суурь векторуудын хувьд харгалзах векторын тэлэлтийн коэффициентүүдээс бүрдэх вектор юм.

c j - X j хувьсагчтай зорилгын функц Z-ийн коэффициент

Үр дагавар -аас теоремууд: Хэрвээ зарим жишиг төлөвлөгөө Х-ийн бүх векторуудын Ā 1, Ā 2, …, Ā n бол Z j – c j хамаарал.< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Тиймээс, теорем ба үр дагавар нь дараагийн дэмжлэгийн төлөвлөгөө оновчтой эсэхийг тодорхойлох боломжийг олгодог бөгөөд хэрэв үгүй ​​бол зорилгын функцийн утга бага байх өөр дэмжлэгийн төлөвлөгөөнд шилжих шаардлагатай болно.

Сэтгэгдэл. Теорем ба үр дагавар нь асуудлыг хамгийн бага зорилгын функцтэй каноник хэлбэртэй гэж үздэг. Гэсэн хэдий ч симплекс аргыг хамгийн их зорилгын функцтэй асуудлыг шийдвэрлэхэд ашиглаж болно. Энэ тохиолдолд тооцооллын утгыг шинжлэхдээ тэдгээрийн эсрэг утгыг ашигладаг, өөрөөр хэлбэл бүх оновчтой байдлын тооцоо нь сөрөг биш (эерэг эсвэл сөрөг) байвал төлөвлөгөө оновчтой байх болно.

31. Суурь руу орж, баазаас гарах векторын сонголт. Энгийн харьцаа.

Шинэ лавлагааны төлөвлөгөөнд шилжихийн тулд үнэгүй векторуудын аль нэг нь шаардлагатай суурь руу оруулж, суурь векторуудын заримыг гаргана. Үндсэндээ оруулахын тулд бид дор хаяж нэг эерэг координаттай векторыг сонгоно. А m+1 вектор ийм вектор байг.

задрал -

Хариулах вектор, муур. координат нь сөрөг биш бол жишиг төлөвлөгөө байх ба эерэг координатын тоо m-тэй тэнцүү байна.

X1 векторын координат нь сөрөг биш байх ёстой, өөрөөр хэлбэл. .

Хэрвээ , тэгвэл энэ координат нь сөрөг биш байх болно.

(5) харьцаатай хамгийн бага утгыг i =1 үед авъя, хэрэв бид авбал

дараа нь векторын эхний координат 1 Xтэг болно.

(6) харилцааг гэж нэрлэдэг симплекс хамаарал. Тиймээс бид анхны суурь 0-ээс шилжсэн X(үндсэн векторууд A1, A2, ... Am) 1-р жишиг төлөвлөгөөнд X(үндсэн векторууд А2,А3,…,Аm, Am+1).

32. Хүснэгтийн зөвшөөрөгдөх элемент, түүний сонголт. Симплекс хүснэгтийг дахин тооцоолох бүрэн Жорданы хасах дүрэм.

33. Симплекс хүснэгтийг дахин тооцоолох "дөрвөлжин" дүрэм

34. Симплекс аргаар LP асуудлыг шийдвэрлэхдээ оновчтой төлөвлөгөөний өвөрмөц байдлын шинж тэмдэг, оновчтой төлөвлөгөөний багц, оновчтой төлөвлөгөө байхгүй байна.

Асуудлыг симплекс аргаар шийдвэрлэхдээ дараахь төрлийн оновчтой шийдлүүдийг гаргаж болно.

1. Өвөрмөц байдал . Хэрэв бүх чөлөөт векторуудын тооцоо нь хатуу сөрөг байвал олж авсан дэмжлэгийн загвар нь оновчтой бөгөөд өвөрмөц юм. (өмнөх догол мөр дэх жишээг үзнэ үү).

2. Альтернатив оновчтой (оновчтой шийдлийн багц).

Хэрэв чөлөөт векторуудын эерэг бус тооцооллын дунд дор хаяж нэг тэг үнэлгээ байгаа бол олж авсан дэмжлэгийн загвар нь оновчтой боловч өвөрмөц биш байх болно. Энэ тохиолдолд та бусад дэмжлэгийн төлөвлөгөөнүүд рүү очиж (тэг тооцоололд тохирсон векторуудыг суурь болгон оруулсан болно) дараа нь олж авсан оновчтой дэмжлэгийн төлөвлөгөөний гүдгэр хослол хэлбэрээр ерөнхий оновчтой шийдлийг бичиж болно.

3. Зорилгын функц нь доороос хязгаарлагдаагүй тул LLP-д оновчтой шийдэл байхгүй . Хэрэв симплекс хүснэгт эерэг оноотой бол бүх элементүүд өгөгдсөн баганасөрөг ба тэг байвал энэ векторыг суурьт оруулж болно. Гэсэн хэдий ч суурь векторуудын аль нь ч баазаас гарах боломжгүй. Үүнээс үзэхэд туслах бус төлөвлөгөөнд шилжих үед зорилгын функцийг цаашид бууруулах боломжтой болно.

4. Хязгаарлалтын систем нь зөрчилтэй тул LLP-д оновчтой шийдэл байхгүй. LLP-ийг шийдвэрлэхдээ ердийн симплекс арга нь анхны лавлагааны төлөвлөгөө байх ёстой тул шугаман тэгшитгэлийн систем нь мэдээжийн хэрэг зөрчилддөггүй. Тиймээс ердийн симплекс аргаар шийдвэрлэхэд ийм тохиолдол гарч болохгүй.

5. Хэрэв ОДЗ нь нэг цэгээс бүрдэх бол ийм асуудлын шийдэл нь өчүүхэн бөгөөд симплекс аргыг ашиглахгүйгээр гаргаж болно.

35. Хиймэл суурь аргыг хэзээ хэрэглэх вэ?

хиймэл.

36. М-бодлогыг зохиомол суурь аргаар байгуулах

Хэрэв шугаман програмчлалын асуудал нь каноник хэлбэртэй байвал бүх тэгшитгэлүүд нь үндсэн хувьсагчдыг агуулдаггүй, өөрөөр хэлбэл анхны суурь шугам байхгүй. Энэ тохиолдолд үндсэн хувьсагч байхгүй тэгшитгэлд +1 коэффициент бүхий сөрөг бус хувьсагчийг нэмэх шаардлагатай. Ийм хувьсагчийг нэрлэдэг хиймэл.

Зорилгын функцэд маш их эерэг тоо бүхий хиймэл хувьсагчийг нэмэх шаардлагатай (зорилгын функц нь хамгийн бага утгыг олох тул). Энэ тоог латин үсгээр тэмдэглэсэн M. Үүнийг +∞-тэй тэнцүү гэж үзэж болно. Үүнтэй холбогдуулан заримдаа хиймэл суурь аргыг М-арга гэж нэрлэдэг. Анхны асуудлыг ингэж өөрчлөхийг өргөтгөсөн бодлогыг бүтээх гэж нэрлэдэг. Хиймэл хувьсагч олохын тулд зорилгын функцтэй асуудлыг шийдэж байгаа бол зорилгын функц дээр маш их эерэг тоогоор нэмэх ёстой (зорилгийн функц нь хамгийн бага утгыг олох тул). Энэ тоог латин үсгээр тэмдэглэсэн M. Үүнийг +∞-тэй тэнцүү гэж үзэж болно. Үүнтэй холбогдуулан заримдаа хиймэл суурь аргыг М-арга гэж нэрлэдэг. Анхны асуудлыг ингэж өөрчлөхийг өргөтгөсөн бодлогыг бүтээх гэж нэрлэдэг. Хэрэв асуудлыг зорилгын функцээр шийдэж байгаа бол максимумыг олох гэж байгаа бол хиймэл хувьсагч нь -M коэффициенттэй зорилгын функцэд орно.

Тиймээс, өргөтгөсөн бодлогод бид суурь үзүүлэлттэй байна (хэдийгээр зарим үндсэн хувьсагч нь хиймэл байдаг).

Анхны симплекс хүснэгтийг бүтээв.

37. хиймэл суурийн аргаар индексийн шугам байгуулах

Тооцооллыг хоёр гишүүнээс бүрдүүлдэг тул индексийн мөрийг хоёр мөрөнд хуваасан анхны симплекс хүснэгтийг бүтээсэн. Дээд мөрөнд M-гүй үнэлгээний нэр томъёо, доод мөрөнд M-ийн коэффициентийг харуулав. Үнэлгээний тэмдэг нь M-гүй нэр томъёоны утга, тэмдгээс үл хамааран M-ийн коэффициентийн тэмдгээр тодорхойлогдоно. M нь маш том эерэг тоо юм.

Тиймээс суурьт оруулсан векторыг тодорхойлохын тулд доод индексийн шугамыг шинжлэх шаардлагатай. Хэрэв сууриас хиймэл вектор гаргаж авсан бол давхар асуудлын шийдлийг олж авах шаардлагагүй бол дараагийн симплекс хүснэгтүүдийн харгалзах баганыг орхиж болно (дараагийн сэдвийг үзнэ үү).

Бүх хиймэл векторуудыг сууриас хассаны дараа доод эгнээнд хиймэл вектортой харгалзах тооцооллоос бусад бүх тэг элемент байх болно. Тэд -1-тэй тэнцүү байх болно. Давхар асуудлын шийдлийг олж авах шаардлагагүй бол ийм мөрийг авч үзэхээс хасч, цаашдын шийдлийг ердийн симплекс аргаар хийж болно (дараагийн сэдвийг үзнэ үү).

38. Хиймэл суурь аргын оновчтой байдлын шалгуур. Тэмдгүүд нь анхны даалгаврын анхны үндсэн төлөвлөгөөг бүтээх явдал юм.

39. Хос симплекс аргын алгоритм

Хос симплекс аргын алгоритм:

1. ердийн аргаарчөлөөт нэр томъёоны шинж тэмдгийг үл тоомсорлож, анхны симплекс хүснэгтийг бөглөнө үү. Ийм асуудал нь анхны нэгжийн суурьтай байх ёстой гэж үздэг.

2. А0 чөлөөт гишүүдийн баганын хамгийн том үнэмлэхүй сөрөг элементээр чиглүүлэгч шугамыг сонгоно

3. Индексийн шугамын элементүүдийн чиглүүлэгч шугамын сөрөг элементүүдийн харьцааны хамгийн бага үнэмлэхүй утгын дагуу чиглүүлэгч баганыг сонгоно.

4. Жорданы бүрэн хасагдах дүрмийн дагуу симплекс хүснэгтийг дахин тооцоол

5. хүлээн авсан төлөвлөгөөг зөвшөөрөх эсэхийг шалгах. Зөвшөөрөгдөх лавлагааны төлөвлөгөөг олж авах шинж тэмдэг нь А0 баганад сөрөг элемент байхгүй байна. Хэрэв A0 баганад сөрөг элементүүд байгаа бол хоёр дахь догол мөрөнд очно уу. Хэрэв байхгүй бол тэд ердийн аргаар асуудлыг шийддэг.

6. Хос симплекс аргаар оновчтой шийдийг олж авах шинж тэмдэг нь энгийн симплекс аргын оновчтой байдлын шалгуур юм.

41. Нээлттэй ба хаалттай тээврийн загвар. Нээлттэй тээврийн загвараас хаалттай хэлбэрт шилжих.

Тээврийн ажлын төрлүүд.

Боломжтой ммэдэгдэж байгаа нөөц бүхий нэгэн төрлийн бүтээгдэхүүн нийлүүлэгчид болон nөгөгдсөн хэмжээний хэрэгцээтэй эдгээр бүтээгдэхүүний хэрэглэгчид. Тээврийн нэгжийн зардлыг бас мэддэг.

Хэрэв бараа материалын эзлэхүүний нийлбэр нь бүх хэрэглэгчдийн хэрэгцээний хэмжээтэй тэнцүү бол ийм асуудлыг нэрлэнэ. хаалттай тээврийн даалгавар

(жишээ нь, хэрэв ∑ Ai = ∑ Bj бол), эс бөгөөс тээврийн асуудлыг нэрлэнэ. нээлттэй. Тээврийн асуудлыг шийдэхийн тулд хаах хэрэгтэй.

Нээлттэй тээвэрлэлтийн даалгаврыг дараах аргаар хаалттай болгон хувиргаж болно.

∑Ai > ∑Bj гэж бичье. Энэ тохиолдолд ∑Ai – ∑Bj хэрэгцээний хэмжээ бүхий зохиомол n + 1 хэрэглэгчийг нэвтрүүлэх шаардлагатай. Нийлүүлэгчээс зохиомол хэрэглэгч хүртэлх тээвэрлэлтийн нэгж зардлыг 0 гэж үздэг, учир нь үнэндээ ийм тээвэрлэлт хийхгүй. хийгдэж, бүтээгдэхүүний зарим хэсэг нь ханган нийлүүлэгчид үлдэх болно.

Хэрэв ∑Bj > ∑Ai бол . Энэ тохиолдолд ∑Bj – ∑Ai бараа материалын эзэлхүүнтэй зохиомол m + 1 нийлүүлэгчийг нэвтрүүлэх шаардлагатай. Хуурамч ханган нийлүүлэгчээс хэрэглэгчдэд хүргэх тээврийн нэгжийн зардлыг 0-тэй тэнцүү гэж үздэг, учир нь үнэн хэрэгтээ ийм тээвэрлэлт хийхгүй бөгөөд хэрэглэгчид зарим бүтээгдэхүүнийг хүлээн авахгүй.

42. Тээврийн бодлогод анхны тархалтыг байгуулах аргууд: баруун хойд булангийн арга ба матрицын хамгийн бага элементийн арга.

Лавлагаа төлөвлөгөө боловсруулах баруун хойд техник. Энэхүү техникийн дагуу хөдөлгөөний утгыг бүрдүүлэх нь s.-z-ээс эхэлдэг. ширээний булан, өөрөөр хэлбэл. x11 нүднээс. Энэ аргын дагуу юуны түрүүнд анхны ханган нийлүүлэгчийн барааг хуваарилдаг. Түүгээр ч барахгүй анхны ханган нийлүүлэгч нь эхлээд эхний хэрэглэгчийнхээ сэтгэлд нийцдэг. Дараа нь ханган нийлүүлэгчид бараа хэвээр байгаа бол

Матрицын хамгийн жижиг элементийн арга.

Аргын мөн чанар нь матрицын хамгийн бага тарифтай тохирч байгаа хамгийн дээд хангамжийг үүрэнд үргэлж оруулдагт оршино.

Нэгдүгээрт, бид шугамын хамгийн бага үнэ ажиглагдаж буй шугамын нүднүүдэд тэмдэглэгээ хийдэг (жишээлбэл, ▼ тэмдгээр). Дараа нь бид хүснэгтийг баганаар тойрон эргэлдэж, баганаар хамгийн бага үнэ байгаа нүдэнд ижил тэмдэглэл хийнэ.

Цаашдын хуваарилалтыг эхлээд хоёр тэмдэгтэй, дараа нь нэгээр нь аль болох хол зайд хийж, дараа нь асуудлыг (m + n - 1) дүүргэлт болгон тэнцвэржүүлнэ. Хүснэгтийг зүүнээс баруун тийш, дээрээс доошоо дамжуулахдаа бид дүүргэлтийг зохион байгуулдаг.

43. Тээврийн даалгаврын шинж чанар

Тээврийн асуудал нь дараах теоремуудад тусгагдах зарим шинж чанартай байдаг.

Теорем 1. Хаалттай тээврийн асуудал үргэлж шийдэлтэй байдаг.

Теорем 2. Хэрэв бүтээгдэхүүний нөөцийн хэмжээ ба хэрэгцээний хэмжээ бүхэл тоо байвал тээврийн асуудлын шийдэл мөн бүхэл тоо байх болно.

Теорем 3. Хаалттай тээврийн асуудлын хязгаарлалтын систем нь үргэлж шугаман хамааралтай байдаг.

Энэ теоремоос харахад тээврийн хаалттай бодлогын тархалт үргэлж m + n – 1 үндсэн хувьсагч ба (m – 1) (n – 1) чөлөөт цагийн хувьсагчтай байна.

44. Тээврийн асуудалд доройтсон хуваарилалт, доройтлоос ангижрах. Загалмайлсан хослол.

Хэрэв эсийн тоо m + n - 1-ээс бага байвал тархалтыг доройтсон гэж нэрлэдэг.

45. Тээврийн асуудлын оновчтой байдлын теоремууд.

Теорем.Хэрэв зарим хуваарилалтын хувьд тээврийн үүрэг та

нөхцөл хангагдсан байна:

a). ui+vj = cij эзлэгдсэн эсийн хувьд

б) ui+vj ≤ сij, чөлөөт нүдний хувьд,

тэгвэл энэ хуваарилалт оновчтой болно.

ui утгыг мөрийн потенциал гэж нэрлэдэг ба vj утгыг баганын потенциал гэж нэрлэдэг.

46. ​​Боломж ба тэдгээрийг тооцоолох арга.

Мөр ба баганын потенциалыг олохын тулд оновчтой байдлын теоремын а) нөхцөлийг үндэслэн дараах үндэслэлийг ашиглана.

Энэ нөхцөл дээр үндэслэсэн тэгшитгэлийн тоо нь m + n – 1, үл мэдэгдэх ui ба vj тоо нь m + n байна. Тэр. хувьсагчийн тоо нь тэгшитгэлийн тооноос их байх ба бүх тэгшитгэлүүд нь шугаман хамааралгүй. Ийм шугаман тэгшитгэлийн системийн шийдэл нь тодорхойгүй тул потенциалуудын аль нэгэнд ямар ч утгыг өгөх ёстой. Практикт ui = 0. m + n – 1 үл мэдэгдэх хувьсагчтай m + n – 1 тэгшитгэлийн системийг олж авдаг. Энэ системийг ямар ч аргаар шийдэж болно. Практикт потенциалыг тооцоолохын тулд тэдгээрийн аль нэг потенциал нь мэдэгдэж байгаа эзлэгдсэн эсүүдийг авч үзэх ба теоремын а) нөхцөлийг үндэслэн үл мэдэгдэх потенциалын утгыг тооцдог.

47. Тээврийн даалгаврын хуваарилалтын оновчтой байдлын тооцоо, оновчтой байдлын шалгуур.

Теоремын b) хамааралд үндэслэн тооцооллыг тооцоолох дараах томъёог бичиж болно: δ ij= ui + vj – сij. Тооцооллыг замын хөдөлгөөний ачаалалтай андуурахгүйн тулд тэдгээрийг (тооцоо) тойрог хэлбэрээр хавсаргасан болно.

Чөлөөт TK эсүүдийн оновчтой байдлын тооцоолол нь тархалтыг оновчтой эсэхийг шалгадаг оновчтой байдлын шалгуур юм. Хэрэв бүх чөлөөт эсийн тооцоо 0-ээс бага эсвэл тэнцүү байвал энэ хуваарилалт оновчтой болно.

48. тээврийн асуудалд хангамжийн дахин хуваарилалт

Хэрэв хуваарилалт оновчтой биш бол хангамжийг дахин хуваарилах шаардлагатай.

Дахин хуваарилахын тулд дахин тооцоолох циклийг бий болгодог. Хамгийн өндөр эерэг оноотой нүдийг нүдээр сонгоно. Энэ нүдийг "+" тэмдгээр тэмдэглэсэн, өөрөөр хэлбэл тодорхой хэмжээний хүргэлтийг бүртгэх шаардлагатай. Гэхдээ дараа нь энэ баганын тэнцвэр алдагдах тул энэ баганын эзлэгдсэн нүднүүдийн аль нэгийг "-" тэмдгээр тэмдэглэсэн байх ёстой, өөрөөр хэлбэл нийлүүлэлтийн хэмжээг ижил хэмжээгээр бууруулах ёстой. Гэхдээ дараа нь энэ шугамын үлдэгдэл өөрчлөгдөх тул энэ шугамын зарим эзлэгдсэн нүдийг "+" тэмдгээр тэмдэглэх ёстой. Энэ үйл явцанхны нүд байрлаж байсан мөрөнд "-" тэмдэг тавих хүртэл үргэлжилнэ.

Аливаа чөлөөт эсийн хувьд дахин тооцоолох мөчлөг байдаг бөгөөд үүнээс гадна цорын ганц байдаг.

49. дахин хуваарилалтын хэлхээ, тэдгээрийн төрөл.

Харж байгаа тээврийн төлөвлөгөө нь оновчтой биш байх ёстой, өөрөөр хэлбэл. харьцангуй эерэг тооцоо байдаг. Дараа нь тааламжгүй эсийг (тааламжгүй хэсгүүдийн нэг) авч, түүнд зориулж дахин тооцоолох циклийг барьж, үүний дагуу төлөвлөсөн тээвэрлэлтийг дахин хуваарилдаг. Цикл нь тасархай хаалттай шугам хэлбэрээр баригдсан бөгөөд сегментүүд нь баганын дагуу эсвэл шугамын дагуу явагддаг. Эвдэрсэн шугамын нэг буланд бүтээгдэхүүнийг нэхэмжилж буй таагүй нүд байдаг бөгөөд бусад буланд нүднүүд дүүрсэн, i.e. циклийг байгуулахдаа бид нэр дэвшигчийн нүднээс эхэлж, тасархай шугамын дагуу буцаж ирдэг боловч бид зөвхөн дүүргэсэн нүднүүдэд (үндсэн хувьсагчдад тохирсон) эргэлт хийх боломжтой. Тааламжгүй эс нь Q бүтээгдэхүүнд нэхэмжлэл гаргахыг зөвшөөрнө үү. Хүснэгт дэх тэнцвэргүй байдлаас урьдчилан сэргийлэхийн тулд дараахь зүйлийг хийх шаардлагатай.

боломжтой урсгал дээр Q нэмэх, хасах. Булангийн тоо тэгш тоотой тул нүднүүдийн хагаст Q-г нэмж, нөгөө талд нь хасах болно. Циклийг цагийн зүүний дагуу эсвэл цагийн зүүний эсрэг нэр дэвшигчийн нүднээс эхлүүлж, тэнд сайн Q-г байрлуулж, Q-г хөрш нүднээс хасч, дараа нь нэмнэ гэх мэт. Q-ийн утгыг өөрөө сонгосон бөгөөд ингэснээр аль нэг нүдийг хоослох боловч нийлүүлэлтийн аль нь ч сөрөг болохгүй.

Үүнийг хийхийн тулд Q-г хассан нүднүүдээс хамгийн бага бууруулж болох хэмжээтэй тэнцүү Q-г сонгох ёстой. Дараах зурагт. 7.1 ба 7.2-т бид мөчлөгийн жишээ, тооцооллын дүрмийг харуулах болно.

Энэ тохиолдолд хоёр нүд хоосорно. Гэхдээ зөвхөн нэг эс харилцан хоосон байх шаардлагатай. Тэд үүнийг хийдэг: хоосорч буй нүднүүдийн нэгийг шинэ хүснэгтэд хоосон болгож, нөгөө хоосон нүдэнд тэгийг тавьдаг. Энэ нүдийг шинэ хүснэгтэд үндсэн (дүүргэсэн) гэж үзнэ.

50. Дахин хуваарилалтын эзлэхүүний сонголт.

Тээвэрлэсэн бүтээгдэхүүний хэмжээг тодорхойлох. Тооцооллын мөчлөгт шилжсэн бүтээгдэхүүний эзлэхүүнийг тодорхойлохдоо бид дараахь хоёр зүйлийг харгалзан үзэх ёстой.

a) Хүснэгтийн нүднүүдэд хувиргасны дараа сөрөг тоог авах ёсгүй;

б) эзлэгдсэн эсийн аль нэг нь чөлөөтэй байх ёстой.

Эдгээр нөхцөлийг хангахын тулд тээвэрлэсэн бүтээгдэхүүний хэмжээг дараах байдлаар сонгох шаардлагатай: θ=min (хij) -, энд (хij) нь дахин тооцоолох мөчлөгийн нүднүүдээс "" тэмдэглэгдсэн тээвэрлэлтийн хэмжээ юм. -” тэмдэг.

θ = мин(20;30)=20

θ нь "+" тэмдгээр тэмдэглэгдсэн нүднүүдийн утгуудад нэмэгддэг. θ нь "-" тэмдгээр тэмдэглэгдсэн нүднүүдийн утгуудаас хасагдана. Үлдсэн нүднүүдийн нийлүүлэлтийн утгыг өөрчлөхгүйгээр дарж бичнэ. Үүний үр дүнд бид дараах хүснэгтийг авна.

53. Потенциалын аргын алгоритм.

Алгоритм:

1. Даалгаврын хувьд тэгшитгэл хангагдсан эсэхийг шалгана уу үгүй бол зохиомол ханган нийлүүлэгч эсвэл хэрэглэгчийг даалгаварт оруулсан болно

2. Даалгаврын нөхцөлийг тээвэрлэх.хүснэгт хэлбэрээр бичнэ

3. Анхны суурь шугамыг барьж байна

4. Хангамж, хэрэглэгчдийн боломжуудыг тодорхойлсон

5. Чөлөөт эсийн оноог тооцдог. Хэрэв бүгд сөрөг биш бол төлөвлөгөө нь оновчтой бөгөөд та хариултаа бичих хэрэгтэй. Тээврийн матриц X ба тээврийн зардлын хэмжээг тодорхойлно. Хэрэв төлөвлөгөө нь оновчтой биш бол, өөрөөр хэлбэл, таамаглалуудын дунд сөрөг үзүүлэлтүүд байгаа бол хамгийн их сөрөг утгатай ирээдүйтэй нүдийг сонго. тооцоолж, дараагийнх руу шилжинэ.

6. Хэтийн төлөвийн нүдийг ачаалах. Шинэ суурь төлөвлөгөөг тээврийн хүснэгт хэлбэрээр бэлтгэ. 4-р цэг рүү оч.

54. Бүтээгдэхүүн үйлдвэрлэх, тээвэрлэх зардлын бүртгэл. Нийлүүлэлтийн хориг бүхий тээвэрлэлтийн даалгавар.

Зарим асуудлыг шийдвэрлэхдээ зөвхөн ачаа тээвэрлэхээс гадна тээвэрлэсэн бүтээгдэхүүн үйлдвэрлэх зардлыг харгалзан үзэх шаардлагатай. Үүнийг хийхийн тулд матриц дамжуулалтанд. даалгавар

Энд Cij ' нь нэг нэгж бүтээгдэхүүн үйлдвэрлэхэд буурсан өртөг юм.

Cij “- нэг нэгж бүтээгдэхүүнийг тээвэрлэх зардал.

Нийлүүлэлтийн хориг бүхий даалгавар.

Зарим тохиолдолд бүтээгдэхүүнийг ямар ч замаар тээвэрлэх боломжгүй байдаг.

Үүнийг хийхийн тулд тээвэрлэхийг хориглосон тээврийн даалгаврын матрицад хориглосон тариф M-ийг оруулна.Цаашилбал, даалгаврыг ердийн аргаар шийддэг.Гэхдээ энэ нүд үргэлж сөрөг эсийн оноотой тохирч байх болно. .

55. тээврийн асуудалд тодорхой хүргэлтийн зайлшгүй шинж чанарыг харгалзан маршрутын нэвтрүүлэх чадварыг хязгаарлах.

маршрутын нэвтрүүлэх чадварын хязгаарлалтыг бүртгэх.

Тээврийн зарим ажилд, зарим чиглэлд, бага нэвтрүүлэх чадварХэрэглээний цэгийн хэрэгцээг хангахад шаардагдахаас илүү.

тээврийн асуудалд тодорхой хүргэлтийн зайлшгүй шинж чанарыг харгалзан үзэх.

Зарим тохиолдолд даалгавар нь жишээлбэл, Ak Bs-ийн маршрутын дагуу А хэмжээтэй нэгжийг хүргэхийг шаарддаг. Энэ тохиолдолд заавал нийлүүлэх хэмжээг А цэгийн үйлдвэрлэлийн хэмжээ ба S Bs хэмжээнээс хасч, нэмэлт нийлүүлэлтийн талаар асуудлыг шийдвэрлэнэ. Оновчтой шийдлийг олж авсны дараа нийлүүлэлтийг Ak Bs үүрэнд байгаа эзэлхүүнд заавал нэмнэ.

56. Эдийн засгийн боломжтой дүгнэлт. нээлттэй тээврийн асуудлын оновчтой хуваарилалтын тайлбар.

Оновчтой хуваарилалтыг хүлээн авсны дараа анхны асуудал руу буцаж, зохих хэмнэлттэй болгох шаардлагатай. дүгнэлт. Тэдгээр нь дараах байдалтай байна.

1. Хэрэглээний цэгийг нэвтрүүлсэн бол энэ нь дүн шинжилгээ хийж буй системд хэт их үйлдвэрлэлийн хэмжээ байгаа гэсэн үг бөгөөд авч үзэж буй системд хохирол учруулахгүйгээр эдгээр үйлдвэрлэлийн цэгүүдийн хүчин чадлыг холбох хэрэгслийн хэмжээгээр бууруулах боломжтой болно. зохиомол хэрэглээний цэгтэй холбоотой байдаг.

2. Хэрэв зохиомол үйлдвэрлэлийн цэгийг нэвтрүүлсэн бол энэ нь үйлдвэрлэлийн бодит цэгүүдийн хүчин чадал хангалтгүй, тэдгээрийг нэмэгдүүлэх шаардлагатай гэсэн үг юм. Хуурамч үйлдвэрлэлийн цэгтэй холбогдсон хэрэглээний цэгүүдэд хамгийн ойр байрлах үйлдвэрлэлийн цэгүүдийн хүчин чадлыг нэмэгдүүлсэн. Үйлдвэрлэгчийн хүчин чадал нь холбох үнээр нэмэгддэг. Үүнийг хийхийн тулд үйлдвэрлэлийн зохиомол цэгтэй холбоотой хэрэглээний цэгийн баганыг авч үзээд хамгийн бага тарифыг олоорой. Энэхүү тарифт тохирсон үйлдвэрлэлийн цэгийн хүчин чадлыг заавал биелүүлэх хэмжээгээр нэмэгдүүлэх нь хамгийн үр дүнтэй байдаг.

57. Хоёрдмол байдлын тухай ойлголт. Үйлдвэрлэлийн төлөвлөгөөг оновчтой болгох асуудлын жишээн дээр давхар асуудлыг эдийн засгийн томъёолол.

Давхар бодлого гэдэг нь эх буюу шууд бодлогын нөхцлөөс шууд тодорхой дүрмийг ашиглан томъёолсон шугаман програмчлалын туслах бодлого юм.

Үйлдвэрлэлийн төлөвлөгөөг оновчтой болгох ажил байг. Энэ нь дараах байдалтай харагдаж байна.

Анхны даалгавар:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | 2 цагт

……………….. |.. (1)

а т 1 x 1 +a т 2 x 2 + ... + a т n x n ≤v 1 | цагт т

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - j-р төрлийн бүтээгдэхүүн үйлдвэрлэхэд зарцуулсан i-р төрлийн түүхий эдийн тоо.

Давхар асуудал

Аж ахуйн нэгж ямар ч шалтгаанаар бүтээгдэхүүн үйлдвэрлэх боломжгүй байг. Сул зогсолтын зардлыг бууруулахын тулд компани өөрт байгаа түүхий эдээ борлуулах боломжтой. Түүхий эдээ ямар үнээр борлуулах ёстой вэ?

i - аж ахуйн нэгжид байгаа i-р төрлийн түүхий эдийн үнэ.

a 11 y 1 + a 21 y 2 + ... + a т 1 жил т≥s 1

a 12 x 1 + a 22 y 2 + ... + a т 2 x n ≥s 2

……………….. (1’)

а 1х y 1 +a 2х y 2 +…+ a tpцагт т≥s П

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b м y м ->мин(3’)

58. Шууд болон давхар асуудлын бүтцийн элементүүдийн хоорондын харилцан хамаарал

Шугаман програмчлалын асуудал бүрийг холбож болно

дараах дүрмийн дагуу давхар асуудал:

1. Анхны асуудлын бүх хязгаарлалтад чөлөөт нэр томъёо заавал байх ёстой

баруун талд байх ба зүүн талд үл мэдэгдэх нэр томъёо.

2. Хязгаарлалт-эхний асуудлын тэгш бус байдал нь шинж тэмдэгтэй байх ёстой,

нэг чиглэлд чиглүүлсэн.

3. Анхны бодлого дахь зорилгын функцийг багасгасан тохиолдолд тэгш бус байдлын хязгаарлалтыг “≤” тэмдгээр бичвэл хос бодлогод зорилгын функц багасаж, тэгш бус байдлын хязгаарлалтын тэмдгүүд “≥” болно.

4. Анхны асуудлын хязгаарлалт бүр нь in хувьсагчтай тохирч байна

давхар даалгавар. Хэрэв хувьсагч нь тэгш бус байдалд тохирч байвал энэ нь сөрөг биш, хэрэв тэгшитгэлтэй тохирч байвал хувьсагч тэмдэгт хязгаарлалтгүй ("дурын") байна.

5. Хос бодлогын хязгаарлалт дахь хувьсагчдын коэффициентийг дараахаас бүрдэх матрицыг шилжүүлснээр олно.

анхны бодлогын хувьсагчдын коэффициент.

6. Анхны бодлогын чөлөөт нөхцөлүүд нь at коэффициентүүд юм

хос бодлогын зорилгын функцэд хувьсагч, чөлөөт

Хос бодлогын нэр томъёо нь хувьсагчдын коэффициент юм

Анхны асуудлын функцууд.Бид мөн хоёрдмол байдлын хамаарал нь харилцан, өөрөөр хэлбэл. хос даалгавартай харьцуулахад давхар даалгавар нь анхныхтай давхцаж байна.Хос хос даалгавар нь тэгш хэмтэй ба тэгш бус гэж хуваагддаг. Тэгш хэмтэй хосын хувьд анхдагч болон давхар бодлогын хязгаарлалтууд нь хатуу бус тэгш бус байдал тул хоёр бодлогын хувьсагчид зөвхөн сөрөг бус утгыг авч болно.

59. Загварын стандарт, каноник, ерөнхий хэлбэрээр бичигдсэн анхны бодлогод давхар бодлого байгуулах (тэгш хэмтэй ба тэгш бус хос бодлого барих)

Стандарт маягт (эх хувь)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Хос стандарт

Σ a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b i y i ->мин(3)

Канон хэлбэрийн анхны асуудал:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Хос каноник

Σ a ij y i ≤ c j , j=1,n(1)

y i - дурын (2)

F = Σ b i y i ->max(3)

Хос асуудлын эдийн засгийн тайлбарыг өгье. Нөөцийг зохистой ашиглах асуудлыг авч үзье. Байгууллагад n төрлийн бүтээгдэхүүн үйлдвэрлэхэд ашиглаж болох b1,b2,...bm нөөцтэй байг. Мөн j төрлийн бүтээгдэхүүний нэгжийн өртөг cj (j=1,n) болон нэгжийг үйлдвэрлэх i-р нөөцийн (i=1,m) зарцуулалтын хэмжээг мэдье. j-р үйлдвэрлэл– aij.Хүй (j=1,n) төрөл бүрийн үйлдвэрлэлийн хэмжээг тодорхойлох шаардлагатай бөгөөд нийт өртгийг хамгийн их байлгах.

f= c1x1+…+cnxn (1)

Үүний зэрэгцээ нөөцийн хэрэглээ нь тэдгээрийн хүртээмжээс хэтрэхгүй байх ёстой.

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Эдийн засгийн утгаараа мэдэгдэж байгаа бүх зүйл сөрөг биш юм:

Xj>=0 (j=1,n). (3)

Энэ асуудал нь тэгш хэмтэй хос бодлого үүсгэдэг гэдгийг анхаарна уу.

Тэгш хэмт бус хос асуудлууд.

ZLP-ийг каноник хэлбэрээр хамгийн дээд хэмжээнд нь авъя:

Макс Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Хоёрдмол байдлын үндсэн ба хоёр дахь теорем (төрийн теорем ба тайлбар)

Хоёрдмол байдлын анхны теорем.

Теорем: хэрэв давхар асуудлын аль нэг нь оновчтой төлөвлөгөөтэй бол нөгөө нь шийдэгдэх боломжтой, өөрөөр хэлбэл. сонголттой төлөвлөгөөтэй. Энэ тохиолдолд зорилгын функцүүдийн туйлын утгууд давхцаж байна (j=1-ээс n хүртэл) Σcjxj*= (i=1-ээс m хүртэл)Σbiyi* хэрэв эх хувилбарт байгаа бол. Бодлого төлөвлөгөөний багц дээр зорилгын функц хязгаарлагдахгүй бол хос бодлогод хязгаарлалтын систем нийцэхгүй байна.

Хоёрдахь хоёрдмол байдлын теорем ба түүний эдийн засгийн тайлбар.

руу хүчинтэй шийдлүүдхос бодлого оновчтой байсан тул нөхцөлийг биелүүлэхэд шаардлагатай бөгөөд хангалттай: xj*(∑aij yi*-cj)=0, j 1-ээс n хүртэл, yi*(∑aij xj*-bi)=0, I 1-ээс м хүртэл. Эдгээр нь нэмэлт сул дорой байдлын нөхцөл юм. Энэ нь тэднээс гарч байна: хэрэв давхар асуудлын аливаа хязгаарлалтыг оновчтой төлөвлөгөөний дагуу хатуу тэгш байдал болгон хувиргавал сонголтын харгалзах бүрэлдэхүүн хэсэг болно. давхар бодлогын төлөвлөгөө тэгтэй тэнцүү байх ёстой.Хэрэв зарим бүрэлдэхүүн хэсэг нь opt. төлөвлөгөө тэгтэй тэнцүү бол хос бодлогын харгалзах хязгаарлалтыг opt.plan-оор хатуу тэгш байдал xj*>0 болгон хувиргадаг тул (i= 1-ээс m хүртэл)Σaij yi*=cj opt.plan, тэгвэл хэрэв зардал>үнэ, үйлдвэрлэлийн хэмжээ=0 Σaij yi* >cj эндээс xj*=0

yi*>0 тиймээс (j=1-ээс n хүртэл) Σaij xj*=bi (нөөцийн уралдаан = нөөцийн нөөц).

(j=1-ээс n хүртэл) Σaij xj*

Теоремын утга нь дараах байдалтай байна.

Нэгж бүтээгдэхүүн үйлдвэрлэхэд шаардагдах нөөцийн хэрэглээний зардлын тооцооллыг бүтээгдэхүүний ii \u003d үнээр тооцсон бол энэ төрлийн бүтээгдэхүүний ii-ийг оновчтой төлөвлөгөөнд тусгасан болно;

Хэрэв зардал нь үнээс давсан бол бүтээгдэхүүн үйлдвэрлэх ёсгүй;

Хэрэв нөөцийн хэрэглээ = нөөц бол энэ нөөцийн зардлын тооцоо эерэг байна. Ийм нөөцийг хомс гэж нэрлэдэг. Хамгийн их дутагдалтай.res-s хамгийн өндөр оноотой;

Хэрэв нөөцийг бүрэн зарцуулаагүй бол түүний зардлын тооцоо = 0 байна.

61. Анхны бодлогын симплекс хүснэгтээс давхар бодлогын оновчтой дэмжлэгийн төлөвлөгөөг байгуулах

Хамгийн оновчтой үр дүнд хүргэсэн шугаман хувиргалтын урвуу матрицын баганаас авсан мэдээлэл. D-1 матрицын баганууд нь маш хэрэгтэй мэдээллийг өгдөг.

А3 багана: S2 нөөцийн "сүүдрийн" үнэ y01=0, багана хэвээр байна

дан бөгөөд эхний мөрөөс x3=9 гэж уншиж болно, өөрөөр хэлбэл. олсон оновчтой төлөвлөгөөг хэрэгжүүлэхэд 1-р нөөц хэт их байх ба энэ илүүдэл (дутуу ашиглалт) ердийн 9 нэгж болно.

А4 багана: S2 нөөцийн "сүүдрийн" үнэ y02=1-тэй тэнцүү, нөөц бүрэн ашиглагдах ба түүний боломжит өсөлт нь зорилгын функц (өөрөөр хэлбэл орлого) нэмэгдэхэд хүргэнэ. Тэгээд учир нь y02=1, дараа нь нөөцийн S2-ийн өсөлт 1 c.u. орлогын хувьд нэмэгдэл өгнө.Z = y02· .w2 = = 1.1 = 1 (мянган грн) (энд.w2 нь S2 нөөцийн өсөлт ба .Z нь орлогын харгалзах өсөлт). S2 нөөцийг ингэж нэмэгдүүлснээр хамгийн их орлого аль хэдийн Zmax=58 мянган грн болно. + 1 мянган грн = 59 мянган грн. Зураг дээр. 6.2-т энэ нөхцөл байдлыг харуулсан бөгөөд тайлбарыг доор өгөх болно. Мөн A4 баганаас S2 нөөцийг 1 c.u-ээр нэмэгдүүлснээр гарч байна. шинэ оновчтой цэгийн хувьд T1 барааны гарц ½ тонноор буурч (х1 үндсэн хувьсагч ба А4 баганын эгнээний огтлолцол дээр "-1/2" байна), T2 барааны гарц ½ тонноор нэмэгдэх болно. 3/2 тонн (Учир нь А4 баганад х2 үндсэн хувьсагчтай эгнээнд "3/2" байна. А4 баганын талаар юу хэлснийг график бүтэц ашиглан доор тайлбарлах болно (Зураг 6.2). А5 багана: " S3 нөөцийн сүүдэр" үнэ y03=2-тэй тэнцүү байна. Энэ нь нөөц S3 1 c.u-ээр нэмэгдсэн гэсэн үг юм. Z-д нэмэлт оруулах болно.Z = y03 · .v3 = 2.1 =2(мянган гривен) ба Zmax=58 мянган гривен болно. + 2 мянган грн = 60 мянган грн. Үүний зэрэгцээ, хүснэгтийн А5 баганаас дараах байдлаар. 3, T1-ийн гарц ½ тонноор нэмэгдэж, T2 ½ тонноор буурна. S1 түүхий эдийн нөөц (1-р мөрийг үзнэ үү) 3/2 c.u-ээр нэмэгдэнэ.

62. Динамик програмчлалын аргын санаа ба түүний геометрийн тайлбар. Беллманы оновчтой байдлын зарчим.

Динамик програмчлалын аргаар асуудлын оновчтой шийдлийг функциональ тэгшитгэлийн үндсэн дээр олно

Үүнийг тодорхойлохын тулд танд хэрэгтэй:

1. үйл явцын сүүлчийн төлөвийн функциональ тэгшитгэлийг бичнэ үү (энэ нь l \u003d n-1-тэй тохирч байна)

fn-1(Sl-1)=хамгийн оновчтой(Rn(Sn-1,Un)+f0(Sn))

2. Зарим тогтмол Sn-1-ийн утгуудын салангид багцаас Rn(Sn-1,Un)-ийг, харгалзах зөвшөөрөгдөх хэсгүүдээс Un-ыг ол (f0(Sn)=0 тул f1(Sn-1)= оновчтой(Rn( Sn-1,Un)

Үүний үр дүнд эхний алхамын дараа Un шийдэл ба f1(Sn-1) функцийн харгалзах утгыг мэддэг болно.

3. l-ийн утгыг нэгээр бууруулж, харгалзах функциональ тэгшитгэлийг бич. l=n-k (k= 2,n)-ийн хувьд иймэрхүү харагдаж байна

fk(Sn-k)= оновчтой(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. илэрхийлэлд үндэслэн нөхцөлт оновчтой шийдлийг олох (2)

5. l-ийн утга хэдтэй тэнцүү болохыг шалгана уу.l=0 бол нөхцөлт оновчтой шийдүүдийн тооцоо дуусч, үйл явцын эхний төлөвийн бодлогын оновчтой шийд олдоно. Хэрэв l нь 0-тэй тэнцүү биш бол 3-р алхам руу очно уу.

6. Тооцооллын төгсгөлөөс эхэнд шилжих үйл явцын дараагийн алхам бүрийн хувьд асуудлын оновчтой шийдлийг тооцоол.

Програмын динамизмын арга нь олон хувьсагчтай нэг бодлогыг цөөн тооны хувьсагчтай дараалсан шийдэгдсэн хэд хэдэн бодлогоор солих боломжийг олгодог. Шийдвэрийг алхам алхмаар гаргадаг. Олон үе шаттай үйл явцыг оновчтой болгох үндсэн зарчим, түүнчлэн тооцооллын аргын онцлог нь Беллманы оновчтой байдлын зарчим юм.

Оновчтой зан төлөв нь анхны төлөв, анхны шийдвэр нь ямар ч байсан дараагийн шийдвэрүүд нь анхны шийдвэрийн үр дүнд бий болсон төлөв байдлын хувьд оновчтой байх ёстой гэсэн шинж чанартай байдаг.

Математикийн хувьд үүнийг дараах хэлбэрийн илэрхийлэл болгон бичдэг.

fn-1(Sl)=хамгийн оновчтой(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Илэрхийлэл дэх хамгийн оновчтой гэдэг нь асуудлын нөхцөлөөс хамааран хамгийн их буюу хамгийн бага утгыг илэрхийлнэ.

63. АН-ын аргаар шийдвэрлэсэн асуудалд тавигдах шаардлага

Динамик програмчлал нь олон шатлалт бодлогын оновчтой шийдлийг олох математикийн арга юм. Олон үе шаттай үйл явц нь цаг хугацааны явцад хөгжиж, хэд хэдэн үе шат буюу үе шатуудад хуваагддаг үйл явц юм.

Динамик програмчлалын аргын нэг онцлог нь олон үе шаттай үйл явцтай холбоотой гаргасан шийдвэрийг нэг үйлдэл биш, харин харилцан уялдаатай шийдвэрийн бүхэл бүтэн цогц байдлаар авч үздэг. Энэ харилцан уялдаатай шийдвэрийн дарааллыг стратеги гэж нэрлэдэг.Онцтой төлөвлөлтийн зорилго нь урьдчилан сонгосон шалгуурын хувьд хамгийн сайн үр дүнг өгөх стратегийг сонгох явдал юм. Ийм стратегийг оновчтой гэж нэрлэдэг.

Аргын өөр нэг чухал шинж чанар бол өмнөх үе шатнаас дараагийн алхамд гаргасан оновчтой шийдвэрийн бие даасан байдал, i.e. хэрхэн оновчтой болгож буй үйл явц өнөөгийн байдалд хүрсэн талаар. Хамгийн оновчтой шийдлийг зөвхөн тухайн үеийн үйл явцыг тодорхойлдог хүчин зүйлсийг харгалзан сонгоно.

Динамик програмын арга нь цаашдын үр дагаврыг харгалзан алхам бүрт оновчтой шийдлийг сонгох ёстой гэдгээрээ онцлог юм. Энэ нь алхам бүрт үйл явцыг оновчтой болгохын зэрэгцээ дараагийн бүх алхмуудыг мартаж болохгүй гэсэн үг юм.

64. АН-ын аргаар шийдсэн асуудлын математик загварыг эдийн засгийн томьёолол, байгуулах (хөрөнгө оруулалтын хуваарилалтын асуудлын жишээн дээр). Беллманы дахилтын хамаарал.

Динамик програмчлалын аргыг голчлон оновчтой болгож буй үйл явц (эсвэл нөхцөл байдал) орон зай, цаг хугацаа эсвэл хоёуланд нь байрлуулсан асуудлуудад хэрэглэгддэг гэдгийг урьдчилан тайлбарлая.

Процесс (нөхцөл байдал) өөрөө маш төвөгтэй байх тул мэдэгдэж буй аргуудыг ашиглан оновчтой болгох арга байхгүй. Дараа нь динамик програмчлалын аргын дагуу COMPLEX процесс (ажиллага, нөхцөл байдал) нь хэд хэдэн үе шатанд (алхам) хуваагддаг (хуваагддаг). Энэ задаргаа нь олон тохиолдолд байгалийн шинжтэй байдаг боловч ерөнхий тохиолдолд үүнийг зохиомлоор нэвтрүүлдэг. . Жишээлбэл, шатрын аливаа тоглоомыг авч үзэхэд тоглогч бүрийн аль ч нүүдэл зүгээр л үйлчилдэг

бүхэл багцыг тус тусад нь (үе шат) болгон хуваах. Нэг пуужинг нөгөө пуужингийн эсрэг явуулах цэргийн ажиллагаанд бүхэл бүтэн тасралтгүй үйл явцыг үе шатуудад, жишээлбэл, ажиглалтын секунд тутамд зохиомлоор хуваах шаардлагатай болдог. Динамик програмчлалын арга нь бүхэл бүтэн нарийн төвөгтэй үйл явцыг оновчтой болгохыг үе шат бүрийн нөхцөлт оновчлолоор солих боломжийг олгодог.

(алхамууд) дараа нь бүх үйл явцыг оновчтой хянах синтез. Үүний зэрэгцээ, арга нь тусдаа алхам (үе шат) дахь нөхцөлт оновчлолыг юуны түрүүнд бүхэл бүтэн үйл ажиллагааны ашиг сонирхолд нийцүүлэн хийх боломжийг олгодог.

N-н үе шатанд хүрсэн үр нөлөөний оновчтой утгыг олох боломжтой бүх тооцоог fn(S0)-ын үндсэн функциональ Беллманы тэгшитгэл буюу давталтын хамаарал гэж нэрлэдэг (1) томъёоны дагуу гүйцэтгэнэ. fn-1 функцийн дараагийн утгыг тооцохдоо өмнөх алхам дээр олж авсан fn-(l+1) функцийн утгыг, Rl+1(Sl,Ul+1) эффектийн шууд утгыг ашиглана. Өгөгдсөн төлөвийн Sl системд Ul+1 уусмалыг сонгосны үр дүнд хүрсэн. fn-1(l=0,n-1) функцийн утгыг тооцоолох үйл явц.

Энэ нь f0(Sn)=0 байгалийн анхны нөхцөлд явагддаг бөгөөд энэ нь системийн эцсийн төлөвөөс гадуур үр нөлөө нь тэг байна гэсэн үг юм.

65. Хөрөнгө оруулалтын хуваарилалтын асуудал (жишээ).

Хөрөнгө оруулалтын оновчтой хуваарилалтын асуудлыг шийдэхийн тулд бид Беллманы функциональ тэгшитгэлийг ашиглана. Эхлээд бид хамгийн энгийн нөхцөл байдлыг ашиглан Беллманы функциональ тэгшитгэлийн гарал үүслийг тайлбарлаж, дараа нь жишээ ашиглан энэ тэгшитгэлийг бидний сонирхож буй асуудлыг шийдвэрлэхэд хэрхэн ашиглахыг нотлох болно.

Хоёр аж ахуйн нэгжийн хооронд К-ийн хэмжээгээр хуваарилагдсан хөрөнгийн хөрөнгө оруулалтын оновчтой хуваарилалтаас эхэлье. Аж ахуйн нэгжүүдийн төлөвлөлтийн хэлтсүүд өөрсдийн тооцоололд үндэслэн Р1 аж ахуйн нэгжийн орлогын q(x) функцийг, Р2 аж ахуйн нэгжийн хувьд h(x) функцийг бүрдүүлсэн. Эдгээр функцууд нь хэрэв эхний эсвэл хоёр дахь аж ахуйн нэгж х хэмжээний хөрөнгө оруулалт хүлээн авбал эхний аж ахуйн нэгж гэсэн үг юм

q(x) орлогыг хүлээн авах ба хоёр дахь h(x) ба x-ийн утга нь 0-ээс K хүртэлх тасралтгүй эсвэл мэдэгдэж буй дискрет утгыг авч болно.

Тиймээс, P1 компани хөрөнгийн хөрөнгө оруулалтыг х хэмжээгээр хуваарилсан бол P2 компанид K - x хэмжээг хуваарилна. Энэ тохиолдолд эхний аж ахуйн нэгжээс q(x) орлогыг, хоёрдугаарт h(K - x) авна. Хэрэв K хөрөнгө оруулалтыг нэг төлөвлөлтийн хугацаанд хуваарилсан бол хоёр аж ахуйн нэгжийн нийт орлого R(K, x) = q(x) + h(K - x) болно. Мэдээжийн хэрэг, x ба үүний дагуу K - x-ийг R(K, x) хамгийн их утгыг нь авахаар сонгох ёстой бөгөөд үүнийг бид F(K) гэж тэмдэглэнэ:

Энэ оруулга нь илүү бүрэн дүүрэн оруулгад зориулсан араг яс шиг юм.

функциональ Беллманы тэгшитгэл. Хөрөнгө оруулалтыг төлөвлөлтийн хоёр хугацаанд (хоёр үе шат) хуваарилах замаар бидний ажлыг хүндрүүлээрэй. . Эхний P1 аж ахуйн нэгжид х дүнг, хоёр дахь аж ахуйн нэгж Р1-д x-ийг хуваарилахаар шийдвэрлэе. Ерөнхийдөө орлого нь R(K, x) = q(x) +-тэй тэнцүү байх болно

h(K - x). Хэрэв бид хөрөнгө оруулалтыг 2 үе (2 үе шат) -аар хуваарилдаг гэдгийг санаж байвал эхний аж ахуйн нэгжид хөрөнгө оруулалтын үлдэгдэл нь x, энд , хоёрдугаарт - .(K - x) байх болно. хоёр дахь үе нь q( .x) - эхний байгууламжийн дагуу, h[.(K - x)] - хоёр дахь нь болно. Динамик програмчлалын оновчлол нь дүрмээр бол эцсийн шатнаас эхэлдэг. Тиймээс бид хоёр дахь шатнаас эхэлж, F1-ийг хоёр дахь аж ахуйн нэгжээс авах боломжтой хамгийн их орлогыг илэрхийлнэ

үе шат. Авах

Дараа нь авч үзсэн сүүлчийн (манай тохиолдолд, хоёр дахь) үе шатанд бид өмнөх (бидний тохиолдолд эхний) шатыг нэмж, хоёр үе шатнаас хамгийн их орлогыг олно.

Үүний нэгэн адил, n үе шатанд бид олж авна

Энд Fn-1 нь сүүлийн (n - 1) үе шатанд хамгийн сайн үр дүнг өгдөг зорилгын функц юм. Үүссэн функциональ Беллманы тэгшитгэл нь давтагдах, i.e. Fn утгыг Fn-1 утгатай холбодог.

Ерөнхийдөө Беллманы тэгшитгэл нь хэлбэртэй байна

Энд , Fn-1 - (n - 1) сүүлийн үе шатуудын хамгийн их орлого, Fn -

бүх n үе шатанд хамгийн их орлого.

66. Шугаман бус програмчлалын асуудлыг шийдвэрлэх тухай ойлголт

Шугаман бус програмчлалын асуудлыг дараах ерөнхий хэлбэрээр тавьж үзье: нөхцөлийг хангасан x1, x2, ..., xn хувьсагчдын утгыг ол.

мөн зорилгын функцийн шаардлагатай экстремумыг (хамгийн их эсвэл хамгийн бага) авчирна

f = f(x1, x2,…, xn), (13.2)

f(х1, …, хn) ба qi(х1, …, хn) (m , 1 i =) нь бодит шугаман бус,

n бодит хувьсагчийн тогтмол функцууд.

Тэдний ерөнхий шинж чанаруудын дагуу шугаман бус програмчлалын асуудлууд байж болно

шугаманхаас эрс ялгаатай. Жишээлбэл, хэрэгжих боломжтой шийдлүүдийн муж нь аль хэдийн гүдгэр биш байж болох ба зорилгын функцийн экстремум нь боломжит мужын аль ч цэг дээр ажиглагдаж болно. Шугаман бус асуудлыг шийдвэрлэх аргууд нь бас эрс ялгаатай. Эдгээр асуудлыг шийдвэрлэх зарим аргыг л авч үзье.

Юуны өмнө график арга нь шугаман бус програмчлалын хамгийн энгийн асуудлыг шийдвэрлэхэд бас хүчинтэй. Тиймээс, хэрэв x1 ба x2 хувьсагч нь асуудлын аргумент бол эхлээд эдгээр хувьсагчийн хавтгай дээр хэрэгжих боломжтой шийдлүүдийн талбайг барьж, дараа нь зорилтын функцийн түвшинг ашиглан тухайн талбайн оновчтой цэгийг тодорхойлно. f(x1,x2).

Шугаман бус програмчлалд градиент аргыг олон асуудлыг шийдвэрлэхэд ашигладаг. Хэд хэдэн градиент аргууд байдаг бөгөөд тэдгээрийн мөн чанар нь зорилгын функцийн градиентийг ашиглан оновчтой үр дүнг олох явдал юм - авч үзсэн цэгийн зорилгын хамгийн их өсөлтийн чиглэлийг харуулсан вектор. Ерөнхий тохиолдолд хайлтын процедурыг анх сонгосон цэгээс хамгийн сайн үзүүлэлттэй цэг хүртэл давталтын горимоор гүйцэтгэдэг. Жишээлбэл, . - зөвшөөрөгдөх шийдлүүдийн домэйн

асуудал гэж үзсэн бөгөөд давтагдах тооцооллын үйл явц нь тухайн цэгээс эхэлдэг

Цаашилбал, эхлээд зорилгын функцийн градиентийн дагуу шилжилт хийж, дараа нь талбай руу буцна. градиентийн дагуу O2 O3 бүсийн эвдэрсэн хил хүртэл. 13.3-т сондгой индекстэй Ai нь тухайн бүсэд хамаарах, тэгш индекстэй Ai цэгүүд хамаарахгүй болохыг харуулсан.Бид оновчтой Q цэгт ойртох тусам ажлын градиентуудын чиглэлүүд нийлдэг. Тиймээс үйл явцыг зогсоох хамгийн тохиромжтой шалгуур нь зорилтот градиент ба эвдэрсэн хилийн градиентийн уялдаа холбоо байх болно.

67. Параметр болон бүхэл тоон програмчлалын тухай ойлголт .

ZCLP-ийн мэдэгдэл ба математик загвар.

Хуваагдах боломжгүй объекттой холбоотой асуудалд хувьсагчдад бүхэл тооны нөхцөл ногдуулдаг. Заримдаа эдгээр нөхцөл нь бүх хувьсагчдад, заримдаа зарим хувьсагчид хамаарна.Бүрэн бүхэл тооны бодлогыг авч үзье.

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xi-бүхэл тоо,j=1,n

Одоо шугаман програмчлалын ерөнхий бодлогоос ялгаатай нь оновчтой төлөвлөгөө нь олон талт төлөвлөгөөний орой дээр байх албагүй.Бүхэл тоон бодлогыг шийдвэрлэх дараах аргууд байдаг.

1. Зүсэх аргууд

2.Комбинаторийн

3. Ойролцоо аргууд..

Параметрийн програмчлал нь зөвшөөрөгдөх нөхцөл, зорилгын функц нь зарим детерминистик параметрээс хамаардаг оновчлолын асуудлыг судлахад зориулагдсан математик програмчлалын салбар юм.

Тодорхойлолт. Шугаман програмчлал (LP) -Судалгааны аргууд ба шугаман хязгаарлалт тогтоогдсон үл мэдэгдэх шугаман функцийн туйлын (хамгийн их ба хамгийн бага) утгыг олох шинжлэх ухаан.

Энэ шугаман функц гэж нэрлэгддэг зорилтот,математикийн хувьд тэгшитгэл эсвэл тэгш бус байдал хэлбэрээр бичигдсэн хязгаарлалтуудыг нэрлэдэг хязгаарлалтын систем.

Тодорхойлолт.Зорилгын функц ба түүний хязгаарлалтын математик илэрхийлэл гэж нэрлэдэг эдийн засгийн асуудлын математик загвар.

Ерөнхийдөө шугаман програмчлалын (LP) бодлогын математик загварыг дараах байдлаар бичдэг

хязгаарлалттай:

хаана x j- үл мэдэгдэх; айж, б би, cjтогтмолууд өгөгдсөн.

Хязгаарлалтын системийн бүх буюу зарим тэгшитгэлийг тэгш бус байдлаар бичиж болно.

Богино тэмдэглэгээний математик загвар нь хэлбэртэй байна

хязгаарлалттай:

Тодорхойлолт.Шугаман програмчлалын асуудлын боломжит шийдэл (төлөвлөгөө) нь вектор = ( х 1 , х 2 ,..., x p),хязгаарлалтын тогтолцоог хангах.

Зөвшөөрөгдөх шийдлүүдийн багц нь зөвшөөрөгдөх уусмалын бүсийг (ODD) бүрдүүлдэг.

Тодорхойлолт.Зорилгын функц нь туйлын утгад хүрэх боломжтой шийдлийг шугаман програмчлалын асуудлын оновчтой шийдэл гэж нэрлээд opt гэж тэмдэглэнэ.

Зөвшөөрөгдөх үндсэн шийдэл (X 1 , X 2 ,...,x r , 0, …, 0) нь лавлагаа шийдэл бөгөөд энд r-хязгаарлалтын системийн зэрэг.

LP бодлогын математик загвар нь каноник ба каноник бус байж болно.

7. Шугаман програмчлалын бодлогыг график аргаар шийдвэрлэх. Хязгаарлалтын функцүүдийн графикууд. Түвшингийн шугамууд.

Шугаман програмчлалын асуудлыг шийдвэрлэх график арга

Шугаман програмчлалын хамгийн энгийн бөгөөд харааны арга бол график арга юм. Энэ нь канон бус хэлбэрээр өгөгдсөн хоёр хувьсагчтай, хоёроос илүүгүй чөлөөт хувьсагч агуулаагүй тохиолдолд каноник хэлбэрээр олон хувьсагчтай LP асуудлыг шийдвэрлэхэд хэрэглэгддэг.

Геометрийн үүднээс авч үзвэл шугаман програмчлалын асуудалд ийм булангийн цэг эсвэл зөвшөөрөгдөх шийдлүүдийн багц цэгийг хайж, хамгийн өндөр (доод) түвшний шугамд хүрч, түүнээс хол (ойр) байрладаг. бусад нь хамгийн хурдан өсөлтийн чиглэлд.

LP асуудлуудын график шийдэлд зорилгын функцын хэт утгыг олохын тулд векторыг ашигладаг Л() гадаргуу дээр X 1 Өө 2 , үүнийг бид тэмдэглэж байна . Энэ вектор нь зорилгын функцийн хамгийн хурдан өөрчлөлтийн чиглэлийг харуулж байна. Өөрөөр хэлбэл вектор нь түвшний шугамын хэвийн хэмжээ юм Л()

хаана д 1 ба д 2 - тэнхлэгийн дагуух нэгж векторууд ҮХЭР 1 ба ҮХЭР 2 тус тус; ингэснээр = (∂L/∂x 1 , ∂L/∂х 2 ). Вектор координатууд нь зорилгын функцийн коэффициентүүд юм L().Практик асуудлыг шийдвэрлэхдээ түвшний шугамын барилгын ажлыг нарийвчлан авч үзэх болно.

Асуудлыг шийдвэрлэх алгоритм

1. Бид асуудлын хязгаарлалтын системийн боломжит шийдлүүдийн талбарыг олдог.

2. Вектор бүтээх .

3. Түвшингийн шугам зур Л 0 , перпендикуляр байна .

4. Бид түвшний шугамыг даалгаврын векторын чиглэлд дээд тал руу, эсрэг чиглэлд шилжүүлдэг , хамгийн бага даалгаврын хувьд.

Түвшингийн шугамыг боломжит шийдлүүдийн талбартай нэг нийтлэг цэгтэй болтол шилжүүлнэ. LP асуудлын өвөрмөц шийдлийг тодорхойлдог энэ цэг нь экстремум цэг болно.

Хэрэв түвшний шугам нь ODT-ийн аль нэг талтай параллель байгаа бол энэ тохиолдолд харгалзах талын бүх цэгүүдэд экстремумд хүрч, LP асуудал нь хязгааргүй олон шийдэлтэй байх болно. Ийм л LP асуудал гардаг гэж байгаа альтернатив оновчтойба түүний шийдлийг дараах томъёогоор тодорхойлно.

0 ≤ хаана байна т≤ 1, 1 ба 2 - ODS-ийн булангийн цэгүүдэд оновчтой шийдлүүд.

LP асуудал нь түүнийг тодорхойлсон хязгаарлалтууд нь зөрчилдөөнтэй байвал шийдвэрлэх боломжгүй байж болно.

5. Бид экстремум цэгийн координат ба түүний доторх зорилгын функцийн утгыг олдог.

Жишээ 3Бүтээгдэхүүний хамгийн сайн хувилбарыг сонгох

Тус компани нь цөцгий, шоколад гэсэн 2 төрлийн зайрмаг үйлдвэрлэдэг. Зайрмаг үйлдвэрлэхэд эхний хоёр бүтээгдэхүүнийг ашигладаг: сүү, дүүргэгч, 1 кг зайрмагны өртөг, өдөр тутмын хангамжийг хүснэгтэд үзүүлэв.

Зах зээлийн судалгаагаар цөцгийн зайрмагны өдөр тутмын хэрэгцээ нь шоколадтай зайрмагны эрэлтээс давсан боловч 100 кг-аас ихгүй байна.

Үүнээс гадна шоколадтай зайрмагны хэрэгцээ өдөрт 350 кг-аас хэтрээгүй нь тогтоогджээ. 1 кг өтгөн зайрмагны жижиглэнгийн үнэ 16 рубль, шоколад 14 рубль байна.

Борлуулалтын орлогоо нэмэгдүүлэхийн тулд пүүс зайрмагны төрөл тус бүрээс хэдийг үйлдвэрлэх ёстой вэ?

Шийдэл.Тэмдэглэх: х 1 - өтгөн зайрмаг үйлдвэрлэх өдөр тутмын хэмжээ, кг; х 2 - шоколадтай зайрмагны өдөр тутмын гарц, кг.

Бодлогын математик загварыг хийцгээе.

Зайрмагны үнэ мэдэгдэж байна: 16 рубль ба 14 рубль тус тусад нь зорилтот функц нь дараах байдалтай байна.

Зайрмагны сүүнд хязгаарлалт тавь. Цөцгийтэй зайрмагны хэрэглээ 0.8 кг, шоколадтай зайрмагны хувьд 0.5 кг байна. Сүүний нөөц 400 кг. Тиймээс эхний тэгш бус байдал дараах байдалтай байна.

0.8x 1 + 0.5x 2 ≤400 - эхний тэгш бус байдал нь хязгаарлалт юм. Үлдсэн тэгш бус байдлыг ижил төстэй байдлаар байгуулна.

Үүний үр дүнд тэгш бус байдлын систем бий болно. тэгш бус байдал бүрийн шийдлийн талбар гэж юу вэ. Тэгш бус байдал бүрд O(0:0) цэгийн координатыг орлуулах замаар үүнийг хийж болно. Үүний үр дүнд бид дараахь зүйлийг авна.

Зураг OABDEF-зөвшөөрөгдөх шийдлүүдийн домэйн. Бид векторыг бүтээдэг (16; 14). түвшний шугам Л 0 нь 16x 1 +14x 2 =Const тэгшитгэлээр өгөгдөнө. Бид дурын тоог сонгоно, жишээ нь 0, дараа нь 16x 1 +14x 2 =0. Зураг дээр L 0 шугамын хувьд тэгтэй тэнцүү биш эерэг тоог сонгосон. Бүх түвшний шугамууд хоорондоо параллель байна. Түвшингийн шугамын хэвийн вектор.

Түвшингийн шугамыг векторын чиглэлд шилжүүлнэ. гарах цэг ЛБоломжит шийдлүүдийн бүсээс 0 нь цэг юм Д, түүний координатыг тэгшитгэлээр өгөгдсөн шугамуудын огтлолцол гэж тодорхойлно.

Системийг шийдэж, бид цэгийн координатыг олж авдаг Д(312.5; 300), үүнд оновчтой шийдэл байх болно, өөрөөр хэлбэл.

Тиймээс тус компани өдөрт 312.5 кг цөцгийн тос, 300 кг шоколадтай зайрмаг үйлдвэрлэх ёстой бөгөөд борлуулалтаас олсон орлого нь 9200 рубль болно.

8. Дурын шугаман програмчлалын бодлогыг үндсэн бодлого болгон бууруулах.Тэгш бусаар өгөгдсөн хязгаарлалтыг харгалзах тэгшитгэлд хөрвүүлэх.

9. Энгийн арга. Аргын шинж чанар, алгоритм, түүний хэрэглээ.

Асуудлыг симплекс аргаар шийдэхийн тулд зайлшгүй шаардлагатай:

1. Ээлжит оновчтой шийдлийг олох аргыг заана уу

2. Зорилгын функцын утга нь оновчтойд ойртох нэг лавлах шийдлээс нөгөөд шилжих аргыг зааж өгнө үү, i.e. лавлагаа шийдлийг сайжруулах арга замыг зааж өгнө

3. Оновчтой шийдлийн талаархи лавлагаа шийдлүүдийн тооллогыг цаг тухайд нь зогсоох эсвэл оновчтой шийдэл байхгүй гэсэн дүгнэлтийг гаргах боломжийг олгох шалгууруудыг тавь.

Шугаман програмчлалын асуудлыг шийдвэрлэх симплекс аргын алгоритм

1. Асуудлыг каноник хэлбэрт оруул

2. "Нэгж суурь"-тай анхны дэмжлэгийн шийдлийг ол (хэрэв дэмжлэгийн шийдэл байхгүй бол хязгаарлалтын систем үл нийцэх тул асуудал шийдэлгүй болно)

3. Векторын тэлэлтийн тооцоог жишиг шийдлийн суурийн хувьд тооцоолж, симплекс аргын хүснэгтийг бөглөнө үү.

4. Хэрэв оновчтой шийдлийн өвөрмөц байдлын шалгуур хангагдсан бол асуудлын шийдэл дуусна.

5. Хэрэв оновчтой шийдлийн багц байх нөхцөл хангагдсан бол энгийн тооллогоор бүх оновчтой шийдлүүд олдоно.

10. Тээврийн даалгавар.Тээврийн асуудлын анхны шийдлийг олох тодорхойлолт, төрөл, арга.

Тээврийн асуудал бол шугаман програмчлалын хамгийн түгээмэл асуудлуудын нэг юм. Үүний зорилго нь ачаа тээвэрлэх хамгийн оновчтой арга, хэрэгслийг хөгжүүлэх, хэт хол зайд, ойртож буй, давтан тээврийг арилгах явдал юм.

1. Анхны лавлагааны шийдлийг олох;

2. Энэ шийдлийг оновчтой эсэхийг шалгах;

3. Нэг үндсэн шийдлээс нөгөөд шилжих.

T10. Шугаман програмчлалын бодлогын мэдэгдэл

математик загварЭдийн засгийн бодлого гэдэг нь эдийн засгийн үйл явцыг дүрсэлсэн математик харилцааны багц юм.

Математик загварыг эмхэтгэхийн тулд дараахь зүйлийг хийх шаардлагатай.

1. даалгаврын хувьсагчдыг сонгох;

2. хязгаарлалтын тогтолцоог боловсруулах;

3. зорилгын функцийг тогтоох.

Даалгаврын хувьсагчидЭдийн засгийн үйл явцыг бүрэн тодорхойлдог x 1 , x 2 ,…, x n хэмжигдэхүүнүүдийг нэрлэнэ. Тэдгээрийг ихэвчлэн X \u003d (x 1, x 2, ..., x n) вектор хэлбэрээр бичдэг.

Даалгаврын хязгаарлалтын системгэдэг нь тухайн асуудлын хувьсагчид хангагдах, хязгаарлагдмал нөөц болон эдийн засгийн бусад нөхцлөөс, тухайлбал, хувьсагчдын эерэг байдлаас үүдэлтэй тэгшитгэл ба тэгш бус байдлын багц юм. Ерөнхийдөө тэд дараах байдлаар харагдаж байна.

Зорилгын функц гэж нэрлэдэгФ(X) = f(x 1 , x 2 ,…, x n) функц нь даалгаврын чанар болон экстремумыг олоход шаардагдах үзүүлэлтийг тодорхойлдог.

Математик програмчлалын ерөнхий асуудалдараах байдлаар томьёологдсон: зорилгын функцийн экстремумыг өгөх x 1 , x 2 ,…, x n даалгаврын хувьсагчдыг ол.

F (X) \u003d f (x 1, x 2, ..., x n) ® max (мин) (2)

ба хязгаарлалтын системийг (1) хангана.

Хэрэв зорилгын функц (2) ба хязгаарлалтын систем (1) нь шугаман байвал математик програмчлалын бодлогыг гэнэ. шугаман програмчлалын асуудал (LPP).

X векторыг (даалгаврын хувьсагчийн багц) гэж нэрлэдэг хүлээн зөвшөөрөгдсөн шийдэл, эсвэл PLP төлөвлөгөө, хэрэв энэ нь хязгаарлалтын системийг (1) хангаж байвал. Зорилгын функцийн экстремумыг хангасан хэрэгжих боломжтой X төлөвлөгөөг нэрлэнэ оновчтой шийдэл ZLP.

2. Эдийн засгийн асуудлын математик загварыг эмхэтгэх жишээ

Үйлдвэрлэлийн тодорхой нөхцөл байдлыг судлах нь хязгаарлагдмал нөөцийг оновчтой ашиглах асуудал гэж тайлбарлагддаг ZLP-д хүргэдэг.

1.Үйлдвэрлэлийн оновчтой төлөвлөгөөний асуудал

T 1 ба T 2 хоёр төрлийн бүтээгдэхүүн үйлдвэрлэхэд S 1, S 2, S 3 гурван төрлийн нөөцийг ашигладаг. Нөөцийн нөөц, нэгж бүтээгдэхүүн үйлдвэрлэхэд зарцуулсан нөөцийн тоо, түүнчлэн бүтээгдэхүүний борлуулалтаас олсон ашгийг хүснэгтэд үзүүлэв.

Борлуулалтаас олох ашиг нь хамгийн их байх бүтээгдэхүүн үйлдвэрлэх ийм төлөвлөгөөг олох шаардлагатай байна.

Шийдэл.

x 1, x 2 - үйлдвэрлэхээр төлөвлөж буй үйлдвэрлэлийн нэгжийн тоо, T 1 ба T 2 -ийг тус тус тэмдэглэе. Тэдгээрийг үйлдвэрлэхэд (x 1 + x 2) нөөцийн нэгж S 1, (x 1 + 4x 2) нөөцийн нэгж S 2, (x 1) нөөцийн нэгж S 3 шаардлагатай болно. S 1, S 2, S 3 нөөцийн хэрэглээ нь тэдгээрийн нөөцөөс 8, 20, 5 нэгжээс хэтрэхгүй байх ёстой.

Дараа нь асуудлын эдийн засаг-математик загварыг дараах байдлаар томъёолж болно.

Хязгаарлалтын системийг хангасан X \u003d (x 1, x 2) үйлдвэрлэлийн төлөвлөгөөг ол.

болон нөхцөл байдал

ямар функц дор байна хамгийн их утгыг авдаг.

m төрлийн нөөцийг ашиглан n төрлийн бүтээгдэхүүн үйлдвэрлэх тохиолдолд асуудлыг хялбархан ерөнхийлж болно.

2.Хамгийн оновчтой хоолны дэглэмийн асуудал

S 1, S 2, S 3 шим тэжээл агуулсан K 1 ба K 2 төрлийн хоол хүнс байдаг. Тэжээлийн төрөл бүрийн 1 кг-д агуулагдах шим тэжээлийн нэгжийн тоо, шаардлагатай хамгийн бага шим тэжээл, түүнчлэн 1 кг тэжээлийн өртөг зэргийг хүснэгтэд үзүүлэв.

Шим тэжээлийн төрөл бүрийн агууламж тогтоосон хэмжээнээс багагүй байх хамгийн бага зардалтай өдөр тутмын хоолны дэглэмийг гаргах шаардлагатай.

Шийдэл.

x 1, x 2 - өдөр тутмын хоолны дэглэмд орсон K 1 ба K 2 тэжээлийн хэмжээг тэмдэглэе. Дараа нь энэ хоолны дэглэмд (3х 1 + х 2) шим тэжээлийн нэгж S 1, (х 1 + 2х 2) нэгж S 2, (х 1 + 6х 2) шим тэжээлийн нэгж S 3 орно. Хоол тэжээл дэх S 1, S 2, S 3 тэжээллэг бодисын агууламж 9, 8, 12 нэгж байх ёстой тул асуудлын эдийн засаг-математик загварыг дараах байдлаар томъёолж болно.

Хязгаарлалтын системийг хангасан өдөр тутмын хоолны дэглэм X \u003d (x 1, x 2) зохиох:

болон нөхцөл байдал

ямар функц дор байна хамгийн бага утгыг авна.

PLP бичлэгийн маягтууд

LLP-д шугаман зорилгын функцийн экстремумыг олох шаардлагатай.

хязгаарлалттай:

болон сөрөг бус байдал

Энд a ij , b i , c j ( , ) тогтмолууд өгөгдсөн.

ZLP нь ингэж бичигдсэн байдаг ерөнхийхэлбэр. Хэрэв хязгаарлалтын систем нь зөвхөн тэгш бус байдлыг агуулж байвал LLP-г төлөөлнө Стандартхэлбэр. Каноник (үндсэн) ZLP тэмдэглэгээний хэлбэр нь хязгаарлалтын систем нь зөвхөн тэгш байдлыг агуулсан тохиолдолд тэмдэглэгээ юм. Тиймээс дээрх ХХК-ийг стандарт хэлбэрээр бичсэн болно.

LLP-ийн ерөнхий, стандарт, каноник хэлбэрүүд нь тэдгээр нь тус бүрийг энгийн хувиргалтуудын тусламжтайгаар өөр хэлбэрээр дахин бичих боломжтой гэсэн утгаараа тэнцүү юм. Хэрэв эдгээр асуудлын аль нэгийг шийдэх арга зам байгаа бол аль нэг асуудлын оновчтой төлөвлөгөөг тодорхойлж болно гэсэн үг юм.

LLP тэмдэглэгээний нэг хэлбэрээс нөгөө хэлбэрт шилжихийн тулд тэгш бус байдлын хязгаарлалтаас тэгш байдлын хязгаарлалт руу шилжих чадвартай байх ёстой.

Тэгш бус байдлын хязгаарлалтыг (£) зүүн талд нь сөрөг бус нэмэлт хувьсагчийг нэмснээр тэгш байдлын хязгаарлалт болгон хувиргаж, тэгш бус байдлын хязгаарлалтыг (³) үүнээс сөрөг бус нэмэлт хувьсагчийг хасах замаар тэгш байдлын хязгаарлалт болгон хувиргаж болно. зүүн тал. Нэмэлт оруулсан сөрөг бус хувьсагчийн тоо нь хувиргасан тэгш бус байдлын хязгаарлалтын тоотой тэнцүү байна.

Танилцуулсан нэмэлт хувьсагч нь эдийн засгийн зарим нэг утга учиртай. Тиймээс хэрэв анхны PLP-ийн хязгаарлалт нь нөөцийн хэрэглээ, хүртээмжийг тусгасан бол каноник хэлбэрээр PLP нэмэлт хувьсагчийн утга нь ашиглагдаагүй харгалзах нөөцийн эзлэхүүнтэй тэнцүү байна.

Жишээ 1. ZLP каноник хэлбэрээр бичнэ үү:

хязгаарлалттай:

Шийдэл.

Зорилгын функц өөрчлөгдөөгүй хэвээр байна:

Тэгш бус байдлын тогтолцоог тэгш байдлын систем болгон хувиргадаг.

LLP-ийг график аргаар шийдвэрлэхдээ каноник хэлбэрээс стандарт хэлбэрт шилжих шаардлагатай.

LLP-ийг стандарт хэлбэрт оруулахын тулд ашиглана уу Жордан-Гаусын арга SLAU шийдэл. Системийн өргөтгөсөн матрицыг шаталсан хэлбэр болгон бууруулдаг Гауссын аргаас ялгаатай нь Жордан-Гауссын аргын хувьд өргөтгөсөн матрицын нэг хэсэг болгон таних матриц үүсдэг. Тиймээс энд урвуу хөдөлгөөн хийх шаардлагагүй.

Анхны каноник ХХК-ийг ижил стандарт LLP болгон хөрвүүлэхийн тулд:

a) хязгаарлалтын системийн өргөтгөсөн матрицад тэгээс ялгаатай a qp элементийг сонгосон. Энэ элементийг нэрлэдэг зөвшөөрөлтэй, ба q - i мөр ба p-р багана идэвхжүүлэх мөр ба идэвхжүүлэх багана гэж нэрлэдэг.

б) шийдвэрлэх мөрийг өөрчлөхгүйгээр дахин бичиж, шийдвэрлэх баганаас бусад шийдвэрлэх баганын бүх элементүүдийг тэгээр солино. Өргөтгөсөн матрицын үлдсэн элементүүдийг "тэгш өнцөгтийн дүрэм" ашиглан тодорхойлно.

Өргөтгөсөн матрицын дөрвөн элементийг авч үзье: хувиргах a ij элемент, шийдвэрлэх элемент a qp, a i p ба qj элементүүд. a ij элементийг олохын тулд a ij элементээс тэгш өнцөгтийн эсрэг талын оройд байрлах a i p ба qj элементүүдийн үржвэрийг a qp шийдвэрлэх элементээр хуваана.

в) зөвшөөрөгдсөн үл мэдэгдэх зүйлсийг нэгэн зэрэг зорилгын функцээс хасна. Үүнийг хийхийн тулд зорилгын функцийн коэффициентүүдийг сүүлчийн эгнээний өргөтгөсөн матрицад бичнэ. Тооцоолол нь сүүлийн мөрөнд байгаа идэвхжүүлэх элементийг сонгох боломжгүй гэдгийг харгалзан үздэг.

Жишээ 2. Стандарт хэлбэрт шилжүүлэх:

Шийдэл.

Жордан-Гаусын аргыг ашиглан бид LLP хязгаарлалтын тэгшитгэлийн системийг тэгш бус байдлын эквивалент системд авчирдаг. Эхний эгнээний гурав дахь элементийг шийдвэрлэх элемент болгон сонгоцгооё.

Сүүлийн эгнээний сүүлчийн баганад авсан -9 тоог зорилтын функцэд эсрэг тэмдгээр бичих ёстой. Өөрчлөлтийн үр дүнд ХХК нь дараахь хэлбэрийг авдаг.

Учир нь x 2 ба x 3 хувьсагч нь сөрөг биш тул тэдгээрийг хаявал ZLP-ийг тэгш хэмтэй хэлбэрээр бичиж болно.

LLP-ийн каноник хэлбэрийн хувьд зорилгын функцийг аль аль нь багасгаж, ихэсгэж болно. Хамгийн ихийг олохоос доод хэмжээг олох эсвэл эсрэгээр нь явах, зорилгын функцийн коэффициентүүдийн тэмдгүүдийг өөрчлөхөд хангалттай: F 1 = - F. Үүссэн асуудал болон анхны LLP нь ижил оновчтой шийдэлтэй бөгөөд энэ шийдэл дээрх зорилгын функцүүдийн утгууд нь зөвхөн ялгаатай байна. тэмдэг.

ZLP шинж чанарууд

1. Шугаман програмчлалын бодлогын хязгаарлалтын системийн бүх зөвшөөрөгдөх шийдлүүдийн багц нь гүдгэр байна.

Цэгүүдийн багцыг нэрлэдэг гүдгэр, хэрэв энэ багцын дурын хоёр цэгийг холбосон сегментийг бүхэлд нь агуулж байвал.

Энэ тодорхойлолтын дагуу 1а-р зураг дээрх олон өнцөгт нь гүдгэр олонлог, харин 1б-р зураг дээрх олон өнцөгт нь тийм биш, учир нь. M ба N хоёр цэгийн хоорондох MN сегмент нь энэ олон өнцөгт бүрэн хамаарахгүй.

Гүдгэр олонлог нь зөвхөн олон өнцөгт биш байж болно. Гүдгэр олонлогийн жишээ нь тойрог, сектор, сегмент, шоо, пирамид гэх мэт.

2. Хэрэв LLP оновчтой шийдэлтэй бол шугаман функц нь шийдвэрийн олон талт булангийн аль нэг цэг дээр хамгийн их (хамгийн бага) утгыг авна. Хэрэв шугаман функц нь нэгээс олон булангийн цэг дээр хамгийн их (хамгийн бага) утгыг авдаг бол эдгээр цэгүүдийн гүдгэр шугаман хослол болох дурын цэг дээр үүнийг авна.

X цэг гэж нэрлэдэг гүдгэр шугаман хослолДараах нөхцөл хангагдсан тохиолдолд X 1 , X 2 ,…, X n оноо:

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,

αj ≥ 0, Σαj = 1.

n = 2-ын хувьд онцгой тохиолдолд хоёр цэгийн гүдгэр шугаман хослол нь тэдгээрийг холбосон сегмент байх нь ойлгомжтой.

3. Каноник LLP хязгаарлалтын системийн зөвшөөрөгдөх суурь шийдэл бүр нь уусмалын олон өнцөгтийн булангийн цэгтэй тохирч, харин эсрэгээр уусмалын олон өнцөгтийн булангийн цэг бүрт зөвшөөрөгдөх үндсэн уусмал тохирно.

Сүүлийн хоёр шинж чанараас харахад хэрэв ХХК нь оновчтой шийдэлтэй бол түүний зөвшөөрөгдөх үндсэн шийдлүүдийн дор хаяж нэгтэй давхцдаг.

Тиймээс LLP шугаман функцийн экстремумыг түүний зөвшөөрөгдөх үндсэн шийдлүүдийн хязгаарлагдмал тооны дундаас хайх ёстой.

Лекц 2

AT каноник хэлбэр

PLP-ийн зөвшөөрөгдөх шийдэл(хүлээн зөвшөөрөгдөх төлөвлөгөө).

ХХК-ийн оновчтой шийдэл.

Хэрэгтэй

Жишээ.

Асуудлаа бичье каноник хэлбэр

ZLP-ийн график шийдлийн онцгой нөхцөл байдал

Даалгавар хийхээс бусад тохиолдолд цорын ганц оновчтой шийдэлтөлөө болон, байж болно онцгой нөхцөл байдал:

1. даалгавар байна хязгааргүй тооны оновчтой шийдлүүд – сегмент дээр функцийн экстремумд хүрсэн ( альтернатив оновчтой)- Зураг 2;

2. даалгавар шийдвэрлэх боломжгүй ODR-ийн хязгааргүй байдлаас шалтгаалан, эсвэл - Зураг 3;

3. ODR - ганц цэг Аа, тэгвэл;

4. даалгавар шийдвэрлэх боломжгүй хэрэв ODR хоосон талбайтай бол.

ГЭХДЭЭ

Зураг 2 Зураг 3

Хэрэв түвшний шугам нь боломжит шийдлийн талбайн хажуу талтай зэрэгцээ байвал хажуугийн бүх цэгүүдэд экстремумд хүрнэ. Асуудал нь хязгааргүй олон оновчтой шийдлүүдтэй - альтернатив оновчтой . Хамгийн оновчтой шийдлийг томъёогоор олно

параметр хаана байна. 0-ээс 1 хүртэлх ямар ч утгын хувьд та сегментийн бүх цэгүүдийг авч болно, тус бүр нь функц нь ижил утгыг авдаг. Тиймээс нэр нь - альтернатив оновчтой.

Жишээ. Шугаман програмчлалын асуудлыг графикаар шийдвэрлэх ( альтернатив оновчтой):

Өөрийгөө хянах асуултууд

1. Шугаман програмчлалын бодлогыг ерөнхий хэлбэрээр бичнэ үү.

2. Шугаман програмчлалын бодлогыг каноник болон стандарт хэлбэрээр бичнэ үү.

3. Шугаман програмчлалын бодлогын ерөнхий болон стандарт хэлбэрээс каноник хэлбэрт шилжихийн тулд ямар хувиргалтыг ашиглаж болох вэ?

4. Шугаман програмчлалын асуудлыг шийдвэрлэх боломжтой, оновчтой шийдлүүдийн тодорхойлолтыг өгнө үү.

5. Хэрэв функцийг багасгах асуудлын аль нь "хамгийн сайн" вэ? ?

6. Хэрэв функцийг хамгийн их байлгах асуудлын аль нь "хамгийн сайн" вэ? ?

7. Хоёр хувьсагчтай шугаман програмчлалын бодлогын математик загварын стандарт хэлбэрийг бич.

8. Хоёр хувьсагчтай шугаман тэгш бус байдлаар өгөгдсөн хагас хавтгайг хэрхэн байгуулах вэ ?

9. Хоёр хувьсагчтай шугаман тэгш бус байдлын системийн шийдийг юу гэж нэрлэдэг вэ? Дараахь шугаман тэгш бус байдлын системийн боломжит шийдлүүдийн мужийг хавтгай дээр байгуул.

1) өвөрмөц шийдэлтэй;

2) хязгааргүй олон шийдэлтэй;

3) шийдэл байхгүй.

10. Шугаман функцийг бич вектор градиент, түвшний шугамын төрлийг нэрлэнэ үү. Градиент ба түвшний шугамууд бие биенээсээ хэрхэн байрладаг вэ?

11. Хоёр хувьсагчтай стандарт LLP-г шийдвэрлэх график аргын алгоритмыг томьёоло.

12. Шийдлийн координат ба утгыг хэрхэн олох вэ?

13. Шугаман програмчлалын асуудлуудын хувьд боломжит шийдлүүд, градиент ба түвшний шугамын талбарыг байгуул, үүнд:

1) нэг цэг дээр хүрч, - ODR сегмент дээр;

2) ODS-ийн нэг цэгт хүрсэн бөгөөд .

14. Хэрэв дараах тохиолдолд ХХК-ийн геометрийн дүрслэлийг өг.

1) ба -д зориулсан өвөрмөц оновчтой шийдэлтэй;

2) -д зориулсан оновчтой шийдлүүдийн багцтай.

Лекц 2

оновчтой шийдлийг олох график арга

1. Шугаман математик загварын хэлбэрүүд, тэдгээрийн хувиргалт

2. Шугаман програмчлалын асуудлыг шийдвэрлэх график арга

3. ХХК-ийн ГРАФИК ШИЙДВЭРИЙН ОНЦГОЙ Нөхцөл байдал

4. Шугаман програмчлалын эдийн засгийн асуудлын график шийдэл

Шугаман математик загварын хэлбэрүүд ба тэдгээрийн хувиргалт

Шугаман програмчлалын бодлогын (LPP) математик загварыг гурван хэлбэрийн аль нэгээр бичиж болно.

AT Математик загварын ерөнхий хэлбэрзорилгын функцийн хамгийн их буюу хамгийн бага утгыг олох шаардлагатай; хязгаарлалтын систем нь тэгш бус байдал ба тэгшитгэлийг агуулдаг; бүх хувьсагч сөрөг биш байж болохгүй.

AT каноник хэлбэрматематик загвар нь зорилгын функцийн дээд хэмжээг олох шаардлагатай; хязгаарлалтын систем нь зөвхөн тэгшитгэлээс бүрдэнэ; бүх хувьсагч сөрөг биш байна.

Математик загварын стандарт хэлбэрээр функцийн хамгийн их эсвэл хамгийн бага утгыг олох шаардлагатай; бүх хязгаарлалтууд нь тэгш бус байдал; бүх хувьсагч сөрөг биш байна.

Хувьсагчдын сөрөг бус байх нөхцлийг хангасан хязгаарлалтын системийн шийдийг гэнэ. PLP-ийн зөвшөөрөгдөх шийдэл(хүлээн зөвшөөрөгдөх төлөвлөгөө).

Боломжит шийдлүүдийн багц гэж нэрлэдэг ХХК-ийн боломжит шийдлүүдийн талбар.

Зорилгын функц нь туйлын утгад хүрэх боломжтой шийдлийг гэж нэрлэдэг ХХК-ийн оновчтой шийдэл.

LLP-ийн гурван хэлбэр нь математикийн хувиргалтын тусламжтайгаар тус бүрийг өөр хэлбэрт оруулах боломжтой гэсэн утгаараа тэнцүү юм.

Хэрэгтэй Математик загварын нэг хэлбэрээс нөгөө хэлбэрт шилжихасуудлыг шийдвэрлэх аргуудтай холбоотой: жишээлбэл, шугаман програмчлалд өргөн хэрэглэгддэг симплекс аргыг каноник хэлбэрээр бичсэн бодлогод, график аргыг математик загварын стандарт хэлбэрт ашигладаг.

ZLP каноник тэмдэглэгээ рүү шилжих.

Жишээ.

Асуудлаа бичье каноник хэлбэр, хязгаарлалтын системийн эхний тэгш бус байдлын зүүн талд "+" тэмдэгтэй нэмэлт (тэнцвэрийн) хувьсагчийг, хоёр дахь тэгш бус байдлын зүүн талд "хасах" тэмдэгтэй нэмэлт хувьсагчийг оруулах.

Төрөл бүрийн нэмэлт хувьсагчдын эдийн засгийн утга нь ижил биш байж болно: энэ нь эдгээр хувьсагчдыг багтаасан хязгаарлалтын эдийн засгийн утгаас хамаарна.

Тиймээс, түүхий эдийг ашиглах асуудалд түүхий эд материалын үлдэгдэл, оновчтой технологийг сонгох асуудалд тодорхой технологи ашиглан аж ахуйн нэгжийн ашиглагдаагүй хугацааг харуулдаг; огтлох асуудалд - төлөвлөгөөнөөс хэтэрсэн өгөгдсөн урттай хоосон зайг гаргах гэх мэт.

Эдийн засгийн асуудлыг шийдвэрлэх үндэс нь математик загвар юм.

математик загварБодлого гэдэг нь асуудлын мөн чанарыг тодорхойлсон математик харилцааны багц юм.

Математик загвар гаргахад дараахь зүйлс орно.

• даалгаврын хувьсагчийн сонголт
• хязгаарлалтын тогтолцоог боловсруулах
• зорилгын функцийг сонгох

Даалгаврын хувьсагчидэдийн засгийн үйл явцыг бүрэн тодорхойлдог X1, X2, Xn хэмжигдэхүүнүүд гэж нэрлэдэг. Ихэвчлэн тэдгээрийг вектор хэлбэрээр бичдэг: X=(X 1 , X 2 ,...,X n).

Хязгаарлалтын системдаалгавар гэдэг нь авч үзэж буй асуудлын хязгаарлагдмал нөөцийг тодорхойлсон тэгшитгэл ба тэгш бус байдлын багц юм.

зорилтот функцдаалгаврын чанарыг тодорхойлох үүрэг даалгаврын хувьсагчийн функц ба түүний экстремумыг олох шаардлагатай гэж нэрлэдэг.

Ерөнхийдөө шугаман програмчлалын бодлогыг дараах байдлаар бичиж болно.

Энэ оруулга нь дараахыг хэлнэ: зорилгын функцийн экстремум (1) ба харгалзах хувьсагчид X=(X 1 , X 2 ,...,X n) эдгээр хувьсагч нь хязгаарлалт (2) ба бус хязгаарлалтын системийг хангасан тохиолдолд ол. -сөрөг нөхцөл (3) .

Зөвшөөрөгдөх шийдэлШугаман програмчлалын бодлогын (төлөвлөгөө) нь хязгаарлалтын систем ба сөрөг бус нөхцлүүдийг хангасан дурын n хэмжээст X=(X 1 , X 2 ,...,X n) вектор юм.

Асуудлын боломжит шийдлүүдийн багц (төлөвлөгөө). боломжит шийдлүүдийн хүрээ(ODR).

Хамгийн оновчтой шийдэлШугаман програмчлалын бодлогын (төлөвлөгөө) нь зорилгын функц нь туйлдаа хүрдэг асуудлын ийм боломжтой шийдэл (төлөвлөгөө) юм.

Математик загварыг эмхэтгэх жишээ

Нөөц (түүхий эд) ашиглах даалгавар

Нөхцөл: N төрлийн бүтээгдэхүүн үйлдвэрлэхэд m төрлийн нөөцийг ашигладаг. Математик загвар хий.

Мэдэгдэж байгаа:

• b i (i = 1,2,3,...,m) нь i-р төрлийн нөөц бүрийн нөөц;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) нь i-р төрлийн нөөц бүрийн нэгж эзлэхүүнийг үйлдвэрлэх зардал юм. j-р төрлийн бүтээгдэхүүн;
• c j (j = 1,2,3,...,n) нь j-р төрлийн бүтээгдэхүүний нэгж эзлэхүүний борлуулалтаас олох ашиг юм.

Нөөцийн (түүхий эд) өгөгдсөн хязгаарлалттай хамгийн их ашиг олох бүтээгдэхүүн үйлдвэрлэх төлөвлөгөө гаргах шаардлагатай.

Шийдэл:

Бид X=(X 1 , X 2 ,...,X n) хувьсагчийн векторыг танилцуулж байна, энд x j (j = 1,2,...,n) нь j-р төрлийн үйлдвэрлэлийн хэмжээ юм. бүтээгдэхүүн.

Өгөгдсөн хэмжээ x j бүтээгдэхүүн үйлдвэрлэх i-р төрлийн нөөцийн зардал нь ij x j-тэй тэнцүү тул бүх төрлийн бүтээгдэхүүн үйлдвэрлэхэд нөөцийг ашиглах хязгаарлалт нь дараахь хэлбэртэй байна.
j-р төрлийн бүтээгдэхүүнийг борлуулсны ашиг нь c j x j -тэй тэнцүү тул зорилгын функц нь дараахтай тэнцүү байна.

Хариулах- Математик загвар нь дараах байдалтай байна.

Шугаман програмчлалын бодлогын каноник хэлбэр

Ерөнхий тохиолдолд шугаман програмчлалын бодлогыг тэгшитгэл ба тэгш бус байдал хоёулаа хязгаарлалт байхаар бичдэг бөгөөд хувьсагч нь сөрөг биш эсвэл дур зоргоороо өөрчлөгдөж болно.

Бүх хязгаарлалтууд тэгшитгэл бөгөөд бүх хувьсагч нь сөрөг бус нөхцөлийг хангаж байвал шугаман програмчлалын бодлогыг гэнэ. каноник.

Үүнийг координат, вектор, матрицын тэмдэглэгээгээр илэрхийлж болно.

Координатын тэмдэглэгээ дэх каноник шугаман програмчлалын бодлого нь дараах хэлбэртэй байна.

Матрицын тэмдэглэгээний каноник шугаман програмчлалын бодлого нь дараах хэлбэртэй байна.

• А нь тэгшитгэлийн системийн коэффициентүүдийн матриц юм
• X нь даалгаврын хувьсагчдын баганын матриц юм
• Ao нь хязгаарлалтын системийн баруун хэсгүүдийн матриц-багана юм

Ихэнхдээ матрицын тэмдэглэгээнд дараахь хэлбэртэй тэгш хэмт гэж нэрлэгддэг шугаман програмчлалын асуудлуудыг ашигладаг.

Шугаман програмчлалын ерөнхий бодлогыг каноник хэлбэрт оруулах

Шугаман програмчлалын асуудлыг шийдвэрлэх ихэнх аргуудад хязгаарлалтын систем нь хувьсагчдын сөрөг бус байдлын тэгшитгэл ба байгалийн нөхцлөөс бүрддэг гэж үздэг. Гэсэн хэдий ч эдийн засгийн асуудлын загварыг эмхэтгэхдээ хязгаарлалтууд нь голчлон тэгш бус байдлын систем хэлбэрээр үүсдэг тул тэгш бус байдлын системээс тэгшитгэлийн систем рүү шилжих чадвартай байх шаардлагатай.

Үүнийг дараах байдлаар хийж болно.

a 1 x 1 +a 2 x 2 +...+a n x n ≤b шугаман тэгш бус байдлыг авч, түүний зүүн талд x n+1 утгыг нэмж, тэгш бус байдал нь a 1 x 1 +a 2 x 2 + тэгшитгэл болно. ...+a n x n +x n+1 =b. Түүнчлэн, энэ утга x n+1 нь сөрөг биш юм.

Бүх зүйлийг жишээгээр авч үзье.

Жишээ 26.1

Шугаман програмчлалын асуудлыг каноник хэлбэр болгон бууруул:

Шийдэл:
Зорилгын функцийн максимумыг олох бодлого руу шилжье.
Үүнийг хийхийн тулд бид зорилгын функцийн коэффициентүүдийн тэмдгүүдийг өөрчилдөг.
Хязгаарлалтын системийн хоёр ба гурав дахь тэгш бус байдлыг тэгшитгэл болгон хөрвүүлэхийн тулд бид сөрөг бус нэмэлт хувьсагч x 4 x 5 (энэ үйлдлийг математик загвар дээр D үсгээр тэмдэглэсэн) оруулдаг.
Хоёр дахь тэгш бус байдлын зүүн талд x 4 хувьсагчийг "+" тэмдгээр оруулна, учир нь тэгш бус байдал нь "≤" хэлбэртэй байна.
Тэгш бус байдал нь "≥" хэлбэртэй тул гурав дахь тэгш бус байдлын зүүн талд x 5 хувьсагчийг "-" тэмдгээр оруулна.
Х 4 х 5 хувьсагчдыг зорилгын функцэд коэффициентээр оруулна. тэгтэй тэнцүү.
Бид асуудлыг каноник хэлбэрээр бичдэг.