x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Анхааруулга

Бүх нүдийг арилгах уу?

Цэвэр хаах

Өгөгдөл оруулах заавар.Тоонуудыг бүхэл тоо (жишээ нь: 487, 5, -7623 гэх мэт), аравтын бутархай (жишээ нь. 67., 102.54 гэх мэт) эсвэл бутархай хэлбэрээр оруулна. Бутархайг a/b хэлбэрээр оруулах ёстой бөгөөд a ба b (b>0) нь бүхэл тоо эсвэл аравтын тоо юм. Жишээ 45/5, 6.6/76.4, -7/6.7 гэх мэт.

Симплекс арга

Simplex аргыг ашиглан ZLP-ийг шийдвэрлэх жишээ

Жишээ 1. Дараах шугаман програмчлалын бодлогыг шийд.

Тэгшитгэлийн системийн хязгаарлалтын баруун тал нь дараах хэлбэртэй байна.

Одоогийн лавлах төлөвлөгөөг бичье:

Сүүлийн эгнээнд сөрөг элементүүд байгаа тул энэ лавлах төлөвлөгөө нь оновчтой биш юм. Модулийн хамгийн том сөрөг элемент нь (-3) тул векторыг суурьт оруулсан болно x цагт . мин(40:6, 28:2)=20/3 нь 1-р мөрөнд тохирч байна. Суурь дээрээс вектор гарч ирнэ. x 3. Баганын хувьд Гауссын хасалтыг хийцгээе x 2, тэргүүлэгч элемент нь 1-р мөртэй тохирч байгааг харгалзан үзвэл, энэ баганын тэргүүлэх элементээс бусад бүх элементүүдийг дахин тохируулъя. Үүнийг хийхийн тулд -1/3, 1/6, 1/2-оор үржүүлсэн 1-р мөрөнд 2, 3, 4-ийн мөрүүдийг нэмнэ. Дараа нь бид тэргүүлэх элементтэй мөрийг тэргүүлэх элементээр хуваана.

Сүүлийн мөрөнд сөрөг элемент (-3) байгаа тул энэ лавлах төлөвлөгөө нь оновчтой биш тул суурь нь векторыг агуулдаг x 1 . Аль вектор нь суурьнаас гарахыг бид тодорхойлно. Үүнийг хийхийн тулд бид тооцоолно цагт . min(44/3:11/3, 62/3:5/3)=4 нь 2-р мөрөнд тохирч байна. Суурь дээрээс вектор гарч ирнэ. x 4 . Баганын хувьд Гауссын хасалтыг хийцгээе x 1, тэргүүлэгч элемент нь 2-р мөртэй тохирч байгааг харгалзан үзвэл энэ баганын тэргүүлэх элементээс бусад бүх элементүүдийг дахин тохируулъя. Үүнийг хийхийн тулд 1, 3, 4-р мөрийг 2-р мөрийг 1/11, -5/11, 9/11-ээр үржүүлж нэмнэ. Дараа нь бид тэргүүлэх элементтэй мөрийг тэргүүлэх элементээр хуваана.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

Хувьсагчийн доор 4-р мөрөнд байгаа тул одоогийн лавлагааны төлөвлөгөө оновчтой байна сөрөг хүчин зүйл байхгүй.

Шийдлийг дараах байдлаар бичиж болно. .

Энэ цэг дэх зорилгын функцийн утга: Ф(X)=.

Жишээ 2. Функцийн хамгийн ихийг ол

Шийдэл.

Үндсэн векторууд x 4 , x 3 Тиймээс багана дахь бүх элементүүд x 4 , xХэвтээ шугамын доорх 3 нь тэг байх ёстой.

Бүх баганын элементүүдийг тэг болго x 4, тэргүүлэх элементээс бусад. Үүнийг хийхийн тулд 3-р мөрийг 1-р мөрийг 4-өөр үржүүлж нэмнэ. Баганын бүх элементүүдийг тэг болгож дахин тохируулна уу. x 3, тэргүүлэх элементээс бусад. Үүнийг хийхийн тулд 3-р мөрийг 2-р мөрийг 1-ээр үржүүлнэ.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

Сүүлийн мөрөнд сөрөг элемент (-11) байгаа тул энэ лавлах төлөвлөгөө нь оновчтой биш тул суурь нь векторыг агуулдаг x 2. Аль вектор нь суурьнаас гарахыг бид тодорхойлно. Үүнийг хийхийн тулд бид тооцоолно цагт . Тиймээс зорилгын функц нь дээрээс хязгааргүй юм. Тэдгээр. шугаман програмчлалын асуудал шийдвэрлэх боломжгүй.

Хиймэл суурь аргыг ашиглан ZLP-ийг шийдвэрлэх жишээ

Жишээ 1. Функцийн хамгийн ихийг ол

Шийдэл.Суурь векторын тоо 3 байх ёстой тул бид зохиомол хувьсагчийг нэмж, зорилгын функцэд энэ хувьсагчийг −M-ээр үржүүлсэнийг нэмэх ба энд M нь маш их тоо:

Тэгшитгэлийн системийн коэффициент матриц нь дараах хэлбэртэй байна.

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

Тэргүүлэгч элементээс бусад баганын бүх элементүүдийг дахин тохируулцгаая. Үүнийг хийхийн тулд 5-р мөрийг -1-ээр үржүүлсэн 3-р мөрийг нэмнэ.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

Сүүлийн эгнээнд сөрөг элементүүд байгаа тул энэ лавлах төлөвлөгөө нь оновчтой биш юм. Хамгийн том үнэмлэхүй сөрөг элемент нь (-5) тул векторыг суурьт оруулсан болно.Бид аль вектор баазаас гарахыг тодорхойлно. Үүнийг хийхийн тулд бид тооцоолно цагт 3-р мөртэй тохирч байна.Суурь дээрээс вектор гарч ирнэ.Тэргүүлэх элемент нь 3-р мөртэй тохирч байгаа тул баганад Гауссын онцгой тохиолдол хийцгээе.Энэ баганын тэргүүлэх элементээс бусад бүх элементүүдийг дахин тохируулъя. Үүнийг хийхийн тулд 3-р мөрийг 1-ээр үржүүлсэн 5-р мөрийг нэмнэ. Дараа нь тэргүүлэгч элементтэй мөрийг тэргүүлэх элементээр хуваана.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

Сүүлийн эгнээнд сөрөг элементүүд байгаа тул энэ лавлах төлөвлөгөө нь оновчтой биш юм. Хамгийн том үнэмлэхүй сөрөг элемент нь (-3) тул вектор нь суурьт багтана.Бид баазаас аль вектор гарахыг тодорхойлно. Үүнийг хийхийн тулд бид тооцоолно цагт 1-р мөртэй тохирч байна. Вектор нь сууриас гарна x 2. Баганын хувьд Гауссын хасалтыг хийцгээе x 1 , тэргүүлэгч элемент нь 1-р мөртэй тохирч байгааг харгалзан үзвэл энэ баганын тэргүүлэх элементээс бусад бүх элементүүдийг дахин тохируулъя. Үүнийг хийхийн тулд 3/2, -1/10, 3/2-оор үржүүлсэн 1-р мөрөнд 2, 3, 4-ийн мөрүүдийг нэмнэ. Дараа нь бид тэргүүлэх элементтэй мөрийг тэргүүлэх элементээр хуваана.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

Сүүлийн эгнээнд сөрөг элементүүд байгаа тул энэ лавлах төлөвлөгөө нь оновчтой биш юм. Модулийн хамгийн том сөрөг элемент (-13/2) тул суурь нь векторыг агуулна x 3. Аль вектор нь суурьнаас гарахыг бид тодорхойлно. Үүнийг хийхийн тулд бид тооцоолно цагт 3-р мөрөнд харгалзах.Суурьаас вектор гарч ирнэ x 5 . Баганын хувьд Гауссын хасалтыг хийцгээе x 3, тэргүүлэгч элемент нь 3-р мөртэй тохирч байгааг харгалзан үзвэл энэ баганын тэргүүлэх элементээс бусад бүх элементүүдийг дахин тохируулъя. Үүнийг хийхийн тулд 5/3, 25/9, 65/9-оор үржүүлсэн 3-р мөртэй 1, 2, 4-ийн мөрүүдийг нэмнэ. Дараа нь бид тэргүүлэх элементтэй мөрийг тэргүүлэх элементээр хуваана.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

4−5-р мөрийн хувьсагчдын дор сөрөг элемент байхгүй тул одоогийн лавлагааны төлөвлөгөө оновчтой байна.

Анхны асуудлын шийдлийг дараах байдлаар бичиж болно.

Жишээ 2. Шугаман програмчлалын бодлогын оновчтой төлөвлөгөөг ол:

Тэгшитгэлийн системийн коэффициент матриц нь дараах хэлбэртэй байна.

Үндсэн векторууд x 4 , x 5 , x 6 Тиймээс багана дахь бүх элементүүд x 4 , x 5 , x 6, хэвтээ шугамын доор тэг байх ёстой.

Бүх баганын элементүүдийг тэг болго x 4, тэргүүлэх элементээс бусад. Үүнийг хийхийн тулд 1-р мөрийг -1-ээр үржүүлсэн 4-р мөрийг нэмнэ. Бүх баганын элементүүдийг тэг болго x 5, тэргүүлэх элементээс бусад. Үүнийг хийхийн тулд 5-р мөрийг 2-р мөрийг -1-ээр үржүүлнэ. Бүх баганын элементүүдийг тэг болго x 6, тэргүүлэх элементээс бусад. Үүнийг хийхийн тулд 5-р мөрийг -1-ээр үржүүлсэн 3-р мөрийг нэмнэ.

Симплекс хүснэгт нь дараах хэлбэртэй байна.

5-р мөрөнд хувьсагчид харгалзах элементүүдийг оруулна x 1 , x 2 , x 3 , x 4 , x 5 , x 6 нь сөрөг биш бөгөөд өгөгдсөн мөр, баганын уулзварт байрлах тоо x 0 сөрөг байна. Дараа нь анхны асуудал нь лавлагааны төлөвлөгөөгүй. Тиймээс үүнийг шийдэх боломжгүй юм.

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

Зорилго функц:

2х 1 +5х 2 +3х 3 +8х 4 →мин

Хязгаарлалтын нөхцөл:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4х 1 -13х 2 +10х 3 +5х 4 ≥6
3x 1 +7x 2 +x 3 ≥1

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

Бидний асуудал бол багасгах асуудал тул бид үүнийг хамгийн их хайлтын бодлого болгон хувиргах хэрэгтэй. Үүнийг хийхийн тулд бид зорилгын функцийн коэффициентүүдийн тэмдгүүдийг эсрэгээр нь өөрчилдөг. Бид эхний тэгш бус байдлын элементүүдийг өөрчлөгдөөгүй бичиж, нэмэлт x 5 хувьсагчийг нэмж, "≤" тэмдгийг "=" болгон өөрчилнө. Хоёр ба гурав дахь тэгш бус байдал нь "≥" тэмдэгтэй тул тэдгээрийн коэффициентуудын тэмдгийг эсрэгээр нь сольж, нэмэлт x 6 ба x 7 хувьсагчдыг тус тус оруулах шаардлагатай. Үүний үр дүнд бид ижил төстэй асуудалтай тулгардаг:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4х 1 +13х 2 -10х 3 -5х 4 +х 6 =-6
-3х 1 -7х 2 -х 3 +х 7 =-1

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

					Чөлөөт гишүүн
Ф
X5
X6
X7

Бидний эмхэтгэсэн хүснэгтэд чөлөөт нэр томъёоны баганад сөрөг элементүүд байгаа бөгөөд тэдгээрийн дотроос модулийн хамгийн их утгыг олдог - энэ бол элемент юм: -6, тэргүүлэгч эгнээ - X6. Энэ мөрөнд бид модулийн хамгийн их сөрөг элементийг олдог: -10 нь X3 баганад байрладаг бөгөөд энэ нь тэргүүлэх багана байх болно. Тэргүүлэх эгнээнд байгаа хувьсагчийг үндсэнээс хасаж, тэргүүлэх баганад харгалзах хувьсагчийг үндсэнд оруулна. Симплекс хүснэгтийг дахин тооцоолъё:

	X1	X2	X6	X4	Чөлөөт гишүүн
Ф	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

Бидний эмхэтгэсэн хүснэгтэд чөлөөт нэр томъёоны баганад сөрөг элементүүд байгаа бөгөөд тэдгээрийн дотроос модулийн хамгийн их утгыг олдог - энэ бол элемент юм: -0.4, тэргүүлэгч эгнээ - X7. Энэ мөрөнд бид модулийн хамгийн их сөрөг элементийг олдог: -8.3 энэ нь X2 баганад байрладаг бөгөөд энэ нь тэргүүлэх багана байх болно. Тэргүүлэх эгнээнд байгаа хувьсагчийг үндсэнээс хасаж, тэргүүлэх баганад харгалзах хувьсагчийг үндсэнд оруулна. Симплекс хүснэгтийг дахин тооцоолъё:

	X1	X7	X6	X4	Чөлөөт гишүүн
Ф	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Чөлөөт нэр томьёоны баганад сөрөг элемент байхгүй тул зөвшөөрөгдөх шийдлийг оллоо.F мөрөнд сөрөг элементүүд байгаа бөгөөд энэ нь гарсан шийдэл нь оновчтой биш гэсэн үг юм. Тэргүүлэх баганыг тодорхойлъё. Үүнийг хийхийн тулд бид F мөрөнд хамгийн их модуль бүхий сөрөг элементийг олох болно - энэ нь -1.988 Тэргүүлэх мөр нь чөлөөт нэр томъёоны тэргүүлэх баганын харгалзах элементтэй харьцуулсан харьцаа хамгийн бага байх болно. Тэргүүлэх мөр нь X2, тэргүүлэх элемент нь: 0.313.

	X2	X7	X6	X4	Чөлөөт гишүүн
Ф	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

F мөрөнд сөрөг элемент байхгүй тул
оновчтой шийдэл олдсон. Анхны даалгавар нь хамгийн бага утгыг олох байсан тул эсрэг тэмдэгтэй F тэмдэгт мөрний чөлөөт гишүүн нь оновчтой шийдэл байх болно. F=1.924
хувьсах утгатай тэнцүү: x 3 =0.539, x 1 =0.153. x 2 ба x 4 хувьсагчдыг суурьт оруулаагүй тул x 2 =0 x 4 =0 байна.

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

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

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

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

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

Систем байгаасай м-аас хязгаарлалтууд nхувьсагч ( м n).

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

Ямар ч мсистемийн хувьсагч мшугаман тэгшитгэлүүд nхувьсагч гэж нэрлэдэг гол , хэрэв тэдгээрийн коэффициентүүдийн тодорхойлогч нь тэгээс ялгаатай бол. Дараа нь бусад нь n - мхувьсагч гэж нэрлэдэг үндсэн бус (эсвэл үнэгүй ).

Энгийн аргын алгоритм

• 1-р алхам. Шугаман програмчлалын бодлогыг каноник хэлбэр болгон бууруул. Үүнийг хийхийн тулд чөлөөт нэр томъёог баруун гар тал руу шилжүүлээрэй (хэрэв эдгээр чөлөөт нэр томъёоны дунд сөрөг утгатай бол харгалзах тэгшитгэл эсвэл тэгш бус байдлыг - 1-ээр үржүүлнэ) ба хязгаарлалт бүрт нэмэлт хувьсагчийг оруулаарай (хэрэв байгаа бол нэмэх тэмдэгтэй). анхны тэгш бус байдлын тэмдэг нь "бага буюу тэнцүү" ", хэрэв "илүү эсвэл тэнцүү" бол хасах тэмдэгтэй).
• Алхам 2. Хэрэв үүссэн системд байгаа бол мтэгшитгэл, тэгвэл мхувьсагчдыг гол хувьсагч болгон авч, үндсэн бус хувьсагчаар нь илэрхийлж, харгалзах үндсэн шийдлийг олно. Хэрэв олсон үндсэн шийдэл нь зөвшөөрөгдөх боломжтой гэж үзвэл зөвшөөрөгдөх үндсэн шийдэл рүү очно уу.
• Алхам 3. Зорилгын функцийг зөвшөөрөгдөх суурь шийдлийн үндсэн бус хувьсагчаар илэрхийл. Хэрэв шугаман хэлбэрийн максимум (хамгийн бага) олдвол түүний илэрхийлэлд сөрөг (эерэг) коэффициент бүхий үндсэн бус хувьсагч байхгүй бол оновчтой байдлын шалгуур хангагдсан бөгөөд үндсэн шийдэл нь оновчтой - шийдэл бүрэн байна. Шугаман хэлбэрийн максимум (хамгийн бага)-ийг олохдоо түүний илэрхийлэл сөрөг (эерэг) коэффициент бүхий нэг буюу хэд хэдэн үндсэн бус хувьсагчийг агуулж байвал шинэ үндсэн шийдэл рүү шилжинэ.
• Алхам 4. Сөрөг (эерэг) коэффициент бүхий шугаман хэлбэрт орсон үндсэн бус хувьсагчдаас хамгийн том (үнэмлэхүй утгаараа) коэффициенттэй тохирохыг сонгон үндсэн үзүүлэлт рүү хөрвүүлнэ. 2-р алхам руу оч.

Чухал нөхцөлүүд

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

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

Симплекс хүснэгт бүхий симплекс арга

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

Бутархайтай үйлдлүүд гарын авлагыг шинэ цонхонд нээх нь ашигтай байх болно: энгийнээр хэлбэл симплекс аргыг ашигласан асуудалд хангалттай тоо байдаг.

Жишээ.

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

.

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

Оруулсан нэмэлт хувьсагчдыг үндсэн (үндсэн хувьсагч) болгон авдаг. Дараа нь ба нь үндсэн бус (чөлөөт) хувьсагч юм.

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

Мөн бид зорилгын функцийг үндсэн бус (чөлөөт) хувьсагчаар илэрхийлж болно:

(Үл мэдэгдэх) хувьсагчдын коэффициентүүдээс бид анхны симплекс хүснэгтийг байгуулна.

Хүснэгт 1
Үндсэн үл мэдэгдэх зүйлс	Чөлөөт гишүүд	Үнэгүй үл мэдэгдэх зүйлс		Туслах коэффициентүүд
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
Ф	0	-1	-2

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

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

Дараагийн хүснэгт рүү шилжихийн тулд хамгийн том (модуль) болон тоонуудыг олцгооё. Энэ тоо нь 2. Тиймээс тэргүүлэх багана нь байгаа багана юм

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

.

Тиймээс тэргүүлэгч мөр нь бичигдсэн мөр юм

Тиймээс тэргүүлэх элемент нь -2 байна.

Бид хоёр дахь симплекс хүснэгтийг бүрдүүлдэг.

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

Эхний мөрийг бөглөнө үү. Үүнийг хийхийн тулд бид 1-р хүснэгтийн эхний эгнээний бүх тоог тэргүүлэх элементээр хувааж, эхний баганын урвуу тооноос бусад хүснэгтийн 2-ын эхний эгнээний харгалзах баганад бичнэ. элемент бичигдсэн (өөрөөр хэлбэл нэгийг тэргүүлэх элементээр хуваасан).

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

хүснэгт 2
Үндсэн үл мэдэгдэх зүйлс	Чөлөөт гишүүд	Үнэгүй үл мэдэгдэх зүйлс		Туслах коэффициентүүд
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
Ф	2	-2	-1	2

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

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

Жишээлбэл, хоёр дахь эгнээний чөлөөт нэр томъёог олж авахын тулд бид 1-ийн тоог 1-ээр үржүүлж, 1-р хүснэгтээс -4 тоог нэмнэ. Бид -3 авдаг. Хоёр дахь мөрөнд бид коэффициентийг олдог. . Өмнөх хүснэгтэд шинэ чөлөөт хувьсагчтай багана байхгүй тул шинэ чөлөөт хувьсагчийн баганын хоёр дахь эгнээний коэффициент дараах байдалтай байна. (өөрөөр хэлбэл 1-р хүснэгтэд c багана байхгүй тул бид 1-р хүснэгтээс 0-ийг нэмнэ).

Индексийн мөрийг мөн бөглөнө:

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

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

Тэргүүлэх эгнээг олохын тулд бид тэргүүлэх эгнээний элементүүдийн чөлөөт нөхцлийн хамгийн бага харьцааг олно. Бид авах:

.

Иймд тэргүүлэх шугам нь , тэргүүлэх элемент нь -3/2 байна.

Гурав дахь симплекс хүснэгтийг эмхэтгэж байна

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

Эхний мөр:

Туслах коэффициентүүд:

Хүснэгт 3
Үндсэн үл мэдэгдэх зүйлс	Чөлөөт гишүүд	Үнэгүй үл мэдэгдэх зүйлс		Туслах коэффициентүүд
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
Ф	6	-4/3	-1/3	2

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

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

Тиймээс тэргүүлэх багана нь .

Чөлөөт гишүүдийн тэргүүлэх баганын элементүүдтэй харилцах хамгийн бага модулиуд:

.

Тиймээс тэргүүлэх шугам нь , тэргүүлэх элемент нь 1/3 байна.

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

Эхний мөр:

Туслах коэффициентүүд:

Хүснэгт 4
Үндсэн үл мэдэгдэх зүйлс	Чөлөөт гишүүд	Үнэгүй үл мэдэгдэх зүйлс		Туслах коэффициентүүд
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
Ф	14	4	-3	4/3

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

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

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

4 ба гэсэн тоонуудаас хамгийн томыг нь олъё. Энэ тоо нь 4. Тиймээс тэргүүлэх багана нь .

Тэргүүлэх шугамыг олохын тулд бид олдог

.

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

Тэргүүлэх шугамыг олохын тулд бид олдог

.

Тиймээс гол мөр нь , тэргүүлэх элемент нь 1 байна.

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

Эхний мөр:

Туслах коэффициентүүд:

Хүснэгт 5
Үндсэн үл мэдэгдэх зүйлс	Чөлөөт гишүүд	Үнэгүй үл мэдэгдэх зүйлс		Туслах коэффициентүүд
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
Ф	20	1	3	3

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

Чөлөөт гишүүд:

Хоёр дахь мөрөнд;

Гурав дахь мөрөнд;

Дөрөв дэх мөрөнд.

Индекс мөр:

Бид симплекс хүснэгт 5-ыг харлаа. Индексийн шугам дахь чөлөөт үл мэдэгдэх коэффицентүүд нь сөрөг биш тул оновчтой шийд гарсан байна.

Алгебрийн хувиргалт бүхий симплекс арга

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

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

Жишээ.Хязгаарлалттай функцийн хамгийн ихийг ол

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

.

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

Үндсэн хувьсагчдыг үндсэн бус хувьсагчаар илэрхийлбэл бид олж авна

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

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

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

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

ZLP-ийг шийдэхийн тулд симплекс аргаэнэ нь каноник хэлбэрт хүргэгдсэн, i.e. Хязгаарлалтаас - тэгш бус байдлаас - хязгаарлалт хийх шаардлагатай - тэгш байдал. Үүнийг хийхийн тулд хязгаарлалт бүрт сөрөг бус нэмэлт хүчин зүйлийг оруулсан болно балансын хувьсагчтэгш бус байдлын тэмдэг нь “£” бол “+” тэмдгээр, “³” бол “–” тэмдгээр.

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

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

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

1. Эхний лавлах төлөвлөгөөг гаргах

Даалгавар ижил хэвээр байна. Тэгш бус байдлын системийн стандарт хэлбэрийг (1) тэгшитгэлийн системийн каноник хэлбэрт нэмэлт тэнцвэрийн хувьсагч оруулах замаар авч үзье. x 3 , x 4 , x 5 ,x 6 .

Эдийн засгийн утгаараа нэмэлт хувьсагчдын утгууд x 3 , x 4 , x 5 бүтээгдэхүүн борлуулсны дараа үлдсэн түүхий эдийг тодорхойлох.

Үүссэн тэгшитгэлийн системийн матриц нь дараах хэлбэртэй байна.

Үүнийг матрицаас харж болно А 4-р эрэмбийн минор суурь нь нэмэлт хувьсагчдын нэгжийн коэффициентуудаас бүрдэх тодорхойлогч юм. x 3 , x 4 , x 5 ,x 6, тэгээс ялгаатай бөгөөд 1-тэй тэнцүү тул эдгээр хувьсагчдын баганын векторууд нь шугаман хамааралгүй, өөрөөр хэлбэл. хэлбэр суурь, болон харгалзах хувьсагчид x 3 , x 4 , x 5 ,x 6 нь үндсэн(үндсэн). Хувьсагч x 1 , x 2 дуудагдах болно үнэгүй(үндсэн бус).

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

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

Үндсэн шийдлүүдийн тоо болон үндсэн хувьсагчдын бүлгүүдийн харгалзах тоо нь -ээс ихгүй байж болно, хаана n- хувьсагчийн нийт тоо, r- үндсэн хувьсагчийн тоо, r≤ м≤ n.

Бидний даалгаврын төлөө r = 4; n= 6. Дараа нь , i.e. 4 үндсэн хувьсагчийн 15 бүлэг (эсвэл 15 үндсэн шийдэл) боломжтой.

Үндсэн хувьсагчдын тэгшитгэлийн системийг шийдье x 3 , x 4 , x 5 ,x 6:

Чөлөөт хувьсагч гэж үзвэл x 1 = 0, x 2 = 0, бид үндсэн хувьсагчдын утгыг олж авна. x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, өөрөөр хэлбэл. үндсэн шийдэл нь = (0; 0; 312; 15; 24; –10) болно.

Энэ бол үндсэн шийдэл юм хүлээн зөвшөөрөх боломжгүй, учир нь x 6 = –10 ≤ 0, мөн хязгаарлалтын нөхцлийн дагуу x 6 ≥ 0. Тиймээс хувьсагчийн оронд x 6 Үндэслэл болгон чөлөөт хувьсагчаас өөр нэг хувьсагчийг авах ёстой x 1 эсвэл x 2 .

Бид дараагийн шийдлийг богиносгосон симплекс хүснэгтүүдийг ашиглан хийж, эхний хүснэгтийн мөрүүдийг системийн коэффициентүүдээр дараах байдлаар бөглөнө (Хүснэгт 1):

Хүснэгт 1

Ф- шугам гэж нэрлэдэг индекс. Функцийн тэгшитгэлийг хэлбэрээр илэрхийлж болох тул эсрэг тэмдгээр авсан зорилгын функцийн коэффициентүүдээр дүүргэгдсэн болно. Ф = 0 – (– 4x 1 – 3x 2).

Чөлөөт гишүүдийн баганад б бисөрөг элемент байна б 4 = -10, өөрөөр хэлбэл. Системийн шийдэл буруу байна. Боломжит шийдэл (лавлагаа төлөвлөгөө) авахын тулд элемент б 4 нь сөрөг биш байх ёстой.

Сонго x 6 -сөрөг чөлөөт нэр томъёо бүхий мөр. Энэ мөрөнд сөрөг элементүүд орно. Тэдгээрийн аль нэгийг нь сонгоно уу, жишээ нь "–1" in x 1 - багана, ба x 1-р баганыг дараах байдлаар авна нарийвчлалын багана(энэ нь хувьсагч болохыг тодорхойлох болно x 1 нь үнэ төлбөргүйгээс үндсэн рүү шилжих болно).

Бид чөлөөт гишүүдийг хуваадаг б бихаргалзах элементүүдэд а ньтогтоолын багана, бид авна үнэлгээний харилцааΘ би= = (24, 15, 12, 10). Эдгээрээс бид хамгийн бага эерэгийг (minΘ би=10), энэ нь тохирох болно зөвшөөрлийн шугам. Идэвхжүүлэх мөр нь хувьсагчийг тодорхойлдог x j, энэ нь дараагийн алхамд үндсэнээсээ цухуйж, чөлөөтэй болно. Тийм ч учраас x 6-мөр нь идэвхжүүлэх мөр, "–1" элемент нь зөвшөөрөх элемент. Үүнийг дугуйлцгаая. Хувьсагч x 1 ба x 6-г сольсон.

Тооцоолсон харьцаа Θ бимөр бүрт дүрмийн дагуу тодорхойлогддог.

1) Θ би= хэрэв б биТэгээд а ньөөр өөр шинж тэмдэгтэй байх;

2) Θ би= ∞, хэрэв б би= 0 ба а нь < 0;

3) Θ би= ∞, хэрэв а нь = 0;

4) Θ би= 0 бол б би= 0 ба а нь > 0;

5) Θ би= хэрэв б биТэгээд а ньижил шинж тэмдэгтэй байна.

Бид Шийдвэрлэх элементээр өөрчлөгдсөн Жорданыг арилгах (JEME) алхамыг хийж, дараах дүрмийн дагуу шинэ хүснэгтийг (Хүснэгт 2) бүрдүүлнэ.

1) шийдвэрлэх элементийн (RE) оронд түүний урвуу утгатай утгыг тогтооно, өөрөөр хэлбэл. ;

2) идэвхжүүлэх мөрийн элементүүд нь RE-д хуваагдана;

3) тогтоолын баганын элементүүдийг RE-д хувааж, тэмдэг өөрчлөгдөнө;

4) үлдсэн элементүүд нь тэгш өнцөгт дүрмийн дагуу байрладаг.

Ширээн дээрээс 2 дахь чөлөөт нөхцлүүд нь тодорхой байна б би- багана нь сөрөг биш тул эхний боломжит шийдлийг олж авна - Эхний лавлах төлөвлөгөө= (10; 0; 182; 5; 4; 0). Энэ тохиолдолд функцийн утга Ф() = 40. Геометрийн хувьд энэ нь дээд талтай тохирч байна Ф(10; 0) уусмалын олон өнцөгт (Зураг 1).

хүснэгт 2

2. Бид төлөвлөгөөг оновчтой эсэхийг шалгадаг.Лавлагаа төлөвлөгөө нь оновчтой биш юм, оноос хойш Ф-мөр нь сөрөг коэффициент “–4” байна. Бид төлөвлөгөөгөө сайжруулдаг.

3. Шинэ лавлах төлөвлөгөө олох

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

Бид хамгийн бага сөрөг коэффициентийг сонгоно Ф-хэрэгжүүлэх баганыг тодорхойлсон "–4" мөр - x 6; хувьсагч x 6 үндсэн хэлбэрт шилжсэн;

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

мин Θ би = мин(14, 5, 2, ∞) = 2, тиймээс, x 5 мөр - идэвхжүүлэх, хувьсагч x 5 нь үнэгүй (хувьсагч x 5 ба x 6-г сольсон).

Шийдвэрлэх мөр ба баганын огтлолцол дээр "2" шийдвэрлэх элемент байна;

Бид SMGI алхамыг хийж, ширээ барьдаг. Дээрх дүрмийн дагуу 3-ыг авч үзвэл бид шинэ лавлах төлөвлөгөө = (12; 0; 156; 3; 0; 2) авна.

Хүснэгт 3

4. Шинэ жишиг төлөвлөгөөг оновчтой эсэхийг шалгах

Лавлагаа төлөвлөгөө нь бас оновчтой биш юм, оноос хойш Ф-мөр нь сөрөг коэффициент “–1” байна. Функцийн үнэ цэнэ Ф() = 48, энэ нь геометрийн хувьд дээд талтай тохирч байна Э(12; 0) уусмалын олон өнцөгт (Зураг 1). Бид төлөвлөгөөгөө сайжруулдаг.

5. Шинэ лавлах төлөвлөгөө олох

x 2-р багана нь зөвшөөрөгдсөн, оноос хойш Ф-мөр, хамгийн бага сөрөг коэффициент “–1” байна x 2 багана (Δ 2 = –1). Бид хамгийн жижиг Θ-г олдог би: мин Θ би = мин(≈ 9, 6, ∞, 24) = 6, тиймээс, x 4 мөр - зөвшөөрөх. Нарийвчлалын элемент "1/2". Хувьсагчдыг солих x 2 ба x 4 . Бид SMGI алхамыг хийж, ширээ барьдаг. 4, бид шинэ лавлах төлөвлөгөө = (9; 6; 51; 0; 0; 5) авна.

6. Лавлах төлөвлөгөөг оновчтой эсэхийг шалгах

IN Ф-шугам, бүх коэффициентүүд сөрөг биш тул лавлагаа төлөвлөгөө оновчтой байна. Геометрийн хувьд цэгтэй тохирч байна Д(9;6) (1-р зургийг үз). Оновчтой төлөвлөгөө нь зорилгын функцийн хамгийн их утгыг өгдөг c.u.

Симплекс арга нь LP асуудлыг тоон аргаар шийдвэрлэх хамгийн үр дүнтэй аргуудын нэг юм. "Симплекс" гэсэн ойлголтын мөн чанар нь дараах байдалтай байна. k хэмжээст орон зай дахь биеийн хувьд симплекс нь энэ биеийн k + 1 оройноос бүрдэх олонлог юм.Тэгэхээр k = 2-ын хувьд, өөрөөр хэлбэл. хавтгай дээр симплекс нь гурвалжны оройнууд байх болно; k = 3-ын хувьд симплекс нь тетраэдрийн оройнууд, жишээлбэл, тетраэдр гэх мэт. Зорилтот функц нь туйлын утгатай байх оройн координатыг тодорхойлохын тулд ODZP-ийн оройнуудын дараалсан хайлт дээр үндэслэсэн тул уг аргыг энэ нэрийг өгсөн.

Үүнийг хоёр үндсэн үе шатанд хуваадаг. Эхний шатанд хязгаарлалтын системийг хангасан шийдлүүдийн аль нэг нь олддог. N > m хязгаарлалтаас олон хувьсагчтай системийг тодорхойгүй гэж нэрлэдэг. Тэдгээр нь N-m аливаа хувьсагчийг тэгтэй тэнцүүлэх замаар тодорхой системд (N = m) буурдаг. Энэ нь m үл мэдэгдэх m тэгшитгэлийн системийг үлдээдэг бөгөөд системийн тодорхойлогч нь тэгээс өөр байвал шийдэлтэй байдаг. Симплекс арга нь үндсэн хувьсагч буюу суурь гэсэн ойлголтыг танилцуулдаг. Суурь нь m-хязгаарлалт дахь эдгээр хувьсагчийн коэффициентуудаас бүрдэх тодорхойлогч нь тэгээс өөр байх m хувьсагчийн дурын багц юм. Үлдсэн N-m хувьсагчдыг үндсэн бус буюу чөлөөт хувьсагч гэж нэрлэдэг. Хэрэв бид бүх үндсэн бус хувьсагчдыг тэгтэй тэнцүү гэж үзэж, үндсэн хувьсагчдын хязгаарлалтын системийг шийдвэл үндсэн шийдлийг олж авна.

N үл мэдэгдэх m тэгшитгэлийн системд N > m-ийн үндсэн шийдүүдийн нийт тоог хослолын тоогоор тодорхойлно.

Бүх x i 0, i = 1,m гэсэн үндсэн шийдлийг нэрлэнэ зөвшөөрөгдөх үндсэн шийдэл.Тиймээс симплекс аргыг ашиглан шийдлийн эхний үе шат нь амжилтгүй болсон ч хүлээн зөвшөөрөгдөх үндсэн шийдлийг олох замаар төгсдөг.

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

1) үндсэн хувьсагч ба зорилгын функц нь үндсэн бус хувьсагчаар илэрхийлэгддэг;

2) тодорхой дүрмийн дагуу үндсэн бус хувьсагчийн аль нэгийг сонгож, түүний утгыг өөрчлөх нь F(x)-ийн утгыг сайжруулж, түүнийг суурь болгон нэвтрүүлсэн;

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

4) үндсэн хувьсагч болон зорилгын функцийг үндсэн бус шинэ хувьсагчаар илэрхийлж, 2) ба 3) үйлдлүүд давтагдана.

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

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

Жишээ 1. Шинэ талбайд тоног төхөөрөмж худалдан авахад зориулж 20 мянган y.e. хуваарилсан. Тоног төхөөрөмжийг 72 м2-аас ихгүй талбайд байрлуулах ёстой. Хоёр төрлийн тоног төхөөрөмжийг захиалж болно: 1) 5 мянган жилийн өртөгтэй, 6 м 2 талбайг эзэлдэг, 8 мянган ширхэг үйлдвэрлэдэг тоног төхөөрөмж. нэг ээлжинд бүтээгдэхүүн; 2) 12 м2 талбайг эзэлдэг, нэг ээлжинд 4 мянган ширхэг үйлдвэрлэдэг 2 мянган жилийн үнэтэй тоног төхөөрөмж. бүтээгдэхүүн. Симплекс аргыг ашиглан сайтын хамгийн их бүтээмжийг хангах тоног төхөөрөмж худалдан авах оновчтой хувилбарыг олоорой.

Эхний болон хоёр дахь төрлийн үл мэдэгдэх тоног төхөөрөмжийг x 1 ба x 2 гэж тэмдэглэе. Зорилгын функцийг дараах байдлаар бичиж болно: F(x) = 8x 1 + 4x 2 (max). Талбайн хязгаарлалт: 6x 1 +12x 2 ≤72; зардлын хязгаарлалт: 5x 1 + 2x 2 ≤20 ; хувьсагчийн тэмдгийн хязгаарлалт х 1 ≥0 ; x 2 ≥0.

Хязгаарлалтын эхнийх нь коэффициентийг 6-д хувааж, хязгаарлалтыг тэгш байдлын хэлбэр болгон бууруулж, x 3 ба x 4 нэмэлт хувьсагчдыг оруулъя.

x 1 + 2x 2 + x 3 =12, (1)

5х 1 + 2х 2 + х 4 = 20. (2)

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

1-р алхам. Симплекс аргыг ашиглан шийдвэрлэхийн тулд бид үндсэн хувьсагчаар (BP) x 2 ба x 4-ийг сонгодог, учир нь асуудлын хязгаарлалт дахь эдгээр хувьсагчийн коэффициентуудаас бүрдэх тодорхойлогч нь тэгээс өөр байна.

Дараа нь x 1 ба x 3 нь үндсэн бус хувьсагч (NP) болно. Үндсэн хувьсагч ба F(x)-ийг үндсэн бус хувьсагчаар илэрхийлье.

(3)

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

x 4 = 20 - 2x 2 - 5x 1. (4)

Дээрх илэрхийллийг харгалзан бид олж авна

x 4 = 8 - 4x 1 + x 3. (5)

Дараа нь

F(x) = 8x 1 + 4x 2 = 24 + 6x 1 - 2x 3. (6)

Алхам бүрт NP нь тэгтэй тэнцүү тул АД ба F(x) нь харгалзах илэрхийлэл дэх чөлөөт нөхцлүүдтэй тэнцүү байх болно.

x 1 = 0, x 3 = 0, x 2 = 6, x 4 = 8, F(x) = 24.

Энэ шийдэл нь Зураг дээрх ODZP-ийн А оройн координаттай тохирч байна. 1. Зорилгын функцийн F(x) илэрхийллийг ашиглан шийдлийн оновчтой байдлыг шалгана. Хувьсагч x 3 нь сөрөг коэффициенттэй энэ илэрхийллийг оруулна; Хэрэв та дараагийн алхамд үндсэн дээр x 3-ийг оруулбал энэ нь эерэг утгыг авах бөгөөд 24-ийн тооноос тодорхой утгыг хасах болно. F(x)-ийн утга буурах болно. Хэрэв та дараагийн алхамд үндсэн дээр x 1-ийг оруулбал зорилгын функцийн утга нэмэгдэх болно, өөрөөр хэлбэл. сайжрах болно.

Симплекс аргыг ашигласнаар суурь х 1-д оруулахад эхлээд тэг рүү очдог хувьсагчийг үндсэнээс хасна. (3) ба (5)-д дүн шинжилгээ хийснээр бид x 4-ийг үндэслэлээс хасах ёстойг тодорхойлно. Дараагийн алхамд x 1 ба x 4 хувьсагчдыг солино.

Симплекс аргын 2-р алхам. x 1 ба x 2 нь үндсэн хувьсагч, x 3 ба x 4 нь үндсэн бус хувьсагч юм. Үндсэн хувьсагч болон F(x)-ийг үндсэн бус хувьсагчаар илэрхийлье. (5)-аас дараах байдалтай байна

x 1 =2+(1/4)x 3 -(1/4)x 4 (7)

Цагаан будаа. 1. Симплекс аргыг ашиглан жишээ 1-ийн график тайлбар.

(3)-д (7) орлуулснаар бид олж авна

x 2 =5-(5/8)x 3 +(1/8)x 4

Тэгвэл F(x) = 8x 1 + 4x 2 = 36 - (1/2)x 3 -(3/4)x 4. Үүний үр дүнд x 3 = x 4 = 0 (үндсэн бус байдлаар), x 1 = 2, x 2 = 5, F = 36. Энэ шийдэл нь Зураг дээрх В оройн координаттай тохирч байна. 1. Олдсон утга нь оновчтой байх бөгөөд сөрөг коэффициент бүхий зорилгын функцийн илэрхийлэлд x 3 ба x 4 хувьсагч орсон тул F(x)-ийн утгыг сайжруулах боломжгүй.

Тиймээс, симплекс аргыг ашиглан сайтын хамгийн их бүтээмж нь 36 мянган нэгж болохыг олж мэдсэн. 2 ширхэг худалдан авснаар нэг ээлжинд бүтээгдэхүүн нийлүүлнэ. эхний төрлийн тоног төхөөрөмж, 5 нэгж . хоёр дахь төрлийн тоног төхөөрөмж. Нэмэлт хувьсагч x 3 ба x 4 нь ашиглагдаагүй нөөцийн утгыг агуулна. Энэ жишээнд талбай болон зардлын хувьд бүх нөөцийг бүрэн ашигласан (x 3 = x 4 = 0).