Үйл ажиллагааны судалгааны үзэл баримтлалын зөв тодорхойлолт нь: Үйл ажиллагааны судалгааны сэдэв, даалгавар

1. AI-ийн үндсэн ойлголтууд

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

IO нь дараах хэсгүүдийг агуулна.

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

2) санамсаргүй үйл явцын онол дээр үндэслэсэн дарааллын онол;

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

Хяналтын тодорхой асуудлыг шийдвэрлэхдээ AI аргыг ашиглах нь дараахь зүйлийг агуулна.

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

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

IO-ийн үндсэн ойлголт, тодорхойлолтууд.

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

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

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

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

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

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

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

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

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

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

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

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

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

Эдийн засаг-математик загвар

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

LP аргуудыг практик асуудлуудад ашигладаг бөгөөд үүнд: 1) олон янзын боломжит шийдлүүдээс хамгийн сайн шийдлийг (оновчтой төлөвлөгөө) сонгох шаардлагатай; 2) шийдлийг зарим хувьсагчийн утгын багц хэлбэрээр илэрхийлж болно; а) асуудлын тодорхой нөхцлөөр боломжит шийдлүүдэд тавьсан хязгаарлалтыг шугаман тэгшитгэл эсвэл тэгш бус байдлын хэлбэрээр томъёолсон; 4) зорилго нь үндсэн хувьсагчдын шугаман функц хэлбэрээр илэрхийлэгдэнэ. Төрөл бүрийн шийдлүүдийг харьцуулах боломжийг олгодог зорилгын функцийн утгууд нь шийдлийн чанарын шалгуур болдог.

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

Загвар үүсгэх ерөнхий схем: I

1) тоон утгыг хуваарилах нь судалж буй үзэгдлийн боломжит төлөвүүдийн аль нэгийг онцгойлон тодорхойлдог тодорхой тооны хувьсах хэмжигдэхүүнийг сонгох;

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

3) сонгосон оновчтой байдлын шалгуурыг зорилгын функц хэлбэрээр тоон илэрхийлэл; I

4) хувьсагчдад тавьсан хязгаарлалтыг биелүүлэхийн тулд зорилгын функцийн экстремумыг олох асуудал болгон асуудлыг математикийн томъёолол.

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

n хувьсагчтай m шугаман тэгшитгэл ба тэгш бус байдлын систем өгөгдсөн

ба шугаман функц

X=(x1,x2,…,xj,…,xn) системийн шийдлийг олох шаардлагатай бөгөөд шугаман функц F нь оновчтой (өөрөөр хэлбэл хамгийн их эсвэл хамгийн бага) утгыг авдаг.

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

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

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

Оновчтой шийдэл (эсвэл оновчтой төлөвлөгөө) LP бодлогын шийдэл нь X=(x1,x2,…,xj,…,xn), (3) нөхцөлийг хангасан хязгаарлалтын систем (1) бөгөөд шугаман функц (2) нь оновчтой утгыг авдаг. (хамгийн их эсвэл хамгийн бага) утга.

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

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

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

4 . Шугаман алгебрийн элементүүд

n хувьсагчтай м шугаман тэгшитгэлийн систем нь хэлбэртэй байна

эсвэл богино хэлбэрээр

n хувьсагчтай м шугаман тэгшитгэлийн системийн дурын m хувьсагч (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

(2.1) системийг m нөхцөлд шийдвэрлэх< n сформулируем утверждение.

Мэдэгдэл 2.1. Хэрэв системийн хувьдмшугаман тэгшитгэлүүдnхувьсагч (м < n) хувьсагчдын коэффициентийн матрицын зэрэглэл нь m-тэй тэнцүү, i.e. Хэрэв үндсэн хувьсагчийн дор хаяж нэг бүлэг байгаа бол энэ систем нь тодорхойгүй бөгөөд үндсэн бус хувьсагчийн дурын багц тус бүр нь системийн нэг шийдэлд тохирно.

Шийдэл(2.1) системийн X=(x1,x2,…,xn) нь зөвхөн сөрөг бус бүрэлдэхүүн хэсгүүдийг агуулж байгаа бол зөвшөөрөгдөх боломжтой гэж нэрлэнэ. Ямар ч j=1,n хувьд xj>=0. Үгүй бол шийдлийг хүчингүй гэж нэрлэдэг.

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

Үндсэн шийдэл n хувьсагчтай м шугаман тэгшитгэлийн системийн бүх n–m бага хувьсагч нь тэгтэй тэнцүү байх шийдэл юм.

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

Гүдгэр цэгүүдийн багц

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

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

Гүдгэр багц нь чухал ач холбогдолтой өмч: Ямар ч тооны гүдгэр олонлогийн огтлолцол (нийтлэг хэсэг) нь гүдгэр олонлог юм.

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

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

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

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

Зураг дээр. 2.4-т олон өнцөгтийн янз бүрийн цэгүүдийн жишээг харуулав: дотоод (цэг M), хил (цэг N) ба булан (A, B, C, D, E цэг). А цэг нь булангийн цэг юм, учир нь бүхэлдээ олон өнцөгт хамаарах аливаа сегментийн хувьд, жишээлбэл, AP сегментийн хувьд энэ нь дотоод биш юм; А цэг нь KL сегментийн дотоод хэсэг боловч энэ сегмент бүхэлдээ олон өнцөгт хамаарахгүй.

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

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

Тэгш бус байдал, тэгшитгэл, тэдгээрийн системийн шийдлийн геометрийн утга

Тэгш бус байдлын шийдлүүдийг авч үзье.

Тайлбар 1. a11x1+a12x2 хоёр хувьсагчтай тэгш бус байдлын шийдлийн багц<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

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

Тэгш бус байдлын системийн шийдлүүдийн багцыг авч үзье.

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

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

Булангийн цэгүүдийн координатууд - олон өнцөгтийн оройнууд нь харгалзах шугамуудын огтлолцох цэгүүдийн координатууд юм.

Тэгш бус байдлын системийн шийдлийн талбайг барих үед бусад тохиолдлууд тохиолдож болно: шийдлийн багц нь гүдгэр олон өнцөгт талбай (Зураг 2.9, а); нэг цэг (Зураг 2.9, b); тэгш бус байдлын систем нийцэхгүй байх үед хоосон олонлог (Зураг 2.9, в).

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

LP асуудлын оновчтой шийдэл

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

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

Дараагийн теорем нь булангийн цэгүүдийг олох аналитик аргад зориулагдсан болно.

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

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

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

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

Хоёр хувьсагчтай стандарт хэлбэрээр асуудлыг авч үзье (П = 2).

Хязгаарлалтын системийн геометрийн дүрсийг олон өнцөгт гэж үзье ABCDE(Зураг 4.1). Энэ олон өнцөгтийн цэгүүдийн дунд F=c1x1+c2x2 шугаман функц хамгийн их (эсвэл хамгийн бага) утгыг авах цэгийг олох шаардлагатай.

гэж нэрлэгддэг зүйлийг авч үзье түвшний шугам шугаман функц Ф, өөрөөр хэлбэл Энэ функц нь ижил тогтмол утгыг авдаг шугам А, өөрөөр хэлбэл Ф = А,эсвэл c1x1+c2x2=a.

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

c1x1+c2x2=a функцийн түвшний шугамын тэгшитгэл нь шулуун шугамын тэгшитгэл юм. Янз бүрийн түвшинд Атүвшний шугамууд зэрэгцээ байна, учир нь тэдгээрийн өнцгийн коэффициентүүд нь зөвхөн c1 ба c2 коэффициентүүдийн хоорондын хамаарлаар тодорхойлогддог тул тэнцүү байна. Тиймээс функцын түвшний шугамууд Ф – Эдгээр нь ихэвчлэн координатын тэнхлэгүүдийн өнцөгт байрладаг өвөрмөц "параллель" юм.

Шугаман функцийн түвшний шугамын чухал шинж чанар нь шугамыг нэг чиглэлд зэрэгцүүлэн шилжүүлэхэд зөвхөн түвшин нэмэгдэж, нөгөө чиглэлд шилжих үед зөвхөн буурдаг. Эхээс гарч буй c=(c1,c2) ​​вектор нь F функцийн хамгийн хурдан өсөх чиглэлийг заана. Шугаман функцийн түвшний шугам нь c=(c1,c2) ​​векторт перпендикуляр байна.

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

1. Уусмалын олон өнцөгтийг байгуул.

2. c=(c1,c2) ​​векторыг байгуулж, эхлээд шугаман функцийн түвшний шугамыг зур. Фжишээлбэл, F=0.

3. F=0 шулууныг c(-c) векторын чиглэлд параллель хөдөлгөөнөөр F хамгийн ихдээ (минимум) хүрэх Amax(Bmin) цэгийг ол.

1. Оновчтой цэг дээр огтлолцох шулуунуудын тэгшитгэлийг хамтран шийдэж координатыг нь ол.

2. Fmax(Fmin)-ийг тооцоол.

Сэтгэгдэл.Хамгийн бага цэг нь шийдлийн олон өнцөгт рүү орох "орох" цэг, хамгийн их цэг нь олон өнцөгтөөс гарах "гарц" цэг юм.

6. Симплекс аргын ерөнхий санаа. Геометрийн тайлбар

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

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

Боломжит шийдлүүдийн мужийг олон өнцөгтөөр илэрхийлье ABCDE. Түүний булангийн цэг гэж үзье Аанхны боломжит суурь шийдэлтэй тохирч байна. Санамсаргүй хайлт хийхэд олон өнцөгтийн таван булангийн цэгт тохирох таван боломжит шийдлийг турших шаардлагатай болно. Гэсэн хэдий ч дээд талын дараа гэдэг нь зурагнаас тодорхой харагдаж байна Ахөрш зэргэлдээ орой руу шилжих нь ашигтай IN,тэгээд хамгийн оновчтой цэг хүртэл ХАМТ.Тавын оронд бид зөвхөн гурван оройгоор дамжиж, шугаман функцийг тогтмол сайжруулав.

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

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

Симплекс аргыг анх 1949 онд Америкийн эрдэмтэн Ж.Данзиг санал болгож байсан бол тэртээ 1939 онд уг аргын санааг Оросын эрдэмтэн Л.В. Канторович.

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

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

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

хамгийн сайн (илүү нарийвчлалтай, муу биш) шийдэлд шилжих дүрэм;

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

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

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

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

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

1. Асуудлын нөхцөл дээр үндэслэн түүний математик загварыг эмхэтгэсэн.

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

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

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

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

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

5. Олдсон анхны тусламжийн төлөвлөгөөг оновчтой эсэхийг шалгана.

a) Хэрэв F эгнээнд сөрөг элемент байхгүй бол (чөлөөт нэр томъёог тооцохгүй) төлөвлөгөө оновчтой байна. Хэрэв тэг байхгүй бол зөвхөн нэг оновчтой төлөвлөгөө байна; хэрэв дор хаяж нэг тэг байгаа бол хязгааргүй тооны оновчтой төлөвлөгөө байдаг;

б) хэрэв F эгнээнд эерэг бус элементүүдийн баганад тохирох дор хаяж нэг сөрөг элемент байвал;

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

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

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

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

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

2) чөлөөт нэр томъёоны баганын элементүүдийн ижил тэмдэгтэй (энгийн харилцаа) шийдвэрлэх баганын харгалзах элементүүдийн харьцааг бүрдүүлэх;

3) симплекс харилцаанаас хамгийн багаг нь сонгоно. Энэ нь идэвхжүүлэх мөрийг тодорхойлно. Жишээлбэл, ийм байг. Р- шугам;

4) шийдвэрлэх багана ба мөрийн огтлолцол дээр шийдвэрлэх элемент олддог. Хэрэв y эгнээний элемент шийдэгдэж байгаа бол симплекс хувиргасны дараа энэ мөрийн чөлөөт гишүүн эерэг болно. Үгүй бол дараагийн алхамд t мөр рүү дахин хандах болно. Хэрэв асуудлыг шийдэх боломжтой бол тодорхой тооны алхмуудын дараа чөлөөт нэр томъёоны баганад сөрөг элемент үлдэхгүй.

8. Урвуу матрицын арга

Дараах хэлбэрийн LP-г авч үзье.

A - хязгаарлалтын матриц;

C=(c1,c2,…,cn)–мөр вектор;

X=(x1,x2,…,xn) – хувьсагч;

баруун талын вектор юм.

Бид бүх тэгшитгэлүүд нь шугаман хамааралгүй гэж үздэг, өөрөөр хэлбэл. зэрэглэл(a)=m. Энэ тохиолдолд суурь нь А матрицын эрэмбийн минор юм. Өөрөөр хэлбэл, |B| гэсэн m дарааллын дор хаяж нэг В дэд матриц байна<>0. В-д харгалзах бүх үл мэдэгдэх зүйлсийг үндсэн гэж нэрлэдэг. Бусад нь бүгд чөлөөтэй.

B ямар нэг суурь байг. Дараа нь А матрицын багануудыг дахин цэгцлэх замаар бид үргэлж А-г A=(B|N) хэлбэрт оруулж болно.

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

Асуудлын (1) аливаа шийдэл нь A*x=b нөхцөлийг хангадаг тул систем дараах хэлбэрийг авна.

Учир нь |B|<>0 бол урвуу матриц байна. Зүүн талаас урвуугаар үржүүлснээр бид дараахь зүйлийг авна.

- нийтлэг шийдвэр.

Үндсэн шийдэл (B суурьтай харьцуулахад) нь нөхцөлийн дагуу олж авсан асуудлын (2) тодорхой шийдэл юм. Дараа нь энэ нь өвөрмөц байдлаар тодорхойлогддог.

Үндсэн шийдэл гэж нэрлэдэг хэрэгжих боломжтой, Хэрэв.

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

Ерөнхий шийдэл нь байгаа бүх шийдлүүдийг агуулдаг. Зорилгын функц рүү буцъя. Бид үндсэн хувьсагчдын өмнө Cb – коэффициентийг, Cn – үлдсэн хэсгийг танилцуулж байна.

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

Мэдэгдэл. Үндсэн шийдлийн оновчтой байдлын шалгуур.

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

Баримт бичиг:Байцгаая. Үндсэн шийдлийг авч үзье, .

Тиймээс үндсэн шийдлийн зорилгын функцийн утга.

Өөр шийдэл байг: (Xb,Xn).

Дараа нь харцгаая

Тиймээс үндсэн шийдэл нь хамгийн мин. Эсрэгээр нь биелэхгүй байг, i.e. байдаг.

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

Энэ нь Xi:Xj чөлөөт хувьсагчтай тохирч, бид утга оноож, суурьт оруулаад, өөр хувьсагч гаргаж аваад түүнийг үнэгүй гэж нэрлэнэ.

Хэрхэн тодорхойлох вэ? Бусад бүх чөлөөт хувьсагч нь 0 хэвээр байна.

Дараа нь ерөнхий шийдэлд, хаана.

Гаргая: - зайлшгүй нөхцөл.

Үндсэн шийдлийг ердийн if гэж нэрлэдэг. Хувьсагч нь сууриас гаралтай. Шинэ шийдлээр зорилгын функц буурдаг, учир нь

Алгоритм:

1.Стандарт хэлбэрээр LP асуудал.

2. Бид шугаман бие даасан тэгшитгэлүүдийг үлдээдэг.

3. |B| байх В матрицыг ол<>0 ба үндсэн шийдэл.

Бид тооцоолно:

хэрэв оновчтой шийдэл байгаа бол энэ нь үндсэн шийдэл юм;

хэрэв, дараа нь бид бүрэлдэхүүн хэсгийг олж, түүнийг нэмж, улмаар өөр шийдлийг олох; – үндсэн хувьсагчийн аль нэг нь =0. Бид энэ хувьсагчийг үндсэнээс хасаад xi-г оруулдаг. Бид B1 суурьтай нэгтгэсэн шинэ суурь B2-г олж авлаа. Дараа нь бид дахин тооцоолно.

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

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

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

Даалгавар. P1 ба P2 хоёр төрлийн бүтээгдэхүүн үйлдвэрлэхэд S1, S2, S3, S4 гэсэн дөрвөн төрлийн нөөцийг ашигладаг. Нөөцийн нөөц, нэгж бүтээгдэхүүн үйлдвэрлэхэд зарцуулсан нөөцийн нэгжийн тоог өгсөн болно. P1 ба P2 үйлдвэрлэлийн нэгжээс авсан ашиг нь мэдэгдэж байна. Борлуулалтаас олох ашиг хамгийн их байх үйлдвэрлэлийн төлөвлөгөө гаргах шаардлагатай.

ДаалгаварI(эх):

F=c1x1+c2x2+…+CnXn->max хязгаарлалттай:

ба сөрөг бус байдлын нөхцөл x1>=0, x2>=0,…,Xn>=0

Бүтээгдэхүүний төрөл тус бүрийн нөөцийн хэрэглээ нь байгаа нөөцөөс хэтрээгүй нөхцөлд бүтээгдэхүүний борлуулалтаас олох ашиг (орлого) хамгийн их байх үйлдвэрлэлийн төлөвлөгөөг X=(x1,x2,…,Xn) гарга.

ДаалгаварII(хос)

Z=b1y1+b2y2+…+BmYm->мин

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

болон сөрөг бус байх нөхцөл

y1>=0, y2>=0,…,yn>=0.

Y=(y1,y2,…,yn) нөөцийн ийм багц үнийг (тооцоо) ол, энэ үед нөөцийн нийт зардал хамгийн бага байх бөгөөд бүтээгдэхүүний төрөл тус бүрийг үйлдвэрлэхэд шаардагдах нөөцийн зардал бага байх болно. энэ бүтээгдэхүүнийг борлуулснаас олсон ашиг (орлого)-оос багагүй байна

Дээрх загварт bi(i=1,2,…,m) нөөцийн нөөц Si-г илэрхийлнэ; aij - нэгж бүтээгдэхүүн үйлдвэрлэхэд зарцуулсан нөөцийн нэгжийн Si тоо Pj(j=1,2,…,n); cj- нэгж үйлдвэрлэлийн борлуулалтаас олсон ашиг (орлого) Pj (эсвэл бүтээгдэхүүний үнэ Pj) .

Зарим байгууллага аж ахуйн нэгжийн S1, S2,..., Sm нөөцийг худалдан авахаар шийдсэн бөгөөд эдгээр нөөцийн y1, y2,..., ym үнийг оновчтой тогтоох шаардлагатай байна гэж бодъё. Мэдээжийн хэрэг, худалдан авагч байгууллага Z бүх нөөцийг b1,b2,...,bm тоо хэмжээгээр зарцуулах сонирхолтой байдаг. y1,y2,…,ym үнээр тус тус хамгийн бага байсан, өөрөөр хэлбэл. Z=b1,y1+b2y2+…+bmym->мин.

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

Бүтээгдэхүүний нэгж P1 үйлдвэрлэхэд a11 нэгж нөөц S1, a21 нэгж нөөц S2,...., aj1 нэгж нөөц Si1,......, am1 нэгж нөөц Sm y1 үнээр зарцуулагдана. ,y1,...,yi,...,ym тус тус. Тиймээс худалдагчийн шаардлагыг хангахын тулд P1 бүтээгдэхүүний нэгжийг үйлдвэрлэхэд зарцуулсан нөөцийн өртөг нь түүний үнээс багагүй байх ёстой c1, өөрөөр хэлбэл. a11y1+a21y2+…+am1ym>=c1.

Үүний нэгэн адил та P1, P2,...Pn бүтээгдэхүүний төрөл тус бүрт тэгш бус байдлын хэлбэрээр хязгаарлалт үүсгэж болно. Ийнхүү олж авсан II давхар бодлогын эдийн засаг-математик загвар, утга учиртай тайлбарыг хүснэгтийн баруун талд өгөв.

Нөөцийн үнэ y1,y1,…,yi,…,ym эдийн засгийн ном зохиолд янз бүрийн нэрээр нэрлэгдсэн байдаг. нягтлан бодох бүртгэл, далд, сүүдэр . Эдгээр нэрсийн утга нь энэ юм нөхцөлт , "хуурамч" үнэ. Дүрмээр бол үйлдвэрлэл эхлэхээс өмнө мэдэгдэж байсан бүтээгдэхүүний үнэ c1,c2,…,cn "гадаад" үнээс ялгаатай нь нөөцийн үнэ y1,y2,…,ym. байна дотоод , Учир нь тэдгээр нь гаднаас өгөгдөөгүй, харин асуудлыг шийдсэний үр дүнд шууд тодорхойлогддог тул тэдгээрийг ихэвчлэн нэрлэдэг. тооцоолол нөөц.

10. Харилцан давхар LP асуудлууд ба тэдгээрийн шинж чанарууд

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

Хоёр үүрэг даалгавар нь дараах байдалтай байна шинж чанарууд:

1. Нэг бодлогод шугаман функцийн максимум, нөгөөд хамгийн бага утгыг хайсан.

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

3. Бодлого бүрийг стандарт хэлбэрээр өгсөн бөгөөд хамгийн их байлгах бодлогод "хэлбэрийн бүх тэгш бус байдлыг харуулав"<=", а в задаче минимизации – все неравенства вида ">=".

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

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

6. Хоёр бодлогод хувьсагчийн сөрөг бус байх нөхцөл хадгалагдана.

Сэтгэгдэл.Хэрэв анхны бодлогын j-р хувьсагч дээр сөрөг бус нөхцөл ногдуулсан бол давхар бодлогын j-р хязгаарлалт нь тэгш бус байдал байх ба хэрэв j-р хувьсагч нь эерэг ба сөрөг утгыг хоёуланг нь авч болно. хос бодлогын j-р хязгаарлалт нь тэгшитгэл байх болно; Анхны асуудлын хязгаарлалт ба хосын хувьсагчид ижил төстэй хамааралтай.

Заасан шинж чанартай шугаман програмчлалын I ба II хоёр бодлогыг тэгш хэмтэй хос бодлого гэнэ. Дараах зүйлд бид энгийн байх үүднээс тэдгээрийг нэрлэх болно давхар даалгавар.

LP асуудал бүр нь түүний давхар даалгавартай холбоотой байж болно.

11. Хос бодлого зохиох алгоритм:

1. Анхны асуудлын хязгаарлалтын системийн бүх тэгш бус байдлыг нэг утга болгон бууруул: хэрэв анхны бодлогод шугаман функцийн хамгийн их утгыг хайж байгаа бол хязгаарлалтын системийн бүх тэгш бус байдлыг "хэлбэр" болгон бууруул.<=", а если минимум – к виду ">=". Энэ шаардлагыг хангаагүй эдгээр тэгш бус байдлын хувьд -1-ээр үржүүлнэ.

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

3. А матрицад шилжүүлсэн матрицыг ол .

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

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

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

Оновчтой байдлын хангалттай шинж тэмдэг.

Хэрэв X*=(x1*,x2*,…,xn*) Тэгээд Y*=(y1*,y2*,…,ym*) - тэгш байдлыг хангасан хоёрдмол асуудлуудын зөвшөөрөгдөх шийдэл;

тэгвэл анхны бодлого I, давхар бодлогын оновчтой шийдэл болно.

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

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

Fmax = Змин эсвэл F(X*)=Z(Y*) .

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

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

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

Үйлдвэрлэлийн төлөвлөгөө X*=(x1*,x2*,…,xn*) ба нөөцийн үнийн багц (тооцоо) Y*=(y1*,y2*,…,ym*) "Гадаад" (урьдчилан мэдэгдэж байгаа) үнээр c1, c2,..., cn-ээр олдсон бүтээгдэхүүнээс олох ашиг (орлого) нь "дотоод" нөөцийн зардалтай тэнцүү (зөвхөн тодорхойлогддог) тохиолдолд л оновчтой болно. асуудлыг шийдэхээс) үнэ y1 ,y2,…,ym. Бусад бүх төлөвлөгөөний хувьд XТэгээд ЮХоёр асуудалд бүтээгдэхүүнээс олох ашиг (орлого) нь нөөцийн зардлаас үргэлж бага (эсвэл тэнцүү) байдаг.

Анхны хоёрдмол байдлын теоремын эдийн засгийн утгыг дараах байдлаар тайлбарлаж болно: ААН оновчтой төлөвлөгөөний дагуу бүтээгдэхүүн үйлдвэрлэж X*=(x1*,x2*,…,xn*) хамгийн их ашиг (орлого) авах эсэхдээ хайхрамжгүй ханддаг Fmax эсвэл нөөцийг оновчтой үнээр зарах Ү* =(y1*,y2*,…,ym*) мөн нөөцийн Zmin хамгийн бага зардлыг борлуулалтаас нөхөн төлөх.

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

Хоёр харилцан давхар бодлого өгье. Хэрэв эдгээр асуудал бүрийг симплекс аргыг ашиглан шийдсэн бол тэдгээрийг каноник хэлбэрт оруулах шаардлагатай бөгөөд үүний тулд I асуудлын хязгаарлалтын системд оруулах шаардлагатай (богино тэмдэглэгээ). Тсөрөг бус хувьсагчид болон II асуудлын хязгаарлалтын системд () – n сөрөг бус хувьсагч, энд i(j) нь нэмэлт хувьсагчийг оруулсан тэгш бус байдлын тоо юм.

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

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

Теорем. Харилцан уялдаатай давхар асуудлын аль нэгний оновчтой шийдлийн эерэг (тэг биш) бүрэлдэхүүн хэсгүүд нь нөгөө асуудлын оновчтой шийдлийн тэг бүрэлдэхүүн хэсгүүдтэй тохирч байна, өөрөөр хэлбэл. дурын i=1,2,…,m u j=1,2,…,n хувьд: хэрэв X*j>0 бол; Хэрэв , дараа нь, мөн адил,

хэрэв, тэгвэл ; хэрэв, тэгвэл.

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

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

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

14. Объектив байдлаар тодорхойлсон үнэлгээ, тэдгээрийн утга

Давхар асуудлын оновчтой шийдлийн бүрэлдэхүүн хэсгүүдийг анхны асуудлын оновчтой (хос) тооцоолол гэж нэрлэдэг. Академич Л.В.Канторович тэднийг дуудсан бодитойгоор тодорхойлсон"тооцоолол (Уран зохиолд тэдгээрийг далд орлого гэж нэрлэдэг) .

S1, S2, S3, S4 нөөцийн би нөөцийн зөрүүг илэрхийлэх анхны бодлогын нэмэлт хувьсагч I. болон тэдгээрийн хэрэглээг илэрхийлнэ үлдсэн нөөц , ба тэдгээрээс нэгж бүтээгдэхүүн үйлдвэрлэх нөөцийн зардал ба P1, P2 бүтээгдэхүүний үнэ cj хоорондын зөрүүг илэрхийлдэг давхар асуудлын II нэмэлт хувьсагч. , илэрхийлэх зардлын үнээс давсан.

Тиймээс, нөөцийн бодитой тодорхойлсон үнэлгээ нь нөөцийн хомсдлын түвшинг тодорхойлдог: үйлдвэрлэлийн оновчтой төлөвлөгөөний дагуу хомс (өөрөөр хэлбэл бүрэн ашигласан) нөөц нь тэгээс ялгаатай үнэлгээ, хомс бус нөөц нь тэг үнэлгээ авдаг. y*i утга нь i-р нөөцийн үнэлгээ юм. Тооцооллын y*i-ийн утга өндөр байх тусам нөөцийн хомсдол нэмэгдэнэ. Ховор биш нөөцийн хувьд y*i=0.

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

Гурав дахь хоёрдмол теорем . Давхар асуудлын оновчтой шийдлийн бүрэлдэхүүн хэсгүүд нь шугаман функцийн хэсэгчилсэн деривативуудын утгатай тэнцүү байна. Fmax(б1, б2,…, bm)холбогдох аргументуудын дагуу, i.e.

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

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

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

1. Нөөц, бүтээгдэхүүний хомсдлын үзүүлэлт.

2. Зорилгын функцийн утгад хязгаарлалтын нөлөөллийн үзүүлэлт.

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

4. Нийт нөхцөлт зардал, үр дүнг харьцуулах хэрэгсэл.

15. Зардлын шалгуурт үндэслэн тээврийн асуудлын мэдэгдэл.

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

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

Зардлын шалгуурын дагуу техникийн үзүүлэлтүүдийн хамгийн энгийн томъёолол нь дараах байдалтай байна ТА1,…, хөөргөх цэгүүдэд хүргэх ёстой нэгэн төрлийн ачааны (нөөц) a1,…,am байгаа эсэх. nхэрэглэгчид B1,…,Bn тоо хэмжээгээр b1,…,bn нэгж (хэрэгцээ). Нэг нэгж ачааг i-р цэгээс хэрэглээний j-р цэг хүртэл тээвэрлэхэд Cij тээврийн зардал тодорхой байна.

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

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

Үйлчилгээ үзүүлэгч	Хэрэглэгч			Ачааны нөөц
Хэрэгцээтэй

Энд i-р цэгээс j-р очих газар хүртэл тээвэрлэсэн ачааны хэмжээ xij-тэй тэнцүү, i-р цэгийн ачааны нөөцийг ai>=0 утгаар тодорхойлно. j-р очих газар ачааны хэрэгцээ bj>=0 . Бүх xij>=0 гэж таамаглаж байна.

Матриц гэж нэрлэдэг тарифын матриц (зардал эсвэл тээврийн зардал).

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

Тээврийн төлөвлөгөөг хэрэгжүүлэхтэй холбоотой нийт зардлыг зорилгын функцээр илэрхийлж болно

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

– нөөцийн хязгаарлалт (2);

– хэрэглэгчдэд тавих хязгаарлалт (2);

– сөрөг бус нөхцөл (3).

Тиймээс математикийн хувьд тээврийн асуудлыг дараах байдлаар томъёолсон болно. (3) нөхцөл дэх хязгаарлалтын систем (2) ба зорилгын функц (1) өгөгдсөн. (2) системийн шийдлүүдийн дотроос (1) функцийг багасгах сөрөг бус шийдлийг олох шаардлагатай.

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

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

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

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

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

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

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

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

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

Теорем. Тээврийн асуудлын матрицын зэрэглэл нь тэгшитгэлийн тооноос нэгээр бага байна, жишээлбэл. r ( а )= м + n -1.

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

Тээврийн ажлын тээвэрлэлтийн төлөвлөгөөг бид шууд түгээлтийн хүснэгтээс хайх болно. Хэрэв xij хувьсагч утга авбал энэ утгыг харгалзах нүдэнд (I,j) бичнэ, харин xij=0 бол (I,j) нүдийг чөлөөтэй үлдээнэ гэж бодъё. Тархалтын хүснэгт дэх матрицын зэрэглэлийн теоремыг харгалзан үзэх лавлагааны төлөвлөгөөнд заавал байх ёстой m+n-1 эзлэгдсэн эсүүд, үлдсэн хэсэг нь үнэ төлбөргүй байх болно.

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

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

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

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

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

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

17. Анхны жишиг төлөвлөгөөг барих

"Баруун хойд булан" дүрэм.

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

Бид "баруун хойд булан" гэж нэрлэгддэг зүүн дээд хэсгээс эхлэн бөглөж, шугамын дагуу баруун эсвэл баганын доошоо шилжинэ. (1; 1) нүдэнд a1 ба b1 тоонуудаас багаыг нь оруулъя, өөрөөр хэлбэл . Хэрэв эхний багана "хаалттай" байвал эхний хэрэглэгчийн эрэлт хэрэгцээ бүрэн хангагдсан байна. Энэ нь эхний баганын бусад бүх нүднүүдийн хувьд ачааны хэмжээ гэсэн үг юм .

Хэрэв, эхний мөр нь мөн адил "хаалттай", өөрөөр хэлбэл for . Бид орох зэргэлдээх нүдийг (2; 1) дүүргэж үргэлжлүүлнэ.

Хоёрдахь нүдийг (1; 2) эсвэл (2; 1) бөглөсний дараа бид дараагийн гурав дахь нүдийг хоёр дахь мөр эсвэл хоёр дахь баганын дагуу бөглөнө. Бид ямар нэгэн үе шатанд нөөц бололцоо, хэрэгцээ нь дуусах хүртэл энэ үйл явцыг үргэлжлүүлнэ. Сүүлийн дүүргэсэн нүд нь сүүлийн n-р багана, сүүлийн m-р мөрөнд байх болно.

"Хамгийн бага элемент" дүрэм.

"Баруун хойд булангийн" дүрмийн дагуу баригдсан анхны лавлах төлөвлөгөө нь ихэвчлэн оновчтой байхаас маш хол байдаг, учир нь түүнийг тодорхойлохдоо зардлын үнэ цэнийг харгалздаггүй. Тиймээс цаашдын тооцоолол нь оновчтой төлөвлөгөөнд хүрэхийн тулд олон давталт хийх шаардлагатай болно. Эхний төлөвлөгөөг "хамгийн бага элемент" дүрмийн дагуу барьсан тохиолдолд давталтын тоог бууруулж болно. Үүний мөн чанар нь алхам бүрт ачааг торонд оруулах хамгийн дээд "хөдөлгөөн"-ийг cij хамгийн бага тарифаар гүйцэтгэдэг явдал юм. Бид тарифын матрицын cij хамгийн бага элементтэй тохирох нүднээс хүснэгтийг бөглөж эхэлнэ. ai эсвэл bj тоонуудын бага нь хамгийн бага тарифтай нүдэнд байрлана . Дараа нь бараа материал нь бүрэн дууссан нийлүүлэгчтэй харгалзах мөр, эсвэл эрэлт нь бүрэн хангагдсан хэрэглэгчтэй харгалзах баганыг авч үзэхгүй. Нийлүүлэгчийн бараа материал бүрэн дуусч, хэрэглэгчийн эрэлт хэрэгцээ бүрэн хангагдсан тохиолдолд мөр, баганыг нэгэн зэрэг хасах шаардлагатай байж болно. Дараа нь хүснэгтийн үлдсэн нүднүүдээс хамгийн бага тарифтай нүдийг дахин сонгож, бүгдийг нь тарааж, эрэлтийг хангах хүртэл хувьцааг хуваарилах үйл явц үргэлжилнэ.

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

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

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

Нэг цэгт нэг тонн ачааны өртөг нь тээвэрлэхээс өмнөх тонн ачааны зардал + тээвэрлэлтийн зардалтай тэнцүү байна: .

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

1. Тээврийн үндсэн төлөвлөгөөг заасан дүрмийн аль нэгний дагуу хий. Бөглөх нүдний тоо m+n-1 байх ёстой.

2. Потенциал ба үүний дагуу ханган нийлүүлэгчид болон хэрэглэгчдийг (эзлэгдсэн эсийн хувьд) тооцоолно: . Бөглөх нүдний тоо m+n-1, тэгшитгэлийн тоо m+n байна. Учир нь Тэгшитгэлийн тоо нь үл мэдэгдэх тооноос нэгээр бага байвал үл мэдэгдэх нэг нь чөлөөтэй болж, ямар ч тоон утгыг авч болно. Жишээлбэл, . Өгөгдсөн лавлагааны шийдлийн үлдсэн боломжуудыг өвөрмөц байдлаар тодорхойлно.

3. Оновчтой байдлыг шалгах, өөрөөр хэлбэл. чөлөөт эсийн хувьд тооцооллыг тооцоол. Хэрэв тээвэрлэлт нь тохиромжтой, X төлөвлөгөө оновчтой байвал оновчтой байдлын шинж тэмдэг юм. Хэрэв дор хаяж нэг ялгаа байгаа бол шинэ лавлах төлөвлөгөө рүү шилжинэ. Эдийн засгийн утгаараа үнэ цэнэ нь i-р ханган нийлүүлэгч j-р хэрэглэгчдэд нэг удаа хүргэлтийн улмаас үүсэх тээврийн нийт зардлын өөрчлөлтийг тодорхойлдог. Хэрэв тийм бол нэг хүргэлт нь тээврийн зардлыг хэмнэхэд хүргэдэг, гэхдээ хэрэв байвал тэдгээрийг нэмэгдүүлэх болно. Тиймээс, хэрэв үнэ төлбөргүй нийлүүлэлтийн чиглэлүүдийн дунд тээврийн зардлыг хэмнэх чиглэл байхгүй бол үр дүнд хүрэх төлөвлөгөө нь оновчтой болно.

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

a) Өгөгдсөн чөлөөт нүдтэй циклээр холбогдсон нүд бүрт тодорхой тэмдэг өгөгдсөн бөгөөд энэ чөлөөт нүд нь "+", бусад бүх нүд (мөчлөгийн орой) нь "-" ба "тэмдэгтүүдийг ээлжлэн өгдөг. +”. Бид эдгээр эсүүдийг хасах ба нэмэх гэж нэрлэх болно.

б) Циклийн сөрөг эсүүдэд бид хамгийн бага нийлүүлэлтийг олдог бөгөөд үүнийг бид тэмдэглэдэг. Хасах нүдэнд байрлах xij тоонуудаас бага нь энэ чөлөөт нүдэнд шилжинэ. Үүний зэрэгцээ энэ тоог "+" тэмдэгтэй нүднүүдийн харгалзах тоон дээр нэмж, хасах нүднүүдийн тооноос хасна. Өмнө нь чөлөөтэй байсан эсийг эзэлж, дэмжлэгийн хавтгайд ордог; мөн xij тоонуудын хамгийн бага хэсгийг агуулсан хасах нүдийг үнэ төлбөргүй гэж үзэж, дэмжлэгийн төлөвлөгөөг орхино.

Тиймээс шинэ жишиг төлөвлөгөөг тодорхойлсон. Дээр дурдсан нэг жишиг төлөвлөгөөнөөс нөгөөд шилжих шилжилтийг дахин тооцоолох мөчлөгийн шилжилт гэж нэрлэдэг. Дахин тооцоолох мөчлөгийн дагуу шилжих үед эзлэгдсэн эсийн тоо өөрчлөгдөхгүй, тухайлбал m+n-1-тэй тэнцүү байна. Түүнээс гадна, хэрэв сөрөг нүднүүдэд хоёр ба түүнээс дээш ижил тооны xij байгаа бол эдгээр эсүүдийн зөвхөн нэг нь суллагдаж, үлдсэн хэсэг нь тэг хангамжтай үлддэг.

5. Үүссэн лавлагааны төлөвлөгөөг оновчтой эсэхийг шалгана, i.e. 2-р алхамаас бүх алхмуудыг давт.

19. Динамик програмчлалын тухай ойлголт.

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

Ихэвчлэн АН-ын аргууд нь зарим хяналттай системийн ажиллагааг оновчтой болгодог бөгөөд тэдгээрийн үр нөлөөг үнэлдэг нэмэлт, эсвэл үржүүлэх, зорилгын функц. Нэмэлт f(x1,x2,…,xn) хэд хэдэн хувьсагчийн функцийг дуудах ба түүний утгыг зөвхөн нэг xj хувьсагчаас хамаарах зарим fj функцүүдийн нийлбэрээр тооцдог: . Нэмэлт зорилгын функцийн нөхцөлүүд нь хяналттай үйл явцын бие даасан үе шатанд гаргасан шийдвэрийн үр дүнтэй тохирч байна.

Р.Беллманы оновчтой байх зарчим.

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

1. судалгааны объект байх ёстой хяналттай систем (объект) өгөгдсөн хүчинтэй мужууд мөн хүлээн зөвшөөрөх боломжтой хэлтэс;

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

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

4. үе шат бүрт системийн төлөвийг ижил (найрлагад) параметрийн багцаар тодорхойлсон байх ёстой;

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

Динамик програмчлалын загварыг ерөнхий хэлбэрээр ашиглах асуудлыг авч үзье. Даалгавар нь өөр өөр төлөвт байж болох зарим хийсвэр объектыг удирдах явдал байг. Объектын одоогийн төлөвийг тодорхой багц параметрүүдээр тодорхойлж, цааш нь S гэж тэмдэглэж, нэрлэх болно. төлөв вектор. Бүх боломжит төлөвүүдийн S багц өгөгдсөн гэж үздэг. Мөн объектод зориулж тодорхойлсон багц байдаг зөвшөөрөгдөх хяналт(хяналтын үйлдлүүд) X,ерөнхий шинж чанараа алдалгүйгээр тоон олонлог гэж үзэж болно. Хяналтын үйлдлүүдийг цаг хугацааны хувьд салангид мөчид хийж, удирдаж болно шийдэлудирдлагын аль нэгийг сонгохоос бүрдэнэ. Төлөвлөгөөдаалгавар эсвэл удирдлагын стратеги-ийг x=(x1,x2,…,xn-1) вектор гэж нэрлэдэг бөгөөд түүний бүрэлдэхүүн хэсгүүд нь үйл явцын алхам бүр дээр сонгогдсон удирдлага юм. Хүлээгдэж буй байдлаас харахад үр дагавар байхгүй Sk ба Sk+1 объектын дараалсан хоёр төлөв бүрийн хооронд мэдэгдэж буй функциональ хамаарал байгаа бөгөөд үүнд сонгосон удирдлагыг мөн багтаасан болно: . Тиймээс объектын анхны төлөвийг тохируулах, төлөвлөгөөг сонгох Xтодорхой тодорхойлох зан үйлийн замналобьект.

Үр ашгийг алхам тутамд хянах кодоогийн төлөв Sk, сонгосон хяналтын xk-аас хамаарах ба нэр томъёо болох fk(xk,Sk) функцуудыг ашиглан тоон үзүүлэлтийг тодорхойлно. нэмэлт зорилгын функц , байгууламжийн удирдлагын ерөнхий үр ашгийг тодорхойлдог. (Анхаарна уу , fk(xk,Sk) функцийн тодорхойлолт нь зөвшөөрөгдөх утгуудын хүрээг агуулна xk , мөн энэ талбай нь дүрмээр бол одоогийн Sk-ийн төлөв байдлаас хамаарна). Хамгийн оновчтой хяналт , Өгөгдсөн S1 төлөвийн хувьд ийм оновчтой төлөвлөгөөг сонгоход хүрдэг x* , Үүнд хүрч байна дээд хэмжээ харгалзах зам дээрх fk утгууд.

Динамик програмчлалын үндсэн зарчим бол алхам бүрт fk(xk,Sk) функцийг тусгаарласан оновчлохыг хичээх хэрэггүй, харин дараачийн бүх алхамууд оновчтой гэж үзэн x*k оновчтой удирдлагыг сонгох явдал юм. Албан ёсоор энэ зарчмыг алхам бүрээр нь олж хэрэгжүүлдэг к нөхцөлт оновчтой хяналтууд , одоогийн төлөвийг S гэж үзвэл энэ алхамаас эхлэн хамгийн их нийт үр ашгийг өгнө.

Zk(s) нь fk функцийн нийлбэрийн хамгийн их утгыг тэмдэглэе -аас бүх алхамууд көмнө П(үйл явцын өгөгдсөн сегмент дэх оновчтой хяналтаар олж авсан), алхмын эхэнд байгаа объект к S төлөвт байна. Дараа нь Zk(s) функцүүд давтагдах хамаарлыг хангах ёстой:

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

Хяналтын оновчтой стратеги нь дараахь нөхцлийг хангасан байх ёстой. анхны төлөв ямар ч байсан sk k-р алхам болон энэ алхам дээр сонгосон удирдлага xk, дараагийн удирдлага (удирдлагын шийдвэрүүд) нь оновчтой байх ёстой cocmo Иания ,k алхам дээр гаргасан шийдвэрийн үр дүнд бий болсон .

Үндсэн хамаарал нь Zk(s) функцийг олох боломжийг олгодог. зөвхөн В-тай хослуулсан анхны нөхцөл,аль нь манай тохиолдолд тэгш байдал юм.

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

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

20. Тоглоомын загваруудын тухай ойлголт.

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

Албан ёсны тоглоом бүрийн хувьд, дүрэм , тэдгээр. дараахь нөхцлийн тогтолцоог тодорхойлдог: 1) тоглогчдын үйлдлийн сонголтууд; 2) тоглогч бүр түншийнхээ зан байдлын талаархи мэдээллийн хэмжээ; 3) үйл ажиллагааны багц бүрд хүргэдэг ашиг. Ерөнхийдөө хожих (эсвэл ялагдах) нь тоон үзүүлэлтээр илэрхийлэгдэх боломжтой; жишээлбэл, та хожигдлыг тэг, хожлыг нэг, тэнцэхийг 1/2 гэж үнэлж болно. Тоглоомын үр дүнг тоогоор илэрхийлэхийг нэрлэдэг төлбөр .

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

Тоглоом гэж нэрлэгддэг тэг нийлбэр тоглоом эсвэл антагонист тэнгэр , хэрэв тоглогчдын аль нэгнийх нь ашиг нөгөөгийнхөө алдагдалтай тэнцүү бол, i.e. хоёр талын хожлын нийлбэр тэг байна. Тоглоомын даалгаврыг гүйцэтгэхийн тулд тэдгээрийн аль нэгнийх нь үнэ цэнийг зааж өгөхөд хангалттай . Хэрэв бид зааж өгвөл А- тоглогчдын аль нэгний ялалт; б – нөгөөх нь хожсон, дараа нь тэг нийлбэртэй тоглоомын хувьд b = –А, тиймээс жишээ нь авч үзэхэд хангалттай А.

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

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

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

Тоглоомыг зөвхөн хөдөлгөөний шинж чанараар (хувийн, санамсаргүй) ангилдаг, мөн тоглогч тус бүрт нөгөөгийнхөө үйлдлийн талаархи мэдээллийн шинж чанар, хэмжээгээр нь ангилдаг. Тоглоомын тусгай анги нь "бүрэн мэдээлэл бүхий тоглоомууд" гэж нэрлэгддэг тоглоомууд юм. Бүрэн мэдээлэл бүхий тоглоом тоглогч бүр хувийн болон санамсаргүй байдлаар өмнөх бүх нүүдлийнхээ үр дүнг мэддэг тоглоом юм. Бүрэн мэдээлэл бүхий тоглоомуудын жишээнд шатар, даам болон бидний сайн мэдэх “tic-tac-toe” тоглоом орно. Ихэнх практик ач холбогдолтой тоглоомууд нь бүрэн мэдээлэл бүхий тоглоомуудын ангилалд хамаарахгүй, учир нь дайсны үйл ажиллагааны талаархи тодорхойгүй байдал нь ихэвчлэн зөрчилдөөний нөхцөл байдлын чухал элемент юм.

Тоглоомын онолын үндсэн ойлголтуудын нэг бол үзэл баримтлал юм стратеги .

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

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

Тоглолт хэд хэдэн удаа давтагдсан бол тоглогчид тодорхой тоглоом бүрт ялах, хожигдох сонирхолгүй байж магадгүй юм. А дундаж ялалт (хожигдол) бүх багцаар.

Тоглоомын онолын зорилго нь тоглогч бүрийн оновчтой стратегийг тодорхойлох явдал юм.

21. Төлбөрийн матриц. Тоглоомын доод ба дээд үнэ

Тоглогчийн тоглох эцсийн тоглоом АБайгаа Тстратеги, тоглогч V – хстратегийг m×n тоглоом гэж нэрлэдэг.

Хоёр тоглогчийн m×n тоглоомыг авч үзье АТэгээд IN("бид" ба "дайсан").

Тоглогчийг зөвшөөр Абайна Т A1,A2,…,Am гэж бидний тэмдэглэдэг хувийн стратеги. Тоглогчийг зөвшөөр INболомжтой nхувийн стратеги, тэдгээрийг B1,B2,…,Bn гэж тэмдэглэе.

Тал бүр тодорхой стратеги сонгох; бидний хувьд энэ нь Ай, дайсан Бж болно. Тоглогчид Ai ба Bj () гэсэн аль ч хос стратегийг сонгосны үр дүнд тоглоомын үр дүн онцгой байдлаар тодорхойлогддог, өөрөөр хэлбэл. тоглогчийн ялалт aij А(эерэг эсвэл сөрөг) болон тоглогчийн алдагдал (-aij). IN.

aij-ийн утгыг аль ч хос стратегид мэддэг гэж үзье (Ai, Bj) . P=aij матриц , элементүүд нь Ai ба Bj стратегид тохирох ашиг юм, дуудсан төлбөрийн матриц эсвэл тоглоомын матриц. Энэ матрицын мөрүүд нь тоглогчийн стратегитай тохирч байна А,ба баганууд - тоглогчийн стратеги Б. Эдгээр стратегийг цэвэр гэж нэрлэдэг.

Тоглоомын m×n матриц нь дараах хэлбэртэй байна.

Матрицтай m×n тоглоомыг авч үзээд A1,A2,…,Am стратегиас хамгийн сайныг нь тодорхойл. . стратеги Ai тоглогч сонгох Атоглогч үүнийг хүлээх ёстой INтоглогч хожсон Bj стратегиудын аль нэгээр хариулах болно Ахамгийн бага (тоглогч INтоглогчийг "хор хөнөөл" гэж оролддог А).

Тоглогчийн хамгийн бага ялалтаар тэмдэглэе Атэр бүх боломжит тоглогчийн стратеги Ai стратегийг сонгох үед IN(хамгийн бага тоо битөлбөрийн матрицын th эгнээ), i.e.

Бүх тоонуудаас () бид хамгийн томыг нь сонгоно: .

За дуудъя тоглоомын хамгийн бага үнэ, эсвэл хамгийн их ялалт (хамгийн их). Энэ нь В тоглогчийн стратегийн хувьд А тоглогчийн хувьд баталгаатай ялалт юм. Тиймээс,

Максиминд тохирсон стратеги гэж нэрлэдэг максимин стратеги . Тоглогч INтоглогчийн хожлыг бууруулах сонирхолтой А, Bj стратегийг сонгохдоо тэрээр хамгийн их ашиг авчрах боломжийг харгалзан үздэг А.гэж тэмдэглэе

Бүх тоонуудын дундаас хамгийн жижигийг нь сонго

тэгээд залгацгаая тоглоомын дээд үнэ эсвэл хамгийн бага ялалт(минимакс). Эго тоглогч Б-г алдах баталгаатай. Тиймээс,

Minimax-д тохирсон стратеги гэж нэрлэдэг минимакс стратеги.

Тоглогчдод хамгийн "болгоомжтой" минимакс ба максимин стратегийг сонгохыг шаарддаг зарчмыг нэрлэдэг. хамгийн бага зарчим . Энэ зарчим нь тоглогч бүр өрсөлдөгчийнхөө эсрэг зорилгод хүрэхийг хичээдэг гэсэн үндэслэлтэй таамаглалаас үүдэлтэй.

Теорем. Тоглоомын доод үнэ нь тоглоомын дээд үнээс үргэлж давдаггүй .

Тоглоомын дээд ба доод үнэ ижил байвал тоглоомын дээд ба доод үнийн нийт үнэ цэнийг гэнэ. тоглоомын цэвэр үнэ, эсвэл тоглоомын зардлаар. Тоглоомын үнэд тохирсон Minimax стратеги оновчтой стратегиуд , бөгөөд тэдгээрийн нийт нь юм оновчтой шийдэл эсвэл тоглоомын шийдэл. Энэ тохиолдолд тоглогч Ахамгийн дээд баталгааг хүлээн авдаг (тоглогчийн зан төлөвөөс үл хамааран) IN)ялалт v, мөн тоглогч INхамгийн бага баталгаатай (тоглогчийн зан төлөвөөс үл хамааран). A)алдаж байна v. Тоглоомын шийдэл байгаа гэж тэд хэлэв тогтвортой байдал , тэдгээр. Хэрэв нэг тоглогч оновчтой стратегиа баримталбал нөгөө нь оновчтой стратегиасаа хазайх нь ашигтай байж чадахгүй.

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

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

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

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

Тиймээс, power point бүхий тоглоом бүрийн хувьд дараах шинж чанараараа ялгаатай хоёр талдаа оновчтой хос стратегийг тодорхойлох шийдэл байдаг.

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

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

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

22. Холимог стратеги дэх тоглоомын шийдэл.

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

Холимог стратеги Са А тоглогч нь p1,p2,…pi,…pm магадлал бүхий A1,A1,…,Ai,…,Am цэвэр стратегиудын хэрэглээ бөгөөд магадлалын нийлбэр нь 1: . А тоглогчийн холимог стратеги нь матриц хэлбэрээр бичигдсэн байдаг

эсвэл мөр хэлбэрээр Sa=(p1,p2,…,pi,…,pm).

Үүний нэгэн адил, В тоглогчийн холимог стратегийг дараах байдлаар тэмдэглэнэ.

Эсвэл Sb=(q1,q2,…,qi,…,qn),

стратеги гарч ирэх магадлалын нийлбэр нь 1-тэй тэнцүү байна: .

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

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

Энд α ба β нь тоглоомын доод ба дээд үнэ юм.

Энэхүү мэдэгдэл нь тухайн зүйлийн агуулгыг бүрдүүлдэг Тоглоомын онолын үндсэн теорем.Энэ теоремыг 1928 онд Жон фон Нейман анх баталсан. Теоремын мэдэгдэж байгаа баталгаа нь харьцангуй төвөгтэй; Тиймээс бид зөвхөн түүний томъёоллыг өгөх болно.

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

Үндсэн теоремоос харахад хязгаарлагдмал тоглоом бүр үнэтэй байдаг.

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

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

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

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

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

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

Тэдгээрийг олохын тулд бид идэвхтэй стратегийн теоремыг ашигладаг. Хэрэв тоглогч бол Аоновчтой стратегиа баримталдаг , Дараа нь түүний дундаж ялалт тоглоомын үнэтэй тэнцэх болно v, тоглогч ямар ч идэвхтэй стратеги ашигладаг IN. 2х2 тоглоомын хувьд дунд цэг байхгүй тохиолдолд ямар ч цэвэр өрсөлдөгчийн стратеги идэвхтэй байдаг. Тоглогчийн ялалт А(тоглогчийн алдагдал IN)– математикийн хүлээлт (дундаж утга) нь тоглоомын үнэ болох санамсаргүй хэмжигдэхүүн. Тиймээс дундаж тоглогчийн ашиг А(оновчтой стратеги) тэнцүү байх болно vдайсны 1 ба 2-р стратегийн хувьд.

Тоглоомыг өгөөжийн матрицаар өгье.

Тоглогчийн дундаж ялалт А,тэр оновчтой холимог стратеги болон тоглогч ашигладаг бол IN -цэвэр стратеги В1 (энэ нь төлбөрийн матрицын 1-р баганатай тохирч байна R),тоглоомын үнэтэй тэнцүү байна v: .

Тоглогч ижил дундаж хожлыг авдаг А, хэрэв 2-р тоглогч В2 стратегийг ашигладаг бол, i.e. . Үүнийг харгалзан бид оновчтой стратегийг тодорхойлох тэгшитгэлийн системийг олж авдаг болон тоглоомын үнэ v:

Энэ системийг шийдэж, бид оновчтой стратегийг олж авдаг

болон тоглоомын үнэ.

Хайлт хийхдээ идэвхтэй стратегийн тухай теоремыг ашиглах – тоглогчийн оновчтой стратеги IN,Бид үүнийг ямар ч цэвэр тоглогч стратегийн хувьд олж мэдсэн А (А1 эсвэл А2) дундаж тоглогчийн алдагдал INтоглоомын үнэтэй тэнцүү байна v, өөрөөр хэлбэл

Дараа нь оновчтой стратегийг дараах томъёогоор тодорхойлно.

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

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

Хэрэв матрицын i-р эгнээний бүх элементүүд k-р эгнээний харгалзах элементүүдээс бага байвал тоглогчийн i-р стратеги Аашиггүй (ашиг багатай).

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

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

23. Тоглоомын геометрийн тайлбар 2х2

Тоглоомын шийдэл 2х2тодорхой геометрийн тайлбар хийх боломжийг олгодог.

Тоглоомыг P=(aij), i, j=1,2 төлбөрийн матрицаар тодорхойл.

Абсцисса тэнхлэг дээр (Зураг) бид зурах болно нэгжсегмент A1A2; цэг А1 ( X=0) стратеги A1, цэг A2 ( X=1) стратеги А2-г дүрсэлсэн бөгөөд энэ сегментийн бүх завсрын цэгүүд нь эхний тоглогчийн холимог стратеги Sa ба сегментийн Sa-аас баруун төгсгөл хүртэлх зай нь А1 стратегийн p1 магадлал юм. , зүүн төгсгөл хүртэлх зай – А2 стратегийн p2 магадлал .

А1 ба А2 цэгүүдээр дамжуулан абсцисса тэнхлэгт хоёр перпендикуляр зуръя: I-I тэнхлэг ба II-II тэнхлэг. I-I тэнхлэг дээр бид стратеги A1-ийн ялалтыг төлөвлөх болно; II-II тэнхлэг дээр – А2 стратегийн үр ашиг.

Хэрэв А тоглогч А1 стратегийг ашигладаг бол В тоглогчийн В1 стратегийн ашиг нь a11, В2 стратегитай бол a12-той тэнцүү байна. I тэнхлэг дээрх a11, a12 тоонууд нь B1 ба B2 цэгүүдтэй тохирч байна.

Хэрэв А тоглогч А2 стратегийг ашигладаг бол В тоглогчийн В1 стратегийн ашиг нь a21, В2 стратегитай бол a22-той тэнцүү байна. a21 ба a22 тоонууд нь II тэнхлэг дээрх B1 ба B2 цэгүүдэд тохирч байна.

Бид B1 (I) ба B1 (II) цэгүүдийг холбодог; B2 (I) ба B2 (II). Бид хоёр шулуун шугам авсан. Шууд B1B1 – хэрэв тоглогч бол Ахолимог стратеги (A1, A2 стратегийн p1 ба p2 магадлал бүхий дурын хослол) хэрэглэх ба В тоглогч В1 стратегийг ашигладаг. Тоглогч ялна АЭнэ шугам дээр байрлах зарим цэгтэй тохирч байна. Холимог стратегид тохирох дундаж үр өгөөжийг a11p1+a21p2 томъёогоор тодорхойлж, M1 цэгээр илэрхийлнэ. шулуун B1B1 дээр.

Үүний нэгэн адил бид хоёр дахь тоглогчийн В2 стратегийг ашиглахад тохирсон B2B2 сегментийг байгуулдаг. Энэ тохиолдолд дундаж ялалтыг a12p1+a22p2 томъёогоор тодорхойлж, M2 цэгээр илэрхийлнэ. шууд B2B2 дээр.

Бид оновчтой S*a стратегийг олох хэрэгтэй, өөрөөр хэлбэл хамгийн бага үр өгөөжтэй (ямар ч зан үйлийн хувьд IN)дээд тал руугаа эргэх болно. Үүний тулд бид барих болно хожлын доод хязгаар B1B2 стратегийн хувьд , өөрөөр хэлбэл, зурагт тэмдэглэсэн тасархай шугам B1NB2. тод шугам. Энэ доод хязгаар нь тоглогчийн хамгийн бага ялалтыг илэрхийлнэ Ахолимог стратегийн аль нэгтэй нь; цэгН , Энэ нь хамгийн бага ашиг хамгийн дээд хэмжээнд хүрч, шийдэл (оновчтой стратеги) болон тоглоомын үнийг тодорхойлдог. Ординат цэг Нтоглоомын үнэ байдаг v. Цэгийн координат Н B1B1 ба B2B2 шугамуудын огтлолцох цэгүүдийн координатыг бид олно. Манай тохиолдолд тоглоомын шийдлийг стратегиудын огтлолцлын цэгээр тодорхойлсон. Гэсэн хэдий ч энэ нь үргэлж тийм биш байх болно.

Геометрийн хувьд тоглогчийн хувьд оновчтой стратегийг тодорхойлж болно А,тоглогч ч мөн адил IN;Энэ хоёр тохиолдолд хамгийн бага зарчмыг ашигладаг, гэхдээ хоёр дахь тохиолдолд хожлын доод хязгаарыг биш, харин дээд хязгаарыг тогтоодог бөгөөд хамгийн их биш, харин хамгийн бага хэмжээг тогтооно.

Хэрэв төлбөрийн матрицад сөрөг тоо байгаа бол асуудлыг графикаар шийдэхийн тулд сөрөг бус элементүүдтэй шинэ матриц руу шилжих нь дээр; Үүнийг хийхийн тулд анхны матрицын элементүүдэд харгалзах эерэг тоог нэмэхэд хангалттай. Тоглоомын шийдэл өөрчлөгдөхгүй, харин тоглоомын үнэ энэ тоогоор өсөх болно. График аргыг 2×n, m×2 тоглоомыг шийдвэрлэхэд ашиглаж болно.

24. Матрицын тоглоомыг шугаман програмчлалын бодлого болгон багасгах

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

m×n тоглоомыг өгөөжийн матрицаар өгье . Тоглогч А A1,A2,..Ai,..Am стратегитэй , тоглогч IN -стратеги Б 1,Б 2,..Бби,.. Б n. Энэ нь оновчтой стратеги, хаана тодорхойлох шаардлагатай байна нь харгалзах цэвэр стратеги Ai,Bj, ашиглах магадлал юм.

Хамгийн оновчтой стратеги нь дараах шаардлагыг хангана. Энэ нь тоглогчийг хангадаг Адундаж ялалт, тоглоомын үнээс багагүй байна v, ямар ч тоглогчийн стратегийн хувьд INболон тоглоомын үнэтэй тэнцэх ялалт v, тоглогчийн оновчтой стратегитай IN.Ерөнхий байдлыг алдалгүйгээр бид таамаглаж байна v> 0; Энэ нь бүх элементүүдийг хийснээр хүрч болно . Хэрэв тоглогч бол А Bj тоглогчийн аливаа цэвэр стратегийн эсрэг холимог стратегийг ашигладаг IN,дараа нь тэр авдаг дундаж ялалт , эсвэл ялах математикийн хүлээлт (жишээ нь элементүүд j-Готөлбөрийн матрицын багануудыг A1, A2,..Ai,..Am стратегиудын харгалзах магадлалаар нэр томъёогоор үржүүлж үр дүнг нэмнэ).

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

Тэгш бус байдал бүрийг тоогоор хувааж болно. Шинэ хувьсагчдыг танилцуулъя: . Дараа нь систем хэлбэрийг авна

Тоглогчийн зорилго А -баталгаатай ялалтаа нэмэгдүүлэх, өөрөөр хэлбэл. тоглоомын үнэ v.

Тэгш байдлаар хуваахад хувьсагч нь дараах нөхцлийг хангаж байгааг олж мэднэ. Тоглоомын үнийг дээд зэргээр нэмэгдүүлэх vтоо хэмжээг багасгахтай тэнцэнэ , Тиймээс асуудлыг дараах байдлаар томъёолж болно. хувьсагчийн утгыг тодорхойлох , ээжИнгэснээр тэдгээр нь шугаман хязгаарлалтыг хангана(*) Мөн шугаман функц байх үед (2*) хамгийн бага хэмжээнд хэрэглэнэ.

Энэ бол шугаман програмчлалын асуудал юм. (1*)–(2*) асуудлыг шийдэж бид оновчтой шийдлийг олж авна ба оновчтой стратеги .

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

Энэ нь тоглогчийн дундаж алдагдалаас үүдэлтэй INТоглогч ямар ч цэвэр стратеги хэрэглэснээс үл хамааран тоглоомын үнээс хэтрэхгүй А.

Хэрэв бид (4*) гэж тэмдэглэвэл тэгш бус байдлын системийг олж авна.

Хувьсагч нь нөхцөлийг хангаж байна.

Тоглоом дараагийн асуудал руу орлоо.

Хувьсах утгыг тодорхойлох , тэгш бус байдлын системийг хангадаг (5*)Тэгээд шугаман функцийг нэмэгдүүлэх

Шугаман програмчлалын асуудлын шийдэл (5*), (6*) нь оновчтой стратегийг тодорхойлдог. Үүний зэрэгцээ, тоглоомын үнэ. (7*)

(1*), (2*) ба (5*), (6*) асуудлуудын өргөтгөсөн матрицуудыг эмхэтгэснээр бид нэг матрицыг нөгөөгөөс нь шилжүүлэн суулгасан эсэхийг шалгана.

Тиймээс шугаман програмчлалын бодлого (1*), (2*) ба (5*), (6*) нь харилцан давхар байна. Мэдээжийн хэрэг, тодорхой асуудлын оновчтой стратегийг тодорхойлохдоо шийдэл нь бага хөдөлмөр шаарддаг харилцан давхар бодлогын аль нэгийг сонгож, хоёрдмол байдлын теоремуудыг ашиглан нөгөө асуудлын шийдлийг олох хэрэгтэй.

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

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

1. Эдийн засгийн үйл ажиллагааны судалгааны сэдэв, зорилт. Үйл ажиллагааны судалгааны онолын үндсэн ойлголтууд.

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

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

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

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

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

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

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

Эдгээрийн хослол нь уусмал үүсгэдэг параметрүүдийг уусмалын элементүүд гэж нэрлэдэг.

Боломжит шийдлүүдийн багц нь тогтмол бөгөөд зөрчих боломжгүй нөхцөлүүдийг өгдөг.

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

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

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

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

Сүлжээний загварын үндсэн ойлголтууд:

Үйл явдал, ажил, зам.

Үйл явдал нь нэг буюу хэд хэдэн ажлын үр дүн юм. Тэдэнд хугацаа сунгагдаагүй байна.

Зам гэдэг нь эхлэл ба төгсгөлийн оройг холбосон бие биенээ дагасан ажлын гинжин хэлхээ юм.

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

3. Сүлжээний диаграммыг байгуулах, зохион байгуулах.

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

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

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

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

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

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

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

Ажлын өртөг гэдэг нь энэ ажлын үргэлжлэх хугацаа, нөхцлөөс хамааран түүнийг дуусгахад шаардагдах шууд зардал юм.

Нөөц нь тухайн ажлыг гүйцэтгэхэд шаардлагатай биет нэгжийн хэрэгцээгээр тодорхойлогддог.

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

Үйл явдал гэдэг нь нэг буюу хэд хэдэн дараагийн ажлын байрыг эхлүүлэхэд шаардлагатай бөгөөд хангалттай нэг буюу хэд хэдэн ажлын байрыг дуусгах явдал юм. Үйл явдал бүрт код гэж нэрлэгддэг дугаар өгөгддөг. Ажил бүр нь хоёр үйл явдлаар тодорхойлогддог: i-ээр тэмдэглэгдсэн эхлэлийн код, j-ээр тэмдэглэгдсэн төгсгөлийн үйл явдлын код.

Өмнөх ажилгүй үйл явдлуудыг анхдагч гэж нэрлэдэг; дараагийн үйл явдлууд нь төгсгөлтэй байдаг.

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

2 Сүлжээг байгуулахдаа дараах асуудлууд шийдэгдэнэ.

Энэ ажлыг эхлүүлэхийн тулд ямар ажил(ууд) хийгдсэн байх ёстой;

Энэ ажилтай зэрэгцэн ямар ажил хийхийг зөвлөж байна;

3 Сүлжээний эхний хуваарийг сүлжээг бүрдүүлдэг ажлын үргэлжлэх хугацааг харгалзахгүйгээр хийсэн.

4 Графикийн хэлбэр нь энгийн бөгөөд нүдэнд харагдахуйц хялбар байх ёстой.

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

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

4. Сүлжээний диаграммын эгзэгтэй зам. Цагийн нөөц. Сүлжээний хуваарийн дагуу үйл явдлын эрт болон хожуу огноо, ажил.

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

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

Сүлжээний диаграммыг зурахдаа хоёр ойлголт онцгой ач холбогдолтой:

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

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

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

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

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

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

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

5. Динамик програмчлал. Беллманы оновчтой байдал ба хяналтын зарчим.

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

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

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

6. Аж ахуйн нэгжүүдийн хооронд хөрөнгө хуваарилах асуудал.

Динамик програмчлалын аргыг ашиглан оновчтой хяналтыг бий болгох журмыг урьдчилсан ба эцсийн гэсэн хоёр үе шатанд хуваадаг гэж бид хэлж чадна. Урьдчилсан шатанд алхам бүрийн хувьд системийн төлөв байдлаас (өмнөх алхмуудын үр дүнд хүрсэн) ТӨҮГ-ыг тодорхойлдог бөгөөд үүнээс эхлэн үлдсэн бүх үе шат дахь нөхцөлт оновчтой ашгийг мөн төлөв байдлаас хамаарна. . Эцсийн шатанд алхам бүрийн оновчтой хяналтыг (болзолгүй) тодорхойлно. Урьдчилсан (нөхцөлт) оновчлолыг урвуу дарааллаар алхам алхмаар гүйцэтгэдэг: сүүлчийн алхамаас эхний шат хүртэл; эцсийн (болзолгүй) оновчлол - мөн үе шаттайгаар, гэхдээ байгалийн дарааллаар: эхний алхамаас сүүлчийнх хүртэл. Оновчлолын хоёр үе шатаас эхнийх нь харьцуулшгүй чухал бөгөөд цаг хугацаа их шаарддаг. Эхний үе шатыг дуусгасны дараа хоёр дахь шатыг дуусгахад ямар ч бэрхшээл гарахгүй: эхний шатанд бэлтгэсэн зөвлөмжийг "унших" л үлдлээ.

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

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

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

Шалгуур нь сонирхлын бүлгийн дараагийн бүтээгдэхүүний MAX үнэ f.

Хяналттай хувьсагч нь f бүлгийн бүх бүтээгдэхүүний үнэ юм.

Ерөнхий параметрийн бус аргыг ашиглан бидний таамаглах асуудлын хязгаарлалтууд нь:

а) тэгш бус байдлын систем (хэрэглэгчийн зан үйлийн оновчтой байдалд тавих хязгаарлалт) (4.2-ыг үзнэ үү. Ерөнхий параметрийн бус аргын хүрээнд урьдчилан таамаглах);

б) хяналттай хувьсагчдын сөрөг бус байх шаардлага (бидний урьдчилан таамаглах асуудалд бид f бүлгийн бүтээгдэхүүний үнэ сүүлийн үеийн үнийн дүнгийн 80% -иас доош буухгүй байхыг шаардах болно);

в) тэгш байдлын хэлбэрийн төсвийн хязгаарлалт - f бүлгийн бүтээгдэхүүн худалдан авах зардлын хэмжээ тогтмол байх шаардлага (жишээлбэл, 15% -ийн инфляцийг харгалзан).

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

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

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

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

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

(2.3) нөхцлийн дагуу (2.2) систем тууштай, шийдлийн олон өнцөгт нь хязгаарлагдмал байна гэж үзье. Дээр дурдсанчлан (2.2) ба (2.3) тэгш бус байдал бүр нь хилийн шугамтай хагас хавтгайг тодорхойлдог: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Z-ийн тогтмол утгуудын шугаман функц (2.1) нь шулуун шугамын тэгшитгэл юм: C1x1 + C2x2 = const. Хязгаарлалтын системийн (2.2) шийдлүүдийн олон өнцөгт ба Z = 0 үед шугаман функцийн (2.1) графикийг байгуулъя (Зураг 2.1). Дараа нь тавьсан шугаман програмчлалын асуудлыг дараах тайлбарыг өгч болно. С1х1 + С2х2 = const тулгуур шугам ба Z функц хамгийн багадаа хүрэх шийдлийн олон өнцөгтийн цэгийг ол.

Z = C1x1 + C2x2-ийн утгууд нь N = (C1, C2) векторын чиглэлд нэмэгдэх тул бид Z = 0 шулуун шугамыг X векторын чиглэлд өөртэйгөө параллель шилжүүлнэ. Зураг. 2.1-ээс харахад шулуун шугам нь шийдлийн олон өнцөгттэй (А ба С цэгүүд дээр) хоёр удаа жишиг шугам болж, А цэг дээр хамгийн бага утгыг авна. AB ба AE шулуун шугамын тэгшитгэлийн систем.

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

Тохиолдол 1. C1x1 + C2x2 = const шулуун нь N векторын чиглэлд эсвэл эсрэгээрээ хөдөлж, шийдлийн олон өнцөгтийг байнга огтолж байгаа бөгөөд ямар ч цэг дээр тулгуур биш юм. Энэ тохиолдолд шугаман функц нь уусмалын олон өнцөгт дээр ба доор хязгаарлагдахгүй (Зураг 2.2).

Тохиолдол 2. Шулуун шугам нь хөдөлж байгаа хэдий ч шийдлийн олон өнцөгттэй харьцуулахад дэмжлэг болдог (Зураг 2.2, a - 2.2, в). Дараа нь талбайн төрлөөс хамааран шугаман функцийг дээрээс нь хязгаарлаж, доороос нь хязгааргүй (Зураг 2.2, а), доороос нь хязгаарлаж, дээрээс нь хязгааргүй (Зураг 2.2, б), эсвэл доороос нь хоёуланг нь хязгаарлаж болно. дээрээс (Зураг .2.2, в).

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

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

Энэ арга нь бүх нийтийнх бөгөөд шугаман програмчлалын аливаа асуудалд каноник хэлбэрээр хэрэглэгдэх боломжтой. Энд байгаа хязгаарлалтын систем нь үл мэдэгдэх тоо нь тэгшитгэлийн тооноос их байх шугаман тэгшитгэлийн систем юм. Хэрэв системийн зэрэглэл нь r бол бид үл мэдэгдэх r үл мэдэгдэхийг сонгож болно. Тодорхой байхын тулд бид эхний дараалсан үл мэдэгдэх X1, X2, ..., Xr-г сонгосон гэж үздэг. Тэгвэл бидний тэгшитгэлийн системийг ингэж бичиж болно

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

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

Ижил төрлийн бүтээгдэхүүний m гарах цэг ("нийлүүлэгч") болон хэрэглээний n цэг ("хэрэглэгч") байдаг. Зүйл бүрийн хувьд дараахь зүйлийг тодорхойлно.

ai - i-р ханган нийлүүлэгчийн үйлдвэрлэлийн хэмжээ, i = 1, …, m;

вj - j-р хэрэглэгчийн эрэлт, j= 1,…,n;

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

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

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

Тээврийн төлөвлөгөө нь тээвэрлэлтийн хэмжээг хэлнэ, i.e. i-р ханган нийлүүлэгчээс j-р хэрэглэгч хүртэл тээвэрлэх шаардлагатай барааны тоо хэмжээ. Бодлогын математик загварыг бүтээхийн тулд xij, i= 1,..., n, j= 1,..., m m·n хувьсагчийг оруулах шаардлагатай бөгөөд xij хувьсагч бүр цэгээс тээвэрлэлтийн эзэлхүүнийг илэрхийлнэ. Bj цэг хүртэл. X = (xij) хувьсагчдын багц нь асуудлыг томъёолсны үндсэн дээр олох шаардлагатай төлөвлөгөө байх болно.

Энэ нь хаалттай, нээлттэй тээврийн асуудлыг (CTZ) шийдвэрлэх нөхцөл юм.

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

Хэрэв энэ тэгш бус байдлыг хатуу хангасан бол асуудлыг "нээлттэй" эсвэл "тэнцвэргүй" гэж нэрлэнэ, харин хэрэв байвал асуудлыг "хаалттай" тээврийн бодлого гэж нэрлэх ба (2) хэлбэртэй байна.

Тэнцвэрийн нөхцөл.

Энэ нь хаалттай тээврийн асуудлыг (CTP) шийдвэрлэх нөхцөл юм.

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

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

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

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

3. Хэрэглээний цэг бүрт бүтээгдэхүүний шаардлагыг мэддэг байх ёстой.

4. Нийт нийлүүлэлт нь нийт эрэлттэй тэнцүү байх ёстой.

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

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

Үе шат 2. Үүссэн нөөцийн хуваарилалтыг оновчтой эсэхийг шалгах

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

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

Энэ давталтын процессыг оновчтой шийдэл гаргах хүртэл давтана.

12. Бараа материалын менежментийн загварууд.

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

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

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

тодорхойлогч;

магадлал.

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

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

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

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

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

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

эргэлтийн хөрөнгө, агуулахын талбай гэх мэт хязгаарлалт байгаа эсэх.

13. Дарааллын систем (QS) ба тэдгээрийн үр дүнтэй байдлын үзүүлэлтүүд.

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

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

Дарааллын систем нь нэг суваг эсвэл олон суваг байж болно.

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

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

14. Магадлалын төлөвийн динамик тэгшитгэл (Колмогоровын тэгшитгэл). Мужуудын магадлалыг хязгаарлах.

Колмогоров-Чэпманы тэгшитгэлийг s = 0-д s-тэй хамааруулан албан ёсоор ялгаж, Колмогоровын шууд тэгшитгэлийг олж авна.

t = 0 үед Колмогоров-Чапманы тэгшитгэлийг t-тэй хамааруулан албан ёсоор ялгаж, урвуу Колмогоровын тэгшитгэлийг олж авна.

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

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

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

Тодорхойлсон нөхцөл хангагдсан гэж үзье, иймээс хязгаарлах магадлал бий:

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

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

15. Үхэл ба нөхөн үржихүйн үйл явц.

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

Нөхөн үржихүйн λi(t) урсгалыг Пуассон урсгал гэж нэрлэх бөгөөд энэ нь X(t) функцийг нэмэгдүүлэхэд хүргэдэг. Үүний дагуу μi(t) нь X(t) функцийг бууруулахад хүргэдэг үхлийн урсгал юм.

Графикаас Колмогоровын тэгшитгэлийг байгуулъя.

Хэрэв урсгал нь хязгаарлагдмал төлөвтэй бол:

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

Цэвэр нөхөн үржихүйн үйл явц нь үхлийн бүх урсгалын эрчим нь тэгтэй тэнцүү байх үхэл ба нөхөн үржихүйн үйл явц юм.

Цэвэр үхлийн үйл явц нь бүх нөхөн үржихүйн урсгалын эрч хүч тэгтэй тэнцүү байх үхэл ба нөхөн үржихүйн үйл явц юм.

16. Алдаатай дарааллын системүүд.

Дарааллын онолын хүрээнд авч үзэж буй асуудлуудын хамгийн энгийн нь алдаа, алдагдал бүхий нэг сувгийн QS-ийн загвар юм.

Энэ тохиолдолд сувгийн тоо 1 () байна гэдгийг тэмдэглэх нь зүйтэй. Энэ суваг нь Пуассон хүсэлтийн урсгалыг хүлээн авдаг бөгөөд эрч хүч нь -тэй тэнцүү байна. Цаг хугацаа нь эрчимжилтэд нөлөөлдөг:

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

17. Хүлээлт бүхий дарааллын системүүд.

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

Хязгаарлагдмал дарааллын урттай систем. Эхлээд дараалалд байгаа газруудын тоог m-ээр хязгаарласан гэж үзье, өөрөөр хэлбэл, хэрэв дараалалд аль хэдийн m програм байгаа үед програм ирвэл системд үйлчлэхгүй орхино. Ирээдүйд m-ийг хязгааргүй рүү чиглүүлснээр бид дарааллын уртыг хязгаарлахгүйгээр нэг сувгийн QS-ийн шинж чанарыг олж авах болно.

Бид QS-ийн төлөвүүдийг систем дэх програмуудын тоогоор (үйлчилгээнд хамрагдаж байгаа болон хүлээж байгаа үйлчилгээгээр) дугаарлана.

- суваг үнэгүй;

— суваг завгүй, дараалал байхгүй;

— суваг завгүй, нэг хүсэлт дараалалд байна;

—суваг завгүй, k - 1 хүсэлт дараалалд байна;

— суваг завгүй, олон тонн програмууд дараалалд байна.

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

Матрицын тоглоом гэдэг нь хоёр тоглогчийн төгсгөлтэй тэг нийлбэртэй тоглоом бөгөөд 1-р тоглогчийн ашиг нь матриц хэлбэрээр тодорхойлогддог (матрицын мөр нь 2-р тоглогчийн ашигласан стратегийн тоотой тохирч, багана нь - матрицын мөр ба баганын огтлолцол дээрх 2-р тоглогчийн ашигласан стратегийн тоо нь ашигласан стратегид тохирсон 1-р тоглогчийн ашиг юм).

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

Хоёр тоглогчтой тэг нийлбэртэй матриц тоглоомыг дараах хийсвэр хоёр тоглогчтой тоглоом гэж ойлгож болно.

Эхний тоглогч m стратеги i = 1,2,...,m, хоёр дахь тоглогч n стратеги j = 1,2,...,n. Хос стратеги (i,j) бүр нь aij тоотой холбоотой бөгөөд энэ нь эхний тоглогч өөрийн i-р стратегийг хүлээн зөвшөөрвөл 2-р тоглогчийн зардлаар 1-р тоглогчийн ашиг, 2-р стратеги нь түүний j-р стратегийг хүлээн зөвшөөрөхийг илэрхийлдэг.

Тоглогч бүр нэг нүүдэл хийдэг: 1-р тоглогч өөрийн i-р стратегийг (i=), 2-р стратегиа (j=) сонгоно, үүний дараа 1-р тоглогч 2-р тоглогчийн зардлаар aij ашиг авна (хэрэв aij бол).

Тоглогчийн стратеги бүр i=; j = ихэвчлэн цэвэр стратеги гэж нэрлэдэг.

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

Тиймээс хэрэв 1-р тоглогч m цэвэр стратеги 1,2,...,m байвал түүний холимог стратеги x нь харилцааг хангасан x = (x1,..., xm) тооны багц болно.

xi³ 0 (i= 1,m), =1.

Үүний нэгэн адил, n цэвэр стратегитай 2-р тоглогчийн хувьд холимог стратеги y нь тоонуудын багц юм.

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

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

Цэвэр стратеги бол холимог стратегийн онцгой тохиолдол юм. Үнэхээр холимог стратегид 1-р магадлал бүхий аль нэг i-р цэвэр стратегийг хэрэглэвэл бусад бүх цэвэр стратеги хэрэглэхгүй. Мөн энэ 1-р цэвэр стратеги нь холимог стратегийн онцгой тохиолдол юм. Нууцлалыг хадгалахын тулд тоглогч бүр өөр тоглогчийн сонголтоос үл хамааран өөрийн стратегийг хэрэгжүүлдэг.

19. Матрицын тоглоомыг шийдвэрлэх геометрийн арга.

2xn эсвэл nx2 хэмжээтэй тоглоомуудын шийдэл нь тодорхой геометрийн тайлбар хийх боломжийг олгодог. Ийм тоглоомыг графикаар шийдэж болно.

Абсцисса тэнхлэгийн дагуу XY хавтгай дээр бид A1A2 нэг сегментийг зурна (Зураг 5.1). Хэсгийн цэг бүрт U = (u1, u2) холимог стратеги оноож үзье. Түүнчлэн зарим нэг завсрын цэг U цэгээс энэ сегментийн баруун төгсгөл хүртэлх зай нь A1 стратегийг сонгох магадлал u1, зүүн төгсгөл хүртэлх зай нь A2 стратегийг сонгох магадлал u2 юм. А1 цэг нь цэвэр стратеги А1, А2 цэг нь цэвэр А2 стратегитай тохирч байна.

A1, A2 цэгүүдэд бид перпендикуляруудыг сэргээж, тоглогчдын ялалтыг тэдэнд оруулна. Эхний перпендикуляр дээр (OY тэнхлэгтэй давхцаж) бид А1 стратегийг ашиглах үед А тоглогчийн үр ашгийг, хоёрдугаарт - А2 стратегийг ашиглах үед харуулав. Хэрэв А тоглогч А1 стратегийг ашигладаг бол В тоглогчийн В1 стратегийн ашиг нь 2, В2 стратегитай бол 5-тай тэнцүү байна. OY тэнхлэг дээрх 2 ба 5 тоо нь B1 ба B2 цэгтэй тохирч байна. Үүний нэгэн адил, хоёр дахь перпендикуляр дээр бид B"1 ба B"2 цэгүүдийг олдог (6 ба 4 олз).

B1 ба B"1, B2 ба B"2 цэгүүдийг холбосноор бид хоёр шулуун шугамыг олж авдаг бөгөөд үүнээс OX тэнхлэг хүртэлх зай нь харгалзах стратегийн аль ч хослолын дундаж үр өгөөжийг тодорхойлдог.

Жишээлбэл, B1B"1 сегментийн аль ч цэгээс OX тэнхлэг хүртэлх зай нь A1 ба A2 стратеги (u1 ба u2 магадлалтай) болон В тоглогчийн В1 стратегийн аль ч хослолын хувьд А тоглогчийн дундаж үр ашгийг тодорхойлдог.

B1MB"2 тасархай шугаманд хамаарах цэгүүдийн ординатууд нь А тоглогч ямар нэгэн холимог стратеги ашиглах үед хамгийн бага ашиг олохыг тодорхойлдог. Энэ хамгийн бага утга нь M цэг дэх хамгийн том утга учир энэ цэг нь оновчтой стратеги U* = ( ,), түүний ординат нь тоглоомын өртөгтэй тэнцүү v .

М цэгийн координатыг B1B"1 ба B2B"2 шулуунуудын огтлолцох цэгийн координат гэж олно.

Үүнийг хийхийн тулд та шугамын тэгшитгэлийг мэдэх хэрэгтэй. Та хоёр цэгээр дамжин өнгөрөх шугамын тэгшитгэлийн томъёог ашиглан ийм тэгшитгэл үүсгэж болно.

Бодлогынхоо шулуун шугамын тэгшитгэлийг байгуулъя.

B1B"1 мөр: = эсвэл y = 4x + 2.

Шууд B2B"2: = эсвэл y = -x + 5.

Бид системийг олж авна: y = 4x + 2,

Үүнийг шийдье: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Тиймээс U = (2/5, 3/5), v = 22/5.

20. Bimatrix тоглоом.

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

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

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

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

зорилгын тодорхойгүй байдал;

хүрээлэн буй орчны талаарх бидний мэдлэгийн тодорхой бус байдал, энэ үзэгдэлд нөлөөлж буй хүчин зүйлүүд (байгалийн тодорхойгүй байдал);

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

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

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

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

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

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

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

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

хүлээгдэж буй үнэ цэнийн шалгуур;

хүлээгдэж буй үнэ цэнэ ба хэлбэлзлийн хослолууд;

мэдэгдэж буй хязгаарын түвшин;

ирээдүйн хамгийн их магадлалтай үйл явдал.

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

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

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

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

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

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

Заримдаа санамсаргүй хүчин зүйл дагалддаг мэс засал нь ийм зорилгыг баримталдаг А, энэ нь бүрэн хүрч болох эсвэл огт хүрэхгүй (“тийм-үгүй” гэх мэт). Дараа нь энэ зорилгодоо хүрэх магадлалыг үр ашгийн үзүүлэлт болгон сонгоно х(А). (Хэрэв х(А) = 0 эсвэл 1, дараа нь бид кибернетикт мэдэгдэж буй "хар хайрцаг" асуудалд хүрнэ.)

Гүйцэтгэлийн үзүүлэлтийг буруу сонгох нь маш аюултай. Амжилтгүй сонгосон шалгуурын дагуу зохион байгуулагдсан үйл ажиллагаа нь үндэслэлгүй зардал, алдагдалд хүргэж болзошгүй юм. (Жишээ нь, "босоо ам" нь аж ахуйн нэгжийн эдийн засгийн үйл ажиллагааг үнэлэх гол шалгуур юм.)

1.3. Үйл ажиллагааны судалгааны асуудлын ерөнхий мэдэгдэл

Үйл ажиллагааны судалгааны асуудлууд нь хоёр ангилалд хуваагдана: a) урагшлах, б) хойшлох.

Шууд даалгаварасуултанд хариулна уу: үр ашгийн үзүүлэлт нь юутай тэнцүү байх вэ? З, хэрэв өгөгдсөн нөхцөлд y  Ютодорхой шийдвэр гарна x  X. Ийм асуудлыг шийдэхийн тулд үр ашгийн үзүүлэлтийг өгөгдсөн нөхцөл, шийдлээр илэрхийлэх боломжийг олгодог математик загварыг бүтээдэг, тухайлбал:

Хаана
заасан хүчин зүйлүүд (анхны өгөгдөл),

хяналтын хувьсагч (шийдвэр),

З- үр ашгийн үзүүлэлт (зорилтот функц),

Ф– хувьсагчдын хоорондох функциональ хамаарал.

Энэ хамаарлыг янз бүрийн загварт өөр өөрөөр илэрхийлдэг. хоорондын хамаарал Тэгээд хязгаарлалтаар ихэвчлэн илэрхийлэгддэг

Хэрэв хамаарлын төрөл Фмэдэгдэж байгаа бол индикатор Зшууд орлуулах замаар олно Тэгээд энэ функцэд .

Урвуу асуудлуудгэсэн асуултанд хариулна уу: эдгээр нөхцөлд яаж шийдлийг сонгох
Ингэснээр гүйцэтгэлийн үзүүлэлт Зхамгийн их (хамгийн бага) руу эргэв. Энэ асуудлыг шийдлийг оновчтой болгох асуудал гэж нэрлэдэг.

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

олох хэрэгтэйийм шийдвэр
үр ашгийн үзүүлэлт З = сонголт:

Энэ томъёог дараах байдлаар уншина. Зоновчтой утга байна
боломжит шийдлүүдийн багцад багтсан бүх шийдлүүдийг авсан X.

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

Үйл ажиллагааны судалгааны асуудал

ОРШИЛ .............................................................................................................................................................................................................................................................................................................................................. ... 3

1. Үйл ажиллагааны судалгааны үндсэн ойлголт, тодорхойлолт ……………..5

2. Үйл ажиллагааны судалгааны асуудлын ерөнхий тодорхойлолт……………………6

Дүгнэлт……………………………………………………………………13

Уран зохиол…………………………………………………………………………………14

Оршил

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

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

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

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

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

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

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

Даалгавар 2. Улирлын чанартай бараа бүтээгдэхүүний тодорхой багцыг борлуулахын тулд түр худалдааны цэгүүдийн сүлжээг бий болгодог. Борлуулалтын хамгийн их эдийн засгийн үр ашгийг хангахын тулд сүлжээний параметрүүдийг сонгох шаардлагатай - цэгүүдийн тоо, тэдгээрийн байршил, боловсон хүчний тоо.

Даалгавар 3. Өгөгдсөн огноогоор тодорхой өвчнийг илрүүлэхийн тулд хүн амын бүлэгт олон нийтийн эрүүл мэндийн үзлэг хийх шаардлагатай. Шалгалтад хамрагдах материал, тоног төхөөрөмж, боловсон хүчнийг хуваарилсан. Ийм үзлэгийн төлөвлөгөөг боловсруулах шаардлагатай - өвчтэй хүмүүсийн хамгийн их хувийг тодорхойлохын тулд эмнэлгийн газруудын тоо, тэдгээрийн байршил, шинжилгээний төрөл, тоог тогтоох шаардлагатай.

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

Өгөгдсөн даалгаврууд нь практикийн өөр өөр чиглэлтэй холбоотой боловч тэдгээр нь нийтлэг шинж чанартай байдаг: тохиолдол бүрт бид зарим талаар ярьж байна. хяналттай үйл явдал (үйл ажиллагаа),тодорхой хөөцөлдөж байна зорилтот. 1-р даалгаварт - энэ нь бүтээгдэхүүний чанарыг хангах үүднээс дээж авах хяналтын зохион байгуулалт юм; 2-р даалгаварт - улирлын чанартай худалдаа эрхлэх зорилгоор түр худалдааны цэгүүдийг зохион байгуулах; 3-р даалгаварт - тохиолдлын хувийг тодорхойлохын тулд олон нийтийн эрүүл мэндийн үзлэг.

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

1. Үйл ажиллагааны судалгааны үндсэн ойлголт, тодорхойлолт

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

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

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

Тайлбар 1. Асуудлын мэдэгдэлд анхаарлаа хандуулах хэрэгтэй: the шийдвэр гаргахүйл ажиллагааны судалгааны хамрах хүрээнээс хэтэрсэн бөгөөд математикийн үндэслэлтэй зүйлээс бусад зүйлийг харгалзан үзэх хариуцлагатай хүн эсвэл бүлэг хүмүүсийн үүрэг юм.

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

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

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

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

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

2. Үйл ажиллагааны судалгааны асуудлын ерөнхий тодорхойлолт

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

тогтмол хүчин зүйлүүд(үйл ажиллагааны нөхцөл), бид нөлөөлж чадахгүй. Тэдгээрийг тэмдэглэе α1, α2, ... ;

хамааралтай хүчин зүйлүүд(шийдлийн элементүүд) x 1, x2, ...;тодорхой хязгаар дотор бид өөрсдийн үзэмжээр сонгож болно.

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

гэж нэрлэгддэг зарим функцээр илэрхийлэгдсэн гүйцэтгэлийн шалгуур зорилтот,хоёр бүлгийн хүчин зүйлээс хамаардаг тул зорилгын функц Зхэлбэрээр бичиж болно

Z= е (x1, x2, ..., α1, α2, ...)

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

Энэ нь юуны түрүүнд том гэдгийг тэмдэглэх нь зүйтэй оновчлолын загваруудын ангилал.Ийм асуудал нь нарийн төвөгтэй системүүд, ялангуяа эдийн засгийн системүүдийн төлөвлөлт, менежментийг оновчтой болгохыг оролдох үед үүсдэг. Оновчлолын асуудлыг ерөнхий хэлбэрээр томъёолж болно. хувьсагчдыг олох x1, x2, ..., x n , тэгш бус байдлын системийг (тэгшитгэл) хангах

g би (x1, x2, x3,..., X n )<= б би , i = 1, 2,..., n (0.1)

Тэгээд зорилгын функцийг хамгийн их (эсвэл хамгийн бага) болгох, i.e.

Z= е (x1, x2, ..., x n ) - м аа (м in ) (0.2)

(Хэрэв байгаа бол хувьсагчдын сөрөг бус байх нөхцөлийг хязгаарлалт (0.1)-д оруулсан болно)

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

Байгаа байг Пбараа, үйлчилгээний төрөл, тэдгээрийн тоо хэмжээ (байгалийн нэгжээр) x1, x2, ..., x n, зохих үнээр х 1, х 2, ..., х nнэгжийн хувьд. Эдгээр бараа, үйлчилгээний нийт өртөг нь ∑ х би x би .

Хэрэглээний түвшин Ззарим функцээр илэрхийлж болно Z= е (x1, x2, ..., x n ) , дуудсан Хэрэглээний функц. Ийм багц бараа, үйлчилгээг олох шаардлагатай байна x1, x2, ..., x n өгсөн орлогын хэмжээ I,руу хамгийн их хэрэглээний түвшинг хангах,тэдгээр.

Z= е (x1, x2, ..., x n ) - м Өө (0.3)

үүнийг өгсөн

∑ х би x би <= I (0.4)

x би >= 0 ( би = 1, 2,..., n ) (0.5)

Үнээс хамаарах энэ асуудлыг шийдэх арга замууд х 1, х 2, ..., х nболон орлогын хэмжээ I, гэж нэрлэдэг эрэлтийн функцууд.

Хэрэглээний асуудал (0.3)-(0.5) болон бусад олон асуудал нь функцийн экстремумыг тодорхойлохын тулд дээр дурдсан ерөнхий бодлогын (0.1)-(0.2) онцгой тохиолдол болох нь ойлгомжтой. Птодорхой хязгаарлалтын дор хувьсагч, i.e. зориулсан даалгавар нөхцөлт экстремум.

Функцүүд байгаа тохиолдолд еТэгээд g би, (0.1)-(0.2) асуудалд дор хаяж хоёр дахин ялгах боломжтой бол бид ашиглаж болно сонгодог оновчлолын аргууд.Гэсэн хэдий ч үйл ажиллагааны судалгаанд эдгээр аргуудыг ашиглах нь маш хязгаарлагдмал, учир нь i хувьсагчийн функцийн нөхцөлт экстремумыг тодорхойлох ажил нь техникийн хувьд маш хэцүү байдаг: арга нь орон нутгийн экстремумыг тодорхойлох боломжийг олгодог бөгөөд олон хэмжээст шинж чанартай байдаг. Түүний хамгийн их (эсвэл хамгийн бага) утгыг (дэлхийн экстремум) тодорхойлох функц нь маш их хөдөлмөр шаарддаг, ялангуяа энэ экстремум нь шийдлийн бүсийн хил дээр боломжтой байдаг тул. Аргументуудын хүчинтэй утгуудын багц нь салангид эсвэл функц байвал сонгодог аргууд огт ажиллахгүй Зхүснэгтэд өгсөн болно. Эдгээр тохиолдолд асуудлыг шийдвэрлэхийн тулд (0.1)-(0.2) аргыг ашигладаг математик програмчлал.

Хэрэв гүйцэтгэлийн шалгуур үзүүлэлт бол Z= е (x1, x2, ..., x n ) (0.2) нь шугаман функц, функцийг илэрхийлнэ g би (x1, x2, x3,..., X n ) хязгаарлалтын системд (0.1) мөн шугаман байдаг бол ийм асуудал нь асуудал болно шугаман програмчлал.Хэрэв агуулгад үндэслэн түүний шийдэл нь бүхэл тоо байх ёстой бол энэ асуудал гарч ирнэ бүхэл тоон шугаман програмчлал.Хэрэв үр ашгийн шалгуур ба (эсвэл) хязгаарлалтын системийг шугаман бус функцээр тодорхойлсон бол бидэнд асуудал байна. шугаман бус програмчлал.Ялангуяа, хэрэв заасан функцууд нь гүдгэр шинж чанартай бол үүссэн асуудал нь асуудал юм гүдгэр програмчлал.

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

Хэрэв үр ашгийн шалгуур (0.2) ба хязгаарлалтын систем (0.1) нь маягтын функцээр тодорхойлогдвол Хамт*( x 1^α 1 )*( x 2^α 2 )...( x n ^α n ) , тэгвэл бидэнд асуудал байна геометрийн програмчлал.Хэрэв функцууд еба/эсвэл g би(0.2) ба (0.1) илэрхийлэлд параметрүүд хамаарах бол бид асуудлыг олж авна параметрийн програмчлал,хэрэв эдгээр функцууд нь санамсаргүй шинж чанартай бол даалгавар стохастик програмчлал.Хэт олон тооны шийдлийн сонголтуудаас болж яг оновчтой алгоритмыг олох боломжгүй бол аргуудыг ашиглана уу. эвристик програмчлал,Таны харж буй сонголтуудын тоог мэдэгдэхүйц бууруулж, оновчтой биш бол практик талаас нь харахад хангалттай сайн шийдлийг олох боломжийг танд олгоно.

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

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

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

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

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

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

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

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

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

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

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

Зорилгын функцийг өөр хоорондоо зөрчилддөг (жишээлбэл, ашиг, зардал) зэрэг олон шалгуураас сонгохын тулд дараахь зүйлийг тодорхойлох шаардлагатай. тэргүүлэх чиглэлшалгуур. гэж тэмдэглэе е 1 (x), f 2 (x), ..., е n (x)(Энд X -нөхцөлт аргумент). Тэдгээрийг эрэмбэлэх буурах дарааллаар байрлуул. Тодорхой нөхцлөөс хамааран үндсэндээ хоёр сонголт байдаг:

Зорилгын функцээр шалгуурыг сонгосон е 1 (x),хамгийн чухал ач холбогдолтой байх;

Хосолсон хувилбарыг авч үзэж байна

е ( x ) = ω 1 * е 1 ( x ) + ω 2 * е 2 ( x ) + …+ ω n * е n ( x ) , (0.6)

Хаана ω 1 , ω 2 , … ω n- зарим коэффициентууд (жин).

Хэмжээ е (X), бүх шалгуурыг тодорхой хэмжээгээр харгалзсан, зорилгын функцээр сонгосон.

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

Олон шалгуурын асуудлыг үр ашгийн нэг шалгуур (зорилго функц) бүхий асуудал болгон бууруулах оролдлого нь ихэнх тохиолдолд хангалттай үр дүнг өгдөггүй. Өөр нэг арга бол зөвшөөрөгдөх шийдлүүдийн багцаас бусад шийдлүүдээс доогуур байгаа илт амжилтгүй шийдлүүдийг хаях явдал юм. бүх шалгуур.Энэ журмын үр дүнд гэж нэрлэгддэг үр дүнтэй(эсвэл " Парето")шийдлүүд, тэдгээрийн багц нь ихэвчлэн анхны хувилбараас хамаагүй бага байдаг. Мөн "буулгалт" шийдлийн эцсийн сонголт (бүх шалгуурын дагуу оновчтой биш, дүрмээр бол байдаггүй, гэхдээ хүлээн зөвшөөрөх боломжтойэдгээр шалгуурын дагуу) тухайн хүн - шийдвэр гаргагчтай үлддэг.

Дүгнэлт

Орчин үеийн математикийн аппаратыг бий болгох, үйл ажиллагааны судалгааны олон чиглэлийг хөгжүүлэхэд Оросын эрдэмтэд ихээхэн хувь нэмэр оруулсан. Канторович, Н.П. Бусленко, Е.С. Вентцел, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин болон бусад олон. Ялангуяа академич Л.В. Канторович 1939 онд фанерын үйлдвэрүүдийн үйл ажиллагааг төлөвлөж эхэлснээр хэд хэдэн асуудлыг шийдсэн: тоног төхөөрөмжийг хамгийн сайн ачих, хамгийн бага алдагдалтай материалыг огтлох, ачааг хэд хэдэн төрлийн тээврийн хэрэгсэлд хуваарилах гэх мэт. Л.В. Канторович нөхцөлт экстремаль асуудлын шинэ ангиллыг боловсруулж, тэдгээрийг шийдвэрлэх бүх нийтийн аргыг санал болгосноор хэрэглээний математикийн шинэ чиглэл болох шугаман програмчлалын үндэс суурийг тавьсан.

Үйл ажиллагааны судалгааг бүрдүүлэх, хөгжүүлэхэд гадаадын эрдэмтэд Р.Акоф, Р.Беллман, Г.Данзиг, Г.Кун, Ж.Нейман, Т.Саати, Р.Черчман, А.Кофман болон бусад эрдэмтэд ихээхэн хувь нэмэр оруулсан.

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

Уран зохиол

1. Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Эдийн засгийн үйл ажиллагааны судалгаа: Их дээд сургуулиудад зориулсан сурах бичиг - М.: ЮНИТИ, 2002.

2. Ventzel E.S. Үйл ажиллагааны судалгаа. Зорилго, зарчим, арга зүй - М.: Наука, 1980.

3. Горелик В.А., Ушаков И.А. Үйл ажиллагааны судалгаа. - М.: Механик инженер, 1986.

И.Н. Слинкин

Сурган хүмүүжүүлэх их дээд сургуулийн оюутнуудад зориулсан сурах бичиг

Компьютерийн шинжлэх ухааны чиглэлээр мэргэшсэн

Шадринск, 2003 он

Слинкина I.N.

Үйл ажиллагааны судалгаа. Сургалт, арга зүйн гарын авлага. – Шадринск: Шадринскийн Улсын сурган хүмүүжүүлэх дээд сургуулийн хэвлэлийн газар, 2002. - 106 х.

Слинкина I.N. – Сурган хүмүүжүүлэх ухааны нэр дэвшигч

Сурах бичигт Үйл ажиллагааны судалгааны хичээлийн онолын хэсгийг оруулсан болно. Энэ нь "Мэдээлэл зүй" мэргэжлээр суралцаж буй факультетийн өдрийн болон хагас цагийн оюутнуудад зориулагдсан.

© Шадринскийн улсын сурган хүмүүжүүлэх дээд сургууль

© Slinkina I.N., 2002

“Үйл ажиллагааны судалгаа” хичээлийн нэгжийн асуултууд 5

1.1. Үйл ажиллагааны судалгааны сэдэв, даалгавар 7

1.2. Үйл ажиллагааны судалгааны үндсэн ойлголт, зарчим 8

1.3. Үйлдлийн математик загварууд 10

1.4. Шугаман програмчлалын тухай ойлголт 12

1.5. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Нөөцийг хамгийн сайн ашиглах асуудал 13

1.6. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Оновчтой технологи сонгох асуудал 15

1.7. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Холимог асуудал 16

1.8. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Тээврийн асуудал 17

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

1.10. 21 хувиргах арга

1.11. Каноник хэлбэрт шилжих 22

1.12. Бичлэгийн тэгш хэмтэй хэлбэрт шилжих 25

2.1. Шугаман програмчлалын бодлогын геометрийн тайлбар 28

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

2.3. Шугаман програмчлалын асуудлын шийдлийн шинж чанарууд 34

2.4. Симплекс аргын ерөнхий санаа 35

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

2.6. Лавлах төлөвлөгөөний оновчтой байдлын тэмдэг. Энгийн хүснэгт 40

2.7. Хамгийн муу тохиолдлын лавлагаа төлөвлөгөөнд шилжих. 44

2.8. Энгийн хувиргалт 46

2.9. Альтернатив оновчтой (жишиг төлөвлөгөөний багцын хязгааргүй байдлын тэмдэг) 51

2.10. Зорилгын функцийн хязгааргүй байдлын тэмдэг 52

2.11. доройтлын тухай ойлголт. Симплекс аргын монотон ба хязгаарлагдмал байдал. Гогцоо 53

2.12. Тэгш хэмт шугаман програмчлалын бодлогын хоёрдмол байдлын тухай ойлголт 54

3.1. Тэгш бус хос бодлого 57

3.2. Тээврийн асуудлын нээлттэй ба хаалттай загвар 61

3.3. Анхны жишиг төлөвлөгөөний барилгын ажил. Баруун хойд булангийн дүрэм 63

3.4. Анхны жишиг төлөвлөгөөний барилгын ажил. Хамгийн бага элементийн дүрэм 64

3.5. Анхны жишиг төлөвлөгөөний барилгын ажил. Фогелийн арга 64

3.6. Боломжит арга 65

3.7. Хүчин чадлын хязгаарлалттай тээврийн асуудлыг шийдвэрлэх 69

3.8. Дискрет програмчлалын асуудлын жишээ. Чингэлэг тээвэрлэлтийн асуудал. Даалгаврын асуудал 71

3.9. Дискрет оновчлолын аргын мөн чанар 72

3.10. Гүдгэр програмчлалын асуудал 74

3.11. Лагранжийн үржүүлэгчийн арга 75

3.12. Градиент аргууд 77

4.1. Торгуулийн арга, саад тотгорын чиг үүрэг 78

4.2. Динамик програмчлал. Үндсэн ойлголтууд. Шийдлийн аргын мөн чанар 79

4.3. Стохастик програмчлал. Үндсэн ойлголтууд 81

4.4. Тэг нийлбэртэй матриц тоглоом 83

4.5. Цэвэр ба холимог стратеги, тэдгээрийн шинж чанарууд 85

4.6. Цэвэр ба холимог стратегийн шинж чанарууд 88

4.7. Матриц тоглоомыг ZLP 92 болгож бууруулж байна

4.8. Дарааллын онолын асуудлууд. Дарааллын системийн ангилал 94

4.9. Үйл явдлын урсгал 96

4.10. Үхэл ба нөхөн үржихүйн схем 97

4.11. Бяцхан Формула 99

4.12. Хамгийн энгийн дарааллын системүүд 101

"Үйл ажиллагааны судалгаа" хичээлийн блокуудад зориулсан асуултууд

Блок 1

1. Үйл ажиллагааны судалгааны сэдэв, зорилт.

2. Үйл ажиллагааны судалгааны үндсэн ойлголт, зарчим.

3. Үйлдлүүдийн математик загварууд.

4. Шугаман програмчлалын тухай ойлголт.

5. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Даалгавар

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

7. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Холимогтой холбоотой асуудал.

8. Эдийн засгийн шугаман програмчлалын асуудлын жишээ. Тээврийн асуудал.

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

10. Хөрвүүлэх аргууд.

11. Каноник хэлбэрт шилжих.

12. Бичлэгийн тэгш хэмт хэлбэрт шилжих.

2-р блок

1. Шугаман програмчлалын бодлогын геометрийн тайлбар.

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

3. Шугаман програмчлалын асуудлын шийдлийн шинж чанарууд.

4. Симплекс аргын ерөнхий санаа.

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

6. Жишиг төлөвлөгөөний оновчтой байдлын тэмдэг. Энгийн хүснэгтүүд.

7. Хамгийн муу биш лавлагаа төлөвлөгөөнд шилжих.

8. Энгийн хувиргалт.

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

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

11. доройтлын тухай ойлголт. Симплекс аргын монотон ба хязгаарлагдмал байдал. Гогцоо.

12. Тэгш хэмт шугаман програмчлалын бодлогын хоёрдмол байдлын тухай ойлголт.

Блок 3

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

2. Тээврийн асуудлын нээлттэй, хаалттай загварууд.

3. Анхны жишиг төлөвлөгөөг байгуулах. "Баруун хойд булан" дүрэм.

4. Анхны жишиг төлөвлөгөөг байгуулах. Хамгийн бага элементийн дүрэм.

5. Анхны жишиг төлөвлөгөөг байгуулах. Фогелийн арга.

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

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

8. Дискрет програмчлалын асуудлын жишээ. Чингэлэг тээвэрлэлтийн асуудал. Даалгаврын асуудал.

9. Дискрет оновчлолын аргын мөн чанар.

10. Гүдгэр програмчлалын бодлого.

11. Лагранжийн үржүүлэгчийн арга.

12. Градиент аргууд.

4-р блок

1. Торгууль, саад тотгорын чиг үүргийн арга.

2. Динамик програмчлал. Үндсэн ойлголтууд. Шийдлийн аргуудын мөн чанар.

3. Стохастик програмчлал. Үндсэн ойлголтууд.

4. Тэг нийлбэртэй матрицтай тоглоомууд.

5. Цэвэр ба холимог стратеги.

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

7. Матрицын тоглоомыг PLP болгон багасгах

8. Дарааллын онолын асуудлууд. Дарааллын системийн ангилал.

9. Үйл явдлын урсгал.

10. Үхэл ба нөхөн үржихүйн схем.

11. Литлийн томьёо.

12. Хамгийн энгийн дарааллын системүүд.

Блок 1.

Үйл ажиллагааны судалгааны сэдэв, даалгавар

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

Практикийн хэрэгцээ шаардлага нь "үйл ажиллагааны судалгаа" гэсэн нэрээр эвтэйхэн хослуулсан шинжлэх ухааны тусгай аргуудыг бий болгосон.

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

Тодорхой зорилгод хүрэхийн тулд ямар нэгэн арга хэмжээ авцгаая. Арга хэмжээг зохион байгуулж буй хүн (эсвэл бүлэг хүмүүс) үргэлж сонгох эрх чөлөөтэй байдаг: үүнийг ямар нэгэн байдлаар зохион байгуулж болно. Шийдвэр нь зохион байгуулагчид байгаа олон боломжуудаас сонголт хийх явдал юм.

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

Даалгавар 1.Нөөцийг хамгийн сайн ашиглах тухай.

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

Даалгавар 2.Холимогуудын тухай.

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

Даалгавар 3.Тээврийн асуудал.

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

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

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

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

Үйл ажиллагааны судалгааны үндсэн ойлголт, зарчим

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

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

Тодорхойлолт:Шийдвэрлэх параметрүүдээс хамааран аливаа тодорхой сонголтыг шийдвэр гэж нэрлэдэг.

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

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

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

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

Тодорхойлолт:Эдгээрийн хослол нь уусмал үүсгэдэг параметрүүдийг уусмалын элементүүд гэж нэрлэдэг.

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

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

Үр ашгийн хувьд янз бүрийн шийдлүүдийг харьцуулахын тулд үр ашгийн үзүүлэлт (зорилго функц) гэж нэрлэгддэг тоон шалгууртай байх хэрэгтэй. Энэ үзүүлэлт нь үйл ажиллагааны зорилтот чиглэлийг тусгасан байхаар сонгогддог. Зорилгодоо хүрэхэд хамгийн их хувь нэмэр оруулах хамгийн сайн шийдлийг авч үзэх болно. Гүйцэтгэлийн үзүүлэлт Z-ийг сонгохын тулд эхлээд асуудлын шийдэл нь юунд хүргэх ёстойг тодорхойлох ёстой. Шийдлийг сонгохдоо үр ашгийн үзүүлэлт Z-ийг хамгийн их эсвэл хамгийн бага болгож хувиргадаг шийдлийг илүүд үздэг. Жишээлбэл, би үйл ажиллагаанаас олох орлогыг нэмэгдүүлэхийг хүсч байна; хэрэв үр ашгийн үзүүлэлт нь зардал байвал тэдгээрийг хамгийн бага хэмжээнд хүртэл бууруулахыг зөвлөж байна.

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

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

Даалгавар 1.Нөөцийг хамгийн сайн ашиглах тухай.

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

Даалгавар 2.Холимогуудын тухай.

Асуудлыг томъёолоход санал болгож буй үр ашгийн байгалийн үзүүлэлт бол хольцын тогтоосон шинж чанарыг хадгалах шаардлагатай (мин Z) хольцод шаардлагатай бүтээгдэхүүний үнэ юм.

Даалгавар 3.Тээврийн асуудал.

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