СЭДЭВ: Шугаман ПРОГРАМЧЛАЛ

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

Анхаар!

Энэ бол 2073 тоот ажлын ТУРШИЛТЫН ХУВИЛБАР бөгөөд анхны үнэ нь 200 рубль юм. онд зохион бүтээсэн Microsoft програмҮг.

Төлбөр. Харилцагчид.

Сонголт 7. Хамгийн их ба хамгийн бага утгыг олшугаман функцФ = 2х 1 - 2 х 2хязгаарлалттай: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1.2.

Шийдэл:

Тэгш бус байдлын тэмдгүүдийг тэгш байдлын тэмдгээр нөхцлөөр сольсноор бид x1 + x2 = 4 тэгшитгэлийн системийг олж авна;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Эдгээр тэгшитгэлийг ашиглан шулуун шугамуудыг байгуулъя, дараа нь тэгш бус байдлын тэмдгүүдийн дагуу бид хагас хавтгайг сонгож, тэдгээрийн нийтлэг хэсгийг - ODR-ийн зөвшөөрөгдөх шийдлийн муж - дөрвөлжин MNPQ-г авна.

Функцийн хамгийн бага утга

tions - M(2; 2) цэг дээр

Ф мин = 2·2 - 2·2 = 0.

Хамгийн их утга нь N цэг дээр хүрсэн (10; 0),

Ф max = 2·10 - 2·0 = 20.

Сонголт 8. Хамгийн их ба хамгийн бага утгыг ол

шугаман функц Ф = x 1 + x 2

хязгаарлалттай: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1.2.

Шийдэл:

Тэгш бус байдлын тэмдгүүдийг тэгш байдлын тэмдгээр нөхцлөөр сольсноор бид x1 - 4 x2 = 4 тэгшитгэлийн системийг олж авна;

3 x1 - x2 = 0;

Эдгээр тэгшитгэлийг ашиглан шулуун шугамуудыг байгуулъя, дараа нь тэгш бус байдлын тэмдгүүдийн дагуу бид хагас хавтгайг сонгож, тэдгээрийн нийтлэг хэсгийг - ODR-ийн зөвшөөрөгдөх шийдлийн муж - хязгааргүй MNPQ олон өнцөгтийг олж авна.

Функцийн хамгийн бага утга

Жишээ нь, шууд NP дээр

P(4; 0) цэг дээр

Ф мин = 4 + 0 = 4.

ODR нь дээрээс хязгаарлагдахгүй тул Ф max = + ∞ байна.

Сонголт 10. Хамгийн их ба хамгийн бага утгыг ол

шугаман функц Ф = 2 x 1 - 3 x 2

хязгаарлалттай: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1.2.

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

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Эдгээр тэгшитгэлүүдийг ашиглан шулуун шугамуудыг байгуулъя, дараа нь тэгш бус байдлын тэмдгүүдийн дагуу хагас хавтгайг сонгоод тэдгээрийн нийтлэг хэсэг - ODR-ийн зөвшөөрөгдөх шийдлийн муж - MNPQRS олон өнцөгтийг олъё.

Г(2; -3) векторыг байгуулж координатын эхийг зуръя түвшний шугам- Чигээрээ.

Бид түвшний шугамыг чиглэлд шилжүүлж, Ф-ийн утга нэмэгддэг. S(7; 0) цэг дээр зорилгын функц хамгийн ихдээ хүрнэ Ф max =2·7–3·0= = 14. Бид түвшний шугамыг чиглэлд шилжүүлж, Ф-ийн утга буурна. Функцийн хамгийн бага утга нь N(0; 5) цэг дээр байна.

Ф мин = 2·0 – 3·5 = –15.

ДААЛГАВАР 2.Б. Шугаман програмчлалын асуудлыг шийдвэрлэх

аналитик симплекс арга

Сонголт 7. Зорилгын функцийг багасгах Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

хязгаарлалттай: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Шийдэл:

Үл мэдэгдэх тоо n=6, тэгшитгэлийн тоо m=3. Иймд r = n-m = 3 үл мэдэгдэхийг чөлөөтэй гэж авч болно. x 1, x 3, x 6-г сонгоцгооё.

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

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

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

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

x 1 = x 3 = x 6 = 0 гэж үзье, үндсэн хувьсагчид x 2 = 2 утгыг авна; x 4 = 9; x 5 = 6, өөрөөр хэлбэл, эхний боломжтой шийдэл (0; 2; 0; 9; 6; 0), зорилгын функц Ф 1 = 13.

X 3 ба x 6 хувьсагч нь сөрөг коэффициент бүхий зорилгын функцэд багтдаг тул тэдгээрийн утга нэмэгдэх тусам Ф-ийн утга буурах болно. Жишээ нь x 6-г авч үзье. Системийн 1-р тэгшитгэлээс (*) харахад x 6-ийн утгыг x 6 = 1 хүртэл нэмэгдүүлэх боломжтой (х 2 ³ 0 байхад). Энэ тохиолдолд x 1 ба x 3 нь тэгтэй тэнцүү хэвээр байна. Одоо бид x 4, x 5, x 6-г үндсэн хувьсагчаар, x 1, x 2, x 3-ыг чөлөөт хувьсагчаар авч байна. Шинэ үндсэн хувьсагчдыг шинэ чөлөөт хувьсагчаар илэрхийлье. Бид авдаг

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Чөлөөт хувьсагчдад тэг утгыг оноож үзье, өөрөөр хэлбэл x 1 = x 2 = x 3 = 0, харин x 6 = 1, x 4 = 3, x 5 = 4, өөрөөр хэлбэл гурав дахь боломжит шийдэл (0) ; 0; 0; 3; 4; 1). Энэ тохиолдолд Ф 3 = 6 байна.

Х 3 хувьсагч нь сөрөг коэффициент бүхий зорилгын функцэд багтсан тул тэг утгатай харьцуулахад x 3-ийн өсөлт нь F-ийн бууралтад хүргэнэ. 2-р тэгшитгэлээс x 3 нь 1/4 болж нэмэгдэх нь тодорхой байна. , 3-р тэгшитгэлээс - 2/3 хүртэл. Хоёр дахь тэгшитгэл нь илүү чухал юм. x 3 хувьсагчийг үндсэн тоонд, x 4-ийг чөлөөт тоонд хөрвүүлье.

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

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Зорилгын функц нь хэлбэрийг авна

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

X 1 ба x 2 хувьсагч нь сөрөг коэффициент бүхий зорилгын функцэд багтдаг тул тэдгээрийн утга нэмэгдэх тусам Ф-ийн утга буурах болно. Жишээ нь x 2-ыг авч үзье. Системийн 2-р тэгшитгэлээс харахад x 2-ийн утгыг x 2 = 5 хүртэл нэмэгдүүлэх боломжтой (х 5 ³ 0 байхад). Энэ тохиолдолд x 1 ба x 4 нь тэг хэвээр үлдэнэ, бусад хувьсагчдын утгууд x 3 = 3/2-тэй тэнцүү байна; x 5 = 0, x 6 = 3/2, өөрөөр хэлбэл дөрөв дэх боломжтой шийдэл (0; 5; 3/2; 0; 0; 3/2). Энэ тохиолдолд Ф 4 = 5/4.

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

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Зорилгын функц нь хэлбэрийг авна

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

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

Өөрөөр хэлбэл, Ф мин = - 5-ийн хамгийн бага утга, хамгийн сүүлийн боломжит шийдэл (0; 5; 3/2; 0; 0; 3/2) оновчтой байна.

Хувилбар 8. Зорилгын функцийг Ф = 4 x 5 + 2 x 6 болгон ихэсгэ

хязгаарлалттай: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Шийдэл:

Тэгшитгэлийн тоо 4, үл мэдэгдэх тоо 6. Иймд r = n – m = 6 – 4 = 2 хувьсагчийг чөлөөт хувьсагчаар, 4 хувьсагчийг үндсэн хувьсагчаар сонгож болно. Бид x 5 ба x 6-г үнэгүй, x 1 , x 2 , x 3 , x 4-ийг үндсэн гэж сонгоно. Үндсэн хувьсагчдыг чөлөөт хувьсагчаар илэрхийлж, тэгшитгэлийн системийг нэгж суурь болгон бууруулъя

x 1 = 12 - x 5 - x 6;

x 2 = 30 - 5 x 5 + x 6;

x 3 = 6 - x 5 + 2 x 6;

x 4 = 9 - 3/2 x 5 + x 6;

Бид зорилгын функцийг Ф = 4 x 5 + 2 x 6 хэлбэрээр бичнэ. x 5 = x 6 = 0 чөлөөт хувьсагчдад тэг утгыг оноож үзье. Энэ тохиолдолд үндсэн хувьсагчид x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 утгуудыг авна. , өөрөөр хэлбэл, бид эхний боломжтой шийдлийг (12, 30, 6, 9, 0,) болон Ф 1 = 0 авна.

Чөлөөт хувьсагч хоёулаа эерэг коэффициентээр зорилгын функцэд ордог, өөрөөр хэлбэл F-ийг цаашид нэмэгдүүлэх боломжтой.Жишээ нь x 6-г үндсэн тоо болгон хөрвүүлье. (1) тэгшитгэлээс x 5 = 12 үед x 1 = 0, (2) ÷ (4) x 6-д эерэг коэффициентүүд орсон нь тодорхой байна. Шинэ суурь руу шилжье: үндсэн хувьсагчид - x 6, x 2, x 3, x 4, free - x 1, x 5. Шинэ үндсэн хувьсагчдыг шинэ чөлөөт хэлбэрээр илэрхийлье.

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5;

x 4 = 21 - x 1 - 5/2 x 5;

Зорилгын функц нь Ф = 24 - 2 x 1 + 2 x 5 хэлбэртэй байна;

x 1 = x 5 = 0 чөлөөт хувьсагчдад тэг утгыг оноож үзье. Энэ тохиолдолд үндсэн хувьсагчид x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 утгуудыг авна. , өөрөөр хэлбэл бид хоёр дахь боломжит шийдлийг (0, 42, 30, 21, 0, 12) олж авна, Ф 2 = 24.

Зорилтот функц x 5 нь эерэг коэффициенттэй, өөрөөр хэлбэл F-ийг цаашид нэмэгдүүлэх боломжтой. Шинэ суурь руу шилжье: үндсэн хувьсагчид - x 6, x 5, x 3, x 4, free - x 1 , x 2. Шинэ үндсэн хувьсагчдыг шинэ үнэгүй хэлбэрээр илэрхийлье

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2;

x 3 = 9 - 3/2 x 1 + 1/2 x 2;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5;

Зорилгын функц нь Ф = 38 – 7/2 x 1 – 1/3 x 2 хэлбэртэй байна;

x 1 = x 2 = 0 чөлөөт хувьсагчдад тэг утгыг оноож үзье. Энэ тохиолдолд үндсэн хувьсагчид x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 утгуудыг авна. /2, өөрөөр хэлбэл, бид X 3 = (0, 0, 9, 7/2, 7, 5) ба Ф 3 = 38 гэсэн гуравдах боломжтой шийдлийг олж авна.

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

Тиймээс хамгийн сүүлийн боломжит шийдэл нь оновчтой, өөрөөр хэлбэл X opt = (0, 0, 9, 7/2, 7, 5) ба Ф max = 38 байна.

Хувилбар 10. Зориулалтын функцийг Ф = x 2 + x 3 хамгийн их болго

хязгаарлалттай: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Шийдэл:

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

x 2 ба x 3-ыг чөлөөт хувьсагч гэж авъя.Тэгвэл үндсэн хувьсагч нь x 1 ба x 2 байх бөгөөд бид үүнийг чөлөөт хэлбэрээр илэрхийлэх болно.

x 1 = 1 + x 2 - x 3; (*)

x 4 = 2 - x 2 + 2 x 3;

Зорилгын функц нь аль хэдийн x 2 ба x 3, өөрөөр хэлбэл Ф = x 2 + x 3-ээр илэрхийлэгдсэн.

x 2 =0 ба x 3 =0-ийн хувьд үндсэн хувьсагчид x 1 = 1, x 4 = 2-тэй тэнцүү байна.

Бидэнд Ф 1 = 0-тэй X 1 = (1, 0, 0, 2) эхний боломжтой шийдэл байна.

Ф-ийн өсөлт нь жишээлбэл, эерэг коэффициент бүхий Ф-ийн илэрхийлэлд орсон x 3-ийн утгыг нэмэгдүүлэх замаар боломжтой (x 2 нь тэгтэй тэнцүү хэвээр байна). Системийн эхний тэгшитгэл (*) нь x 3-ийг 1 хүртэл нэмэгдүүлэх боломжтойг харуулж байна (х 1 ³0 нөхцөлөөс), өөрөөр хэлбэл энэ тэгшитгэл нь x 3-ийн утгыг нэмэгдүүлэхэд хязгаарлалт тавьдаг. Системийн эхний тэгшитгэл (*) шийдэгдэж байна. Энэ тэгшитгэл дээр үндэслэн бид x 1 ба x 3-ыг сольж, шинэ суурь руу шилжинэ. Одоо үндсэн хувьсагч нь x 3 ба x 4, чөлөөт хувьсагч нь x 1 ба x 2 байх болно. Одоо x 3 ба x 4-ийг x 1 ба x 2-оор илэрхийлье.

Бид авна: x 3 = 1 - x 1 + x 2; (**)

x 4 = 4 - 2 x 1 + x 2;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Чөлөөт хувьсагчдыг тэгтэй тэнцүүлснээр бид хоёр дахь зөвшөөрөгдөх үндсэн шийдлийг олж авна X 2 = (0; 0; 1; 4), Ф 2 = 1.

Х2-ийн өсөлтөөр Ф-ийн өсөлт боломжтой. Сүүлчийн тэгшитгэлийн системээс (**) харахад x 2-ын өсөлт хязгаарлагдмал биш юм. Үүний үр дүнд Ф нь улам их эерэг утгыг авах болно, өөрөөр хэлбэл Ф max = + ¥.

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

ДААЛГАВАР 2.D. Өгөгдсөнтэй давхар бодлого зохио

анхны даалгавар.

Хувилбар 7. Зорилгын функцийг Ф = 2 хамгийн их болго× x 1 - x 4

хязгаарлалттай: x 1 + x 2 = 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Шийдэл:

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

x 1 + x 2 = 20,

x 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

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

F = 20 зорилгын функцийг багасга × y 1 + 5 × y2+8 × y 3

y 1 - y 3 үед ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Сонголт 8. Зориулалтын функцийг Ф = x 2 - x 4 - 3-ийг ихэсгэ× x 5

хязгаарлалттай: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (би = 1, 6)

Шийдэл:

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

Анхны асуудал: Давхар асуудал:

F = C × X max F = B T × Ymin

дээр А × A T дээр X = B × Y ≥ C T

Анхны бодлогод зорилгын функц дэх хувьсагчдын коэффициентүүдийн эгнээний матриц нь C = (0; 1; 0; -1; -3; 0) хэлбэртэй байна.

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

B = 2, A = 0 - 4 1 2 -1 0

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

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

Хос асуудлыг дараах хэлбэрээр бичнэ.

F = y 1 + 2 зорилгын функцийн хамгийн бага утгыг ол × y2+5 × y 3

хязгаарлалт дор y 1 ≥ 0,

2× y 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Сонголт 10. Ф = x 1 + x 2 + x 3 функцийг багасга

хязгаарлалттай: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Шийдэл:

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

Анхны асуудал Хос асуудал

F = C × X мин F = B T × Y макс

дээр А × X ≥ B дээр A T × Ю ≤ С Т

X ≥ 0 Y ≥ 0

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

C = (1; 1; 1), B = 3, A = 6 4 5

Хос бодлогын матрицуудыг олъё

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Хос асуудлыг дараах байдлаар томъёолсон болно.

F = 2y 1 + 3y 2 + 4y 3 зорилгын функцийг хамгийн их болго

хязгаарлалт дор 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y би ≥ 0 (i = 1, 2, 3)

ДААЛГАВАР 2.C. Симплекс хүснэгтийг ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх.

Сонголт 7. Зорилгын функцийг хамгийн их болгох Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

хязгаарлалттай: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Шийдэл:

Хязгаарлалтын системийг каноник хэлбэрт оруулъя

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

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

(2) -аас бид x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6 байна.

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

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Симплекс хүснэгт үүсгэцгээе

I давталтын хүснэгт 1

Үндсэн АС	Эрх чөлөө. АС
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
Ф	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II давталт Хүснэгт 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
Ф	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III давталт Хүснэгт 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
Ф	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV давталт Хүснэгт 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
Ф	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

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

Хариулт: Ф m ax = 149/14,

оновчтой шийдэл (0; 0; 25/14; 37/14; 1/2; 0; 0)

Хувилбар 8. Зорилгын функцийг Ф = 5 x 1 - x 3-ыг багасга

хязгаарлалттай: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Шийдэл:

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

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Тэгшитгэлийн систем ба зорилгын функцийг симплекс хүснэгтэд тохиромжтой хэлбэрээр бичье, өөрөөр хэлбэл x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

Ширээ хийцгээе

I давталтын хүснэгт 1

Үндсэн АС	Эрх чөлөө. АС
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
Ф	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) Ф 1 = 10.

II давталт Хүснэгт 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
Ф	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III давталт Хүснэгт 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
Ф	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

Сүүлийн хүснэгтийн индексийн мөрөнд эерэг тоо байхгүй, өөрөөр хэлбэл зорилгын функцийн илэрхийлэлд бүгд Г i > 0 байна. Бидэнд I тохиолдол байгаа тул сүүлчийн үндсэн шийдэл нь оновчтой байна.

Хариулт: Ф мин = -7/4, оновчтой шийдэл (0; 0; 7/4; 1/2)

********************

Сонголт 10. Зорилгын функцийг багасгах Ф = x 1 + x 2,

хязгаарлалттай: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Шийдэл:

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

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Бид зорилгын функцийг чөлөөт хувьсагчаар илэрхийлж Ф - 3 x 3 +3 x 4 = 3 хэлбэрээр бичнэ.

Ширээ хийцгээе

I давталтын хүснэгт 1

Үндсэн АС	Эрх чөлөө. АС
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
Ф	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

хүснэгт 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
Ф	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

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

Хариулт: Ф мин = 3/2, оновчтой шийдэл (3/2; 0; 0; 1/2; 11/2).

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

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

илүү өндөр Мэргэжлийн боловсрол

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

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

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

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

сонголт 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

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

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

Сонголт 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

Хэрэгцээ

Оршил

Хүний хөгжлийн өнөөгийн үе шат нь эрчим хүчний эрин үеийг компьютерийн шинжлэх ухааны эрин үеээр сольж байгаагаараа онцлог юм. Хүний үйл ажиллагааны бүхий л салбарт шинэ технологи эрчимтэй нэвтэрч байна. Боловсролын хөгжлийг нэн тэргүүнд тавих ёстой мэдээллийн нийгэмд шилжих бодит асуудал байна. Нийгэм дэх мэдлэгийн бүтэц ч өөрчлөгдөж байна. хувьд улам бүр чухал болж байна практик амьдралхувь хүний ​​бүтээлч хөгжилд хувь нэмэр оруулах суурь мэдлэгийг олж авах. Олж авсан мэдлэгийн бүтээлч байдал, түүнийг зорилгодоо нийцүүлэн зохион байгуулах чадвар нь бас чухал юм. Мэдлэгт тулгуурлан шинээр бий болдог мэдээллийн нөөцнийгэм. Шинэ мэдлэгийг бий болгох, эзэмших нь системийн хандлагын хатуу арга зүйд суурилсан байх ёстой бөгөөд үүнд загвар хандлага онцгой байр суурь эзэлдэг. Загварын аргын боломжууд нь ашигласан албан ёсны загварууд болон загварчлалын аргуудыг хэрэгжүүлэх аргын хувьд маш олон янз байдаг. Физик загварчлал нь нэлээд энгийн системүүдийн найдвартай үр дүнд хүрэх боломжийг олгодог.

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

1. Асуудлын тухай мэдэгдэл

хамгийн бага зорилгын функц

Даалгаврын 16-р хувилбарын дагуу шийдлийн олон өнцөгтөөр тодорхойлсон хязгаарлалтын системийн зорилгын функцын минимумыг олох бодлогыг шийд. Уусмалын олон өнцөгтийг 1-р зурагт үзүүлэв.

Зураг 1 - Асуудлын шийдлийн олон өнцөгт

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

Дараах аргуудыг ашиглан асуудлыг шийдвэрлэх шаардлагатай.

LP асуудлыг шийдвэрлэх график арга;

LP асуудлыг шийдвэрлэх алгебрийн арга;

LP асуудлыг шийдвэрлэх энгийн арга;

LP-ийн асуудлын зөвшөөрөгдөх шийдлийг олох арга;

Хос LP асуудлыг шийдэх;

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

Бүхэл тоон LP бодлогуудыг шийдвэрлэх Гоморийн арга;

Boolean LP асуудлыг шийдвэрлэх Balazs арга.

Шийдлийн үр дүнг харьцуулах өөр өөр аргуудажлаас зохих дүгнэлт гаргах.

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

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

Цагаан будаа. 2 LP асуудлын график шийдэл

Хамгийн бага оноо

А1 ба А2 хоёр цэгийг дайран өнгөрөх шулууны тэгшитгэл:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

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

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

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

Зүүн талд хувьсагч, чөлөөт нөхцөл байхаар тэгш бус байдлыг хувирга, баруун талд 0, өөрөөр хэлбэл. руу зүүн талтэгээс их буюу тэнцүү байсан;

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

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

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

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

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

Чөлөөт хувьсагч

Гэгээн эгнээ - нэмэлт иж бүрдэл

Сөрөг бус нөхцөл хангагдсан тул оновчтой шийдлийг оллоо.

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

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

Системийн бүх тэгшитгэлийг дараах хэлбэрт оруулъя.

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

Хүснэгтийн нүд бүрийн дээд буланд тэгшитгэлийн системээс коэффициентүүдийг оруулна;

Бид F мөрөнд хамгийн их эерэг элементийг сонгоно, гэхдээ энэ нь ерөнхий багана байх болно;

Ерөнхий элементийг олохын тулд бид бүх эерэг талуудын харилцааг бий болгодог. 3/3; 9/1;- x3 мөрөнд хамгийн бага харьцаа. Тиймээс - ерөнхий мөр ба =3 - ерөнхий элемент.

Бид =1/=1/3-ийг олно. Бид үүнийг ерөнхий элемент байрладаг нүдний доод буланд оруулдаг;

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

Ерөнхий шугамын дээд буланг сонгох;

Ерөнхий баганын бүх доод буланд бид дээд буланд байгаа утгын үржвэрийг оруулаад гарч ирсэн утгыг сонгоно;

Хүснэгтийн үлдсэн нүдийг сонгосон элементүүдийн бүтээгдэхүүн болгон бөглөнө;

Дараа нь бид ерөнхий багана ба мөрний элементүүдийн нүднүүдийн тэмдэглэгээг сольж байгаа шинэ хүснэгтийг байгуулна (x2 ба x3);

Өмнө нь доод буланд байсан утгууд нь өмнөх ерөнхий мөр, баганын дээд буланд бичигдсэн;

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

4. Зөвшөөрөгдөх шийдлийг олох замаар шугаман програмчлалын асуудлыг шийдвэрлэх

Шугаман алгебрийн тэгшитгэлийн системийг өгье.

Бүх зүйл байгаа гэж бид таамаглаж болно, эс тэгвээс бид харгалзах тэгшитгэлийг -1-ээр үржүүлнэ.

Бид туслах хувьсагчдыг танилцуулж байна:

Бид мөн туслах функцийг танилцуулж байна

Бид хязгаарлалт (2) болон нөхцлийн дагуу системийг багасгах болно.

ЗӨВШӨӨРӨГДӨГ ШИЙДЛИЙГ ОЛОХ ДҮРЭМ: (1) системийн зөвшөөрөгдөх шийдлийг олохын тулд (2) хязгаарлалтын дагуу (3) хэлбэрийг багасгаж, xj-г чөлөөт үл мэдэгдэх, xj-г суурь болгон авна.

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

min f=0, тэгвэл бүх i тэгтэй тэнцүү байх ёстой. Мөн xj-ийн үр дүнд гарсан утгууд нь (1) системийн зөвшөөрөгдөх шийдлийг бүрдүүлнэ.

мин f>0, өөрөөр хэлбэл. анхны систем нь боломжит шийдэлгүй.

Эх сурвалжийн систем:

Өмнөх сэдвийн асуудлын нөхцөлийг ашигласан болно.

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

Анхны асуудлын зөвшөөрөгдөх шийдлийг оллоо: x1 = 3, x2 = 3, F = -12. Боломжит шийдэлд үндэслэн бид симплекс аргыг ашиглан анхны асуудлын оновчтой шийдлийг олох болно. Үүнийг хийхийн тулд бид дээрх хүснэгтээс шинэ симплекс хүснэгтийг барьж, туслах асуудлын зорилтот функц бүхий мөр, мөрийг устгана.

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

6. Хос шугаман програмчлалын бодлого

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

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

Шийдэл: Хязгаарлалтын системийг стандарт хэлбэрт оруулъя:

Үүнтэй холбоотой асуудал нь дараах хэлбэртэй байна.

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

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

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??мин

Хос LP асуудлыг шийдэх анхны симплекс хүснэгтийг байгуулъя.

Симплекс аргын хоёр дахь алхам

Ингээд симплекс аргын 3-р алхамд y2 = -7 /8, y1 = -11/8, Ф = 12 гэсэн үр дүнгээр багасгах бодлогын оновчтой шийдийг олов. -ийн утгыг олохын тулд Давхар асуудлын зорилгын функцийг бид үндсэн болон чөлөөт хувьсагчдын олсон утгыг максимум функц болгон орлуулна.

Фmax = - Фмин = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Шууд болон давхар бодлогын зорилгын функцын утга давхцаж байгаа тул шууд бодлогын шийдэл олдож 12-той тэнцүү байна.

Fmin = Фmax = -12

7. Бүхэл тоон шугаман програмчлалын бодлогыг салбар-ба-хязгаарлалтын аргыг ашиглан шийдвэрлэх

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

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

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

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

Шийдлийн үр дүнд асуудлын оновчтой төлөвлөгөө олдсон: x1 = 9/4, x2 = 5/2, F = -41/4. Энэ шийдэл нь асуудалд тогтоосон бүхэл тооны нөхцөлийг хангахгүй байна. Анхны шийдлийн олон өнцөгтийг 3-р талбайг хасч хоёр хэсэгт хуваая

Өөрчлөгдсөн асуудлын шийдлийн олон өнцөгт

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

Зүүн бүсийн хязгаарлалтын систем

Баруун тал нь С цэгийг илэрхийлнэ.

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

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

Шийдлийн үр дүнд асуудлын оновчтой төлөвлөгөө олдсон: x1 = 3, x2 = 3, F = -12. Энэхүү төлөвлөгөө нь асуудлын хувьсагчид бүхэл тоо байх нөхцөлийг хангасан бөгөөд анхны бүхэл тоон шугаман програмчлалын бодлогын оновчтой лавлагаа төлөвлөгөө болгон хүлээн зөвшөөрч болно. Зөв шийдлийн бүсийг шийдэх нь утгагүй юм. Доорх зурагт бүхэл тоон шугаман програмчлалын бодлогыг мод хэлбэрээр шийдвэрлэх явцыг харуулав.

Гоморийн аргыг ашиглан бүхэл тоон шугаман програмчлалын бодлогыг шийдвэрлэх явц.

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

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

Бүхэл тоон програмчлалын асуудлыг шийдэх аргуудын нэгийг Гомори санал болгосон. Аргын санаа нь тасралтгүй шугаман програмчлалын аргууд, тухайлбал симплекс аргыг ашиглах явдал юм.

1) Симплекс аргыг ашиглан (1), (2) асуудлын шийдлийг тодорхойлж, бүхэл тооны шийдлийн шаардлагыг арилгана; хэрэв шийдэл нь бүхэл тоо болж хувирвал бүхэл тооны асуудлын хүссэн шийдийг мөн олох болно;

2) Үгүй бол, хэрэв зарим координат нь бүхэл тоо биш бол асуудлын үр дүнгийн шийдэл нь бүхэл тооны шийдэл байгаа эсэхийг шалгана (зөвшөөрөгдөх олон өнцөгт дэх бүхэл тоон цэгүүд):

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

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

3) Нэмэлт шугаман хязгаарлалт байгуулахын тулд бутархай чөлөөт гишүүнтэй l-р мөрийг сонгоод нэмэлт хязгаарлалтыг бичнэ үү.

Энд ба нь тус тус коэффициентийн бутархай хэсэг ба чөлөөт

гишүүн. (3) хязгаарлалтад туслах хувьсагчийг оруулъя:

Хязгаарлалт (4)-д багтсан коэффициентүүдийг тодорхойлъё:

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

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

Шийдэл: Шугаман хязгаарлалтын систем ба зорилгын функцийг каноник хэлбэрт оруулъя.

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

Balazs аргыг ашиглан Boolean LP асуудлыг шийдвэрлэх.

Дараах дүрмийг харгалзан Булийн хувьсагчтай бүхэл тоон шугаман програмчлалын бодлогын өөрийн хувилбарыг үүсгэнэ үү: бодлогод дор хаяж 5 хувьсагч, дор хаяж 4 хязгаарлалт, хязгаарлалтын коэффициент болон зорилгын функцийг дур мэдэн сонгосон, гэхдээ ийм тохиолдолд. хязгаарлалтын систем нийцтэй байх арга. Даалгавар бол Balazs алгоритмыг ашиглан Булийн хувьсагчтай LCLP-ийг шийдэж, цогц хайлтын аргыг ашиглан асуудлыг шийдвэрлэхтэй холбоотой тооцооллын нарийн төвөгтэй байдлыг багасгах явдал юм.

Хязгаарлалтын хэрэгжилт

F утга

Шүүлтүүрийн хязгаарлалт:

Тооцооллын хүчин чармайлтын бууралтыг тодорхойлох

Бүрэн хайлтын аргыг ашиглан асуудлыг шийдэх арга нь 6*25=192 тооцоолсон илэрхийлэл юм. Балазын аргыг ашиглан асуудлыг шийдэх арга нь 3*6+(25-3)=47 тооцоолсон илэрхийлэл юм. Бүрэн хайлтын аргыг ашиглан асуудлыг шийдвэрлэхтэй холбоотой тооцооллын нарийн төвөгтэй байдлын нийт бууралт нь:

Дүгнэлт

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

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

Уран зохиол:

1. Лященко I.N. Шугаман ба шугаман бус програмчлал / И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова, Н.З.Шор. - К.: "Ахлах сургууль", 1975, 372 х.

2. "Компьютерийн систем ба сүлжээ" мэргэжлээр суралцаж буй өдрийн болон цагийн ангийн оюутнуудад зориулсан "Хэрэглээний математик" сэдвээр курсын төслийг дуусгах заавар / Эмхэтгэсэн: Балакирева И.А., Скатков А.В. Хэвлэлийн газар, 2003. - 15 х.

3. “Хэрэглээний математик” хичээлийг судлах заавар, “Дэлхийн эрэл хайгуул ба нэг хэмжээст багасгах арга” хэсэг / Comp. А.В.Скатков, И.А.Балакирева, Л.А.Литвинова - Севастополь: СевГТУ хэвлэлийн газар, 2000. - 31 х.

4. "Компьютерийн систем ба сүлжээ" мэргэжлээр суралцаж буй оюутнуудад зориулсан "Хэрэглээний математик" хичээлийг өдрийн болон эчнээ сургалтын "Бүхэл тоон шугаман програмчлалын бодлого шийдвэрлэх" хэсэг / Эмхэтгэсэн: И.А.Балакирева, А.В.Скатков - Севастополь хот. : SevNTU-ийн хэвлэлийн газар, 2000. - 13 х.

5. Акулич И.Л. Жишээ ба бодлого дахь математик програмчлал:

6. Сурах бичиг эдийн засгийн оюутнуудад зориулсан тэтгэмж. мэргэжилтэн. их дээд сургуулиуд.-М.: Дээд. сургууль, 1986.- 319 х., өвчтэй.

7. Андронов С.А. Загварын оновчтой аргууд: Лекцийн текст / SPbSUAP. Санкт-Петербург, 2001. 169 х.: өвчтэй.

Үүнтэй төстэй баримт бичиг

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

курсын ажил, 2012/03/21 нэмэгдсэн


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

туршилт, 2016 оны 04-05-нд нэмэгдсэн


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

курсын ажил, 2008 оны 12-09-нд нэмэгдсэн


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

курсын ажил, 2014/10/31 нэмэгдсэн


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

курсын ажил, 2014/12/17 нэмэгдсэн


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

курсын ажил, 2008 оны 10-13-нд нэмэгдсэн


Шугаман програмчлалын асуудлыг график аргаар шийдвэрлэх, MS Excel программ дээр шалгах. Програм дахь асуудлыг шийдвэрлэх дотоод бүтцийн шинжилгээ. Үйлдвэрлэлийн төлөвлөгөөг оновчтой болгох. Симплекс аргыг ашиглан асуудлыг шийдвэрлэх. Олон сувгийн дарааллын систем.

туршилт, 2012 оны 05-р сарын 02-нд нэмэгдсэн


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

туршилт, 2012 оны 04-р сарын 11-нд нэмэгдсэн


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

курсын ажил, 2012/12/17 нэмэгдсэн


Шугаман програмчлалын асуудлын шийдлийн шинжилгээ. Симплекс хүснэгт ашиглан симплекс арга. Компьютер дээр LP асуудлыг загварчлах, шийдвэрлэх. Асуудлын оновчтой шийдлийн эдийн засгийн тайлбар. Тээврийн асуудлын математик томъёолол.