Зорилгын функцийн оновчтой утгыг нэрлэнэ. График аргыг ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх

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

Бид x 1 x 2 координатын системд шулуун шугамыг барьдаг

Бид системээр тодорхойлсон хагас хавтгайг олдог. Системийн тэгш бус байдал нь харгалзах хагас хавтгайн аль ч цэгт хангагдах тул тэдгээрийг аль нэг цэгийн хувьд шалгахад хангалттай. Бид (0;0) цэгийг ашигладаг. Түүний координатыг системийн эхний тэгш бус байдалд орлуулъя. Учир нь , тэгвэл тэгш бус байдал нь (0;0) цэгийг агуулаагүй хагас хавтгайг тодорхойлно. Үлдсэн хагас онгоцыг бид ижил төстэй байдлаар тодорхойлдог. Бид боломжит шийдлүүдийн багцыг үүссэн хагас хавтгайн нийтлэг хэсэг гэж олдог - энэ бол сүүдэртэй газар юм.

Бид вектор ба түүнд перпендикуляр тэг түвшний шугамыг байгуулдаг.

Шулуун шугамыг (5) векторын чиглэлд хөдөлгөхөд бүс нутгийн хамгийн их цэг нь шулуун (3) ба шулуун шугамын (2) огтлолцлын А цэг дээр байх болно. Бид тэгшитгэлийн системийн шийдлийг олдог.

Энэ нь бид (13;11) цэгийг авсан гэсэн үг юм.

Шулуун шугамыг (5) векторын чиглэлд хөдөлгөхөд бүс нутгийн хамгийн бага цэг нь шулуун (1) ба шулуун шугамын (4) огтлолцлын B цэг дээр байх болно. Бид тэгшитгэлийн системийн шийдлийг олдог.

Энэ нь бид (6;6) гэсэн цэгийг авсан гэсэн үг юм.

2. Тавилгын компани хосолсон кабинет, компьютерийн ширээ үйлдвэрлэдэг. Тэдний үйлдвэрлэл нь түүхий эд (өндөр чанартай хавтан, холбох хэрэгсэл), тэдгээрийг боловсруулж буй машинуудын ажиллах хугацаа зэргээр хязгаарлагддаг. Кабинет бүрт 5 м2 самбар, ширээний хувьд 2 м2 шаардлагатай. Холбох хэрэгсэл нь нэг шүүгээнд 10 доллар, нэг ширээ 8 доллар байдаг. Тус компани ханган нийлүүлэгчдээсээ сард 600 м2 хавтан, 2000 ам.долларын үнэтэй дагалдах хэрэгслийг хүлээн авах боломжтой. Кабинет бүрт 7 цаг машин ажиллах шаардлагатай бөгөөд хүснэгтэд 3 цаг шаардагдана. Сард нийт 840 машин ажиллах цагийг ашиглах боломжтой.

Нэг кабинет нь 100 долларын ашиг авчирч, ширээ бүр нь 50 долларын орлого авчирч байвал ашгийг нэмэгдүүлэхийн тулд компани сард хэдэн хосолсон кабинет, компьютерийн ширээ үйлдвэрлэх ёстой вэ?

• 1. Зохиох математик загварасуудлыг симплекс аргаар шийднэ.
• 2. Хос бодлогын математик загвар зохиож, түүний шийдлийг эх хувилбарын шийдэлд тулгуурлан бич.
• 3. Ашигласан нөөцийн хомсдлын зэрэглэлийг тогтоож, оновчтой төлөвлөгөөний ашигт ажиллагааны үндэслэлийг гаргах.
• 4. Нөөцийн төрөл тус бүрийн ашиглалтаас хамааран үйлдвэрлэлийн гарцыг цаашид нэмэгдүүлэх боломжийг судлах.
• 5. Нэг тавиурыг үйлдвэрлэхэд 1 м 2 самбар, дагалдах хэрэгсэл 5 долларын үнэтэй, машиныг 0.25 цаг ажиллуулах, борлуулалтаас олох ашгийг зарцуулах шаардлагатай бол шинэ төрлийн бүтээгдэхүүн болох номын тавиурыг нэвтрүүлэх боломжийг үнэлэх. нэг тавиур 20 доллар.
• 1. Энэ бодлогын математик загвар бүтээцгээе.

Шүүгээний үйлдвэрлэлийн хэмжээг x 1, хүснэгтийн үйлдвэрлэлийн хэмжээг x 2 гэж тэмдэглэе. Хязгаарлалтын систем ба зорилгын функцийг бий болгоё:

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

Даалгаврын өгөгдлийг хүснэгт хэлбэрээр бичье.

Хүснэгт 1

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

САХИЛГААН ДАХЬ ХЯНАЛТЫН АЖИЛ:

“ОНОВЧТОЙ ШИЙДЛИЙН АРГА”

Сонголт No8

1. Шийдэх график аргашугаман програмчлалын асуудал. Өгөгдсөн хязгаарлалттай функцийн хамгийн их ба хамгийн бага утгыг ол:

,

.

Шийдэл

Хязгаарлалтын системийн дагуу зорилгын функцийн хамгийн бага утга ба хамгийн их утгыг олох шаардлагатай.

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Боломжит шийдлүүдийн бүсийг байгуулъя, жишээлбэл. Тэгш бус байдлын системийг графикаар шийдье. Үүнийг хийхийн тулд бид шулуун шугам бүрийг барьж, тэгш бус байдлаар тодорхойлогдсон хагас хавтгайг тодорхойлно (хагас хавтгайг анхны тоогоор тэмдэглэнэ).

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

F = 0 функцийн утгад тохирох шулуун шугамыг байгуулъя: F = 2x 1 +3x 2 = 0. Зорилгын функцийн коэффициентүүдээс бүрдэх градиент вектор нь F(X)-ийн багасгах чиглэлийг заана. Векторын эхлэл нь цэг (0; 0), төгсгөл нь (2; 3) цэг юм. Бид энэ шулуун шугамыг зэрэгцээ байдлаар шилжүүлнэ. Бид хамгийн бага шийдлийг сонирхож байгаа тул шулуун шугамыг заасан хэсэгт хүрэх хүртэл шилжүүлдэг. График дээр энэ шулуун шугамыг тасархай шугамаар зааж өгсөн болно.

Чигээрээ
мужийг C цэгт огтолдог. С цэг нь (4) ба (1) шугамуудын огтлолцлын үр дүнд үүссэн тул түүний координатууд нь эдгээр шулуунуудын тэгшитгэлийг хангана.
.

Тэгшитгэлийн системийг шийдсэний дараа бид дараахь зүйлийг авна: x 1 = 3.3333, x 2 = 0.

Зорилгын функцийн хамгийн бага утгыг хэрхэн олох вэ: .

Ингээд авч үзье зорилтот функцдаалгавар.

F = 0 функцийн утгад тохирох шулуун шугамыг байгуулъя: F = 2x 1 +3x 2 = 0. Зорилгын функцийн коэффициентуудаас бүрдэх градиент вектор нь F(X)-ийн хамгийн их байх чиглэлийг заана. Векторын эхлэл нь цэг (0; 0), төгсгөл нь (2; 3) цэг юм. Бид энэ шулуун шугамыг зэрэгцээ байдлаар шилжүүлнэ. Бид хамгийн дээд шийдлийг сонирхож байгаа тул шулуун шугамыг заасан талбайн сүүлчийн хүрэх хүртэл шилжүүлнэ. График дээр энэ шулуун шугамыг тасархай шугамаар зааж өгсөн болно.

Чигээрээ
бүсийг B цэг дээр огтолно. В цэг нь (2) ба (3) шугамын огтлолцлын үр дүнд үүссэн тул түүний координат нь эдгээр шулуунуудын тэгшитгэлийг хангана.

.

Зорилгын функцийн хамгийн их утгыг хэрхэн олох вэ: .

Хариулт:
Тэгээд
.

2 . Шугаман програмчлалын бодлогыг симплекс аргыг ашиглан шийд.

.

Шийдэл

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

Зорилгын функцийн хамгийн бага утгыг тодорхойлъё
дараах нөхцлөөр - хязгаарлалт:
.

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

1-р утгын тэгш бус байдалд (≥) бид үндсэн хувьсагчийг оруулав x 3 хасах тэмдэгтэй. Утгын 2-р тэгш бус байдалд (≤) бид үндсэн хувьсагчийг оруулав x 4 . Утгын 3-р тэгш бус байдалд (≤) бид үндсэн хувьсагч x 5-ийг оруулав.

Хиймэл хувьсагчдыг танилцуулъя : 1-р тэгшитгэлд бид хувьсагчийг оруулдаг x 6 ;

Асуудлыг хамгийн бага хэмжээнд байлгахын тулд бид зорилгын функцийг дараах байдлаар бичнэ: .

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

Үүссэн суурийг хиймэл, шийдлийн аргыг хиймэл суурь гэж нэрлэдэг.

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

Тэгшитгэлээс бид хиймэл хувьсагчдыг илэрхийлдэг: x 6 = 4-x 1 -x 2 +x 3, бид үүнийг зорилгын функцэд орлуулна: эсвэл.

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

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

Чөлөөт хувьсагчдыг 0-тэй тэнцүү гэж үзвэл эхнийхийг олж авна лавлагаа төлөвлөгөө:

X1 = (0,0,0,2,10,4)

Үндсэн шийдэл нь сөрөг биш бол зөвшөөрөгдөх гэж нэрлэдэг.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Индексийн мөрөнд эерэг коэффициентүүд байгаа тул одоогийн жишиг төлөвлөгөө нь оновчтой биш юм. Тэргүүлэх баганын хувьд бид x 2 хувьсагчтай тохирох баганыг сонгоно, учир нь энэ нь хамгийн том коэффициент юм. Утгыг тооцож үзье Д би Тэдгээрээс бид хамгийн жижигийг нь сонгоно: min(4: 1, 2: 2, 10: 2) = 1.

Тиймээс 2-р мөр нь тэргүүлэгч юм.

Шийдвэрлэх элемент нь (2)-тай тэнцүү бөгөөд тэргүүлэх багана ба тэргүүлэх эгнээний огтлолцол дээр байрладаг.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Бид симплекс хүснэгтийн дараагийн хэсгийг бүрдүүлдэг. 1-р төлөвлөгөөнд x 4 хувьсагчийн оронд x 2 хувьсагч багтана.

1-р төлөвлөгөөний x 2 хувьсагчтай харгалзах мөрийг 0-р төлөвлөгөөний x 4 мөрийн бүх элементүүдийг RE = 2 шийдвэрлэх элементээр хувааснаар гарна. Шийдвэрлэх элементийн оронд бид 1-ийг авна. x 2 баганын үлдсэн нүдэнд бид тэг бичнэ.

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

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 М

Индексийн эгнээнд эерэг коэффициентүүд байгаа тул одоогийн жишиг төлөвлөгөө нь оновчтой биш юм. Тэргүүлэх баганын хувьд бид x 1 хувьсагчтай тохирох баганыг сонгоно, учир нь энэ нь хамгийн том коэффициент юм. Утгыг тооцож үзье Д бихуваах коэффициент болгон мөрөөр: Тэдгээрээс бид хамгийн жижигийг нь сонгоно: мин (3: 1 1/2, -, 8: 2) = 2.

Тиймээс 1-р эгнээ нь тэргүүлэх эгнээнд ордог.

Шийдвэрлэх элемент нь (1 1/2) -тай тэнцүү бөгөөд тэргүүлэх багана ба тэргүүлэх эгнээний огтлолцол дээр байрладаг.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 М

Бид симплекс хүснэгтийн дараагийн хэсгийг бүрдүүлдэг. 2-р төлөвлөгөөнд x 6 хувьсагчийн оронд x 1 хувьсагч орно.

Бид шинэ симплекс хүснэгтийг авах болно:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

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

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

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

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

Хамгийн оновчтой төлөвлөгөөг дараах байдлаар бичиж болно: x 1 = 2, x 2 = 2:.

Хариулт:
,
.

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

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

Шийдэл

Асуудлыг шийдвэрлэхэд шаардлагатай бөгөөд хангалттай нөхцөлийг шалгацгаая.

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

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

Анхны өгөгдлийг түгээлтийн хүснэгтэд оруулъя.

Хэрэгцээ

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

Төлөвлөгөөг зүүн дээд булангаас бөглөж эхэлнэ.

Шаардлагатай элемент нь 4. Энэ элементийн хувьд бараа материал 300, шаардлага 250. Хамгийн бага нь 250 тул хасна: .

			300 - 250 = 50
250 - 250 = 0

Шаардлагатай элемент нь 2-той тэнцүү. Энэ элементийн хувьд бараа материал 50, шаардлага 400. Хамгийн бага нь 50 байх тул үүнийг хасна: .

			50 - 50 = 0
	400 - 50 = 350

Шаардлагатай элемент нь 5. Энэ элементийн хувьд бараа материал 300, шаардлага 350. Хамгийн бага нь 300 байх тул үүнийг хасна.

			300 - 300 = 0
	350 - 300 = 50

Шаардлагатай элемент нь 3. Энэ элементийн хувьд бараа материал 200, шаардлага 50. Хамгийн бага нь 50 байх тул бид үүнийг хасна.

			200 - 50 = 150
	50 - 50 = 0

Шаардлагатай элемент нь 6. Энэ элементийн хувьд бараа материал 150, шаардлага 150. Хамгийн бага нь 150 байх тул үүнийг хасна.

			150 - 150 = 0
		150 - 150 = 0

Хэрэгцээ

Лабораторийн ажил No1. Шугаман програмчлалын бодлого бодох

Ажлын зорилгоГрафик, симплекс, Excel-ийн аргуудыг ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх чадварыг олж авах.

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

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

Жишээ. Зорилгын функцийн хамгийн их утгыг ол Л=2x 1 +2xӨгөгдсөн хязгаарлалтын дагуу 2

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

л 1: 3x 1 -2x 2 +6=0,

л 2: 3x 1 +x 2 -3=0,

л 3:x 1 -3=0.

ДХАМТ

2 0 1 3 X 1

(л 1) (л 3)

Чигээрээ л 1 нь онгоцыг хуваана XТУХАЙ цагтхоёр хагас хавтгайд хуваах ба үүнээс та системийн (3) эхний тэгш бус байдлыг хангах нэгийг сонгох хэрэгтэй. Үүнийг хийхийн тулд t-г авч үзье. ТУХАЙ(0; 0) ба тэгш бус байдалд орлуулна. Хэрэв энэ нь үнэн бол та хагас хавтгайг гэж нэрлэгддэг шулуун шугамаас сүүдэрлэх хэрэгтэй. ТУХАЙ(0; 0). Шулуун шугамтай ижил зүйлийг хий. л 2 ба л 3. Тэгш бус байдлын шийдлийн муж (3) нь олон өнцөгт юм ABCД. Хавтгай дээрх цэг бүрийн хувьд функц Лтогтмол утгыг авдаг Л=Л 1 . Одоогийн бүх цэгүүдийн багц нь шулуун шугам юм Л=в 1 x 1 +в 2 x 2 (бидний тохиолдолд Л=2x 1 +2x 2), векторт перпендикуляр ХАМТ(-тай 1 ;-тай 2) (ХАМТ(2; 2)), гарал үүсэлтэй. Хэрэв энэ шугамыг векторын эерэг чиглэлд шилжүүлбэл -тай, дараа нь зорилгын функц Лнэмэгдэх болно, эс бөгөөс буурах болно. Тиймээс манай тохиолдолд олон өнцөгтөөс гарах шулуун шугам ABCДшийдвэрүүд гэгчээр дамжих болно IN(3; 7.5), тиймээс орно. INзорилгын функц нь хамгийн их утгыг авдаг, өөрөөр хэлбэл. Лхамгийн их =2ּ3+2ּ7.5=21. Үүний нэгэн адил функцийн авах хамгийн бага утга нь тодорхойлогддог Д(1; 0) ба Лмин =2ּ1+2ּ0=2.

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

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

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

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

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

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

6. Шийдлийг сайжруулахын тулд нэг симплекс хүснэгтээс нөгөөд шилжих шаардлагатай. Үүнийг хийхийн тулд өмнөх хүснэгтээс хамгийн их бодлого дахь хүснэгтийн сүүлийн эгнээний хамгийн бага сөрөг элемент, хамгийн бага бодлогын хамгийн том эерэг коэффициенттэй тохирох гол баганыг ол. Дараа нь чөлөөт нэр томъёоны гол баганын харгалзах эерэг элементүүдийн хамгийн бага харьцаатай тохирох гол мөр олдоно. Түлхүүр багана ба гол мөрний огтлолцол дээр гол элемент байна.

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

8. Симплекс хүснэгтийн хувиргалтыг оновчтой төлөвлөгөө гартал гүйцэтгэнэ.

Жишээ. Функцийн хамгийн их утгыг ол
, хэрэв хувьсагч
хязгаарлалтын тогтолцоог хангах:

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

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

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

2. Эхний хүснэгтийн шийдвэрлэх элементийг дараах байдлаар ол. Сүүлийн эгнээний элементүүдээс бид хамгийн том сөрөг коэффициентийг (энэ нь -3) сонгож, хоёр дахь баганыг шийдвэрлэх гэж авна. Хэрэв баганын бүх коэффициент эерэг биш байвал
.

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

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

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

.

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

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

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

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

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

Excel ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх нь дараах байдлаар явагдана.

Шугаман програмчлалын асуудлыг шийдэхийн тулд Шийдэл хайх нэмэлт хэрэгслийг ашиглана уу. Эхлээд та энэ нэмэлт нь Анализ бүлгийн Мэдээллийн таб дээр байгаа эсэхийг шалгах хэрэгтэй (2003 оны "Хэрэгслүүд" хэсгийг үзнэ үү). Хэрэв Шийдэл олох команд эсвэл Шинжилгээний бүлэг байхгүй бол та энэ нэмэлтийг татаж авах ёстой.

Үүнийг хийхийн тулд Microsoft Office File (2010) дээр дараад Excel Options товчийг дарна уу. Гарч ирэх Excel Options цонхноос зүүн талд байгаа Нэмэлтүүдийг сонгоно уу. Цонхны баруун талд "Хяналтын" талбарын утгыг Excel-ийн нэмэлт хэрэгсэл болгон тохируулах ёстой бөгөөд энэ талбарын хажууд байрлах "Явах" товчийг дарна уу. Нэмэлт хэрэгслүүдийн цонхонд Шийдэл олох гэсний хажууд байгаа нүдийг сонгоод OK дарна уу. Дараа нь та суулгасан Search for Solutions нэмэлттэй ажиллах боломжтой.

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

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

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

Дараа нь та шийдэл хайх нэмэлт хэрэгслийг ашиглах хэрэгтэй. Өгөгдлийн табын Анализ бүлгийн Шийдэл олох хэсгийг сонгоно уу. Шийдэл хайх харилцах цонх гарч ирэх бөгөөд үүнийг дараах байдлаар бөглөх ёстой.

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

2) "Хувьсах нүдийг өөрчлөх" талбарт өөрчлөх нүднүүдийг оруулна уу. Дараагийн талбарт "Хязгаарлалтын дагуу" "Нэмэх" товчийг ашиглан заасан хязгаарлалтыг оруулна уу. Гарч ирэх цонхонд хязгаарлалтын системийн томьёог агуулсан нүднүүдийг оруулаад хязгаарлалтын тэмдэг болон хязгаарлалтын утгыг (чөлөөт коэффициент) сонгоно.

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

Жишээ. Excel-ийн шийдлийн нэмэлтийг ашиглан шугаман програмчлалын асуудлыг шийд: функцийн хамгийн их утгыг ол
хязгаарлалт дор

,

;

,
.

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

Бид зорилгын функц болон хязгаарлалтын системийн хамаарлыг танилцуулж байна. Үүнийг хийхийн тулд C2 нүдэнд =SUMPRODUCT(A2:B2;A3:B3) томъёог оруулна. С4 ба С5 нүдэнд тус тус томъёо нь: =ДҮГНЭЛТ(A2:B2,A4:B4) ба =ДҮГНЭЛТ(A2:B2,A5:B5). Үүний үр дүнд бид ширээ авдаг.

"Шийдвэр хайх" командыг ажиллуулаад дараах байдлаар гарч ирэх Шийдэл хайх цонхыг бөглөнө үү. "Зориулалтын функцийг оновчтой болгох" талбарт C2 нүдийг оруулна уу. Зорилтот эсийн утгыг оновчтой болгох "Хамгийн дээд"-ийг сонгоно уу.

"Хувьсагчийн нүдийг өөрчлөх" талбарт A2:B2 өөрчлөгдөж буй нүднүүдийг оруулна. "Хязгаарлалтын дагуу" талбарт "Нэмэх" товчийг ашиглан заасан хязгаарлалтыг оруулна уу. Нүдний лавлагаа $C$4:$C$5 Хязгаарлалтын лавлагаа =$D$4:$D$5 тэдгээрийн хоорондох тэмдэг<= затем кнопку «ОК».

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

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

“Шийдлийн хайлтын үр дүн” харилцах цонхонд x1=0.75, x2=0.75, F=1.5 - зорилгын функцийн хамгийн их утгатай тэнцүү үр дүнг хадгална.

Бие даасан ажилд зориулсан даалгавар

Дасгал 1.График, симплекс аргууд болон Excel хэрэгслүүдийг ашиглан функцийн хамгийн их ба хамгийн бага утгыг олоорой Ф(x) өгөгдсөн хязгаарлалтын тогтолцооны дагуу.

1. Ф(x)=10x 1 +5x 2 2. Ф(x)=3x 1 -2x 2

3. Ф(x)=3x 1 +5x 2 4. Ф(x)=3x 1 +3x 2

5. Ф(x)=4x 1 -3x 2 6. Ф(x)=2x 1 -x 2

7. Ф(x)=-2x 1 +4x 2 8. Ф(x)=4x 1 -3x 2

9. Ф(x)=5x 1 +10x 2 10. Ф(x)=2x 1 +x 2

11. Ф(x)=x 1 +x 2 12. Ф(x)=3x 1 +x 2

13. Ф(x)=4x 1 +5x 2 14. Ф(x)=3x 1 +2x 2

15. Ф(x)=-x 1 -x 2 16. Ф(x)=-3x 1 -5x 2

17. Ф(x)=2x 1 +3x 2 18. Ф(x)=4x 1 +3x 2

19. Ф(x)=-3x 1 -2x 2 20. Ф(x)=-3x 1 +4x 2

21. Ф(x)=5x 1 -2x 2 22. Ф(x)=-2x 1 +3x 3

23. Ф(x)=2x 1 +3x 2 24. Ф(x)=4x 1 +3x 2

25. Ф(x)=-3x 1 -2x 2 26. Ф(x)=-3x 1 +4x 2

27. Ф(x)=-2x 1 +4x 2 28. Ф(x)=4x 1 -3x 2

29. Ф(x)=-x 1 -x 2 30. Ф(x)=-3x 1 -5x 2

Хяналтын асуултууд.

1. Шугаман програмчлалын бодлого гэдэг ямар бодлого вэ?

2. Шугаман програмчлалын бодлогын жишээг өг.

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

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

5. Excel ашиглан шугаман програмчлалын бодлого бодох алгоритмыг тайлбарла.

Холбооны боловсролын агентлаг

Улсын төсвийн боловсролын байгууллага

дээд мэргэжлийн боловсрол

Омскийн улсын техникийн их сургууль

ТООЦОО, ГРАФИКИЙН АЖИЛ

сахилга батаар"ХЯНАЛТЫН ОНОВЧТОЙ ОНОЛ »

сэдвээр"ОНОВЧЛОЛЫН АРГА, ҮЙЛ АЖИЛЛАГААНЫ СУДАЛГАА »

сонголт 7

Дууссан:

захидал харилцааны оюутан

4-р курсын бүлэг ZA-419

Бүтэн нэр: Кужелев С.А.

Шалгасан:

Девятерикова М.В.

Омск - 2012
^

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

7) 7x 1 + 6x 2 → хамгийн их 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Алхам 1: Боломжит бүсийг байгуулах

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

Загварын эхний хязгаарлалт нь хэлбэртэй байна . Тэнд байгаа ≤ тэмдгийг = тэмдгээр орлуулснаар бид тэгшитгэлийг олж авна . Зураг дээр. 1.1 Энэ нь хавтгайг хоёр хагас хавтгайд хуваадаг шулуун шугамыг (1) тодорхойлдог бөгөөд энэ тохиолдолд шугамын дээгүүр ба доор байна. Аль нь тэгш бус байдлыг хангахыг сонгох , өгөгдсөн шулуун дээр ороогүй дурын цэгийн координатыг орлуулна (жишээлбэл, эх X 1 = 0, X 2 = 0). Бид зөв илэрхийлэл (20 0 + 6 0 = 0 ≤15) олж авсан тул координатын гарал үүслийг агуулсан хагас хавтгай (сумаар тэмдэглэгдсэн) тэгш бус байдлыг хангаж байна. Үгүй бол өөр хагас онгоц.

Бид асуудлын үлдсэн хязгаарлалттай ижил төстэй байдлаар ажиллана. Бүх баригдсан хагас хавтгайн эхний квадрат хэлбэрүүдтэй огтлолцол A B C D(1-р зургийг үз). Энэ бол асуудлын боломжтой талбар юм.

Алхам 2. Түвшингийн шугам зурах Түвшингийн шугам Зорилгын функц нь тогтмол утгыг авах хавтгай дахь цэгүүдийн багц юм. Ийм олонлогийг тэгшитгэлээр өгөгдсөн е ( x) = const. Жишээ нь: const = 0 ба түвшинд шугам зур е ( x) = 0, өөрөөр хэлбэл. манай тохиолдолд шулуун шугам 7 x 1 + 6x 2 = 0.

Энэ шугам нь эхийг дайран өнгөрч, векторт перпендикуляр байна. Энэ вектор нь (0,0) цэг дээрх зорилгын функцийн градиент юм. Функцийн градиент нь тухайн цэг дэх өгөгдсөн функцийн хэсэгчилсэн деривативуудын утгын вектор юм. LP асуудлын хувьд зорилгын функцийн хэсэгчилсэн деривативууд нь коэффициентүүдтэй тэнцүү байна Cби, j = 1 , ..., n.

Градиент нь функцийн хамгийн хурдан өсөлтийн чиглэлийг харуулдаг. Зорилгын функцын түвшний шугамыг хөдөлгөж байна е ( x) = const. градиентийн чиглэлд перпендикуляр, бид бүстэй огтлолцох сүүлчийн цэгийг олдог. Манай тохиолдолд энэ нь D цэг бөгөөд энэ нь зорилгын функцийн хамгийн их цэг байх болно (2-р зургийг үз).

Энэ нь (2) ба (3) шугамын огтлолцол дээр байрладаг (1-р зургийг үз) ба оновчтой шийдлийг зааж өгдөг.

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

^ Алхам 3. Зорилгын функцийн хамгийн их (хамгийн бага) цэгийн координат ба оновчтой утгыг тодорхойлох

С цэгийн координатыг олохын тулд шулуун шугамд тохирох тэгшитгэлээс бүрдэх системийг шийдэх шаардлагатай (энэ тохиолдолд тэгшитгэл 2 ба 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Бид оновчтой шийдлийг авна = 1.33.

^ Зорилгын функцийн оновчтой утга е * = е (X*) = 7 * 0 + 6 * 1,33 = 7,8