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

Хэд хэдэн цэгийн сегментийн тухай ойлголтыг нэгтгэх нь тэдгээрийн гүдгэр шугаман хослол юм.

X цэг гэж нэрлэдэг гүдгэр шугаман хослолоноо, нөхцөл хангагдсан бол

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

Гүдгэр олон талт дүрслэлийн талаарх дараах теоремыг бид баталж чадна.

Теорем 1.1. Гүдгэр n хэмжээст олон өнцөгт нь түүний булангийн цэгүүдийн гүдгэр шугаман хослол юм.

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

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

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

Матрицын бичлэгийн хэлбэр:

Энд ХАМТ- эгнээ матриц, А- системийн матриц, X– хувьсагчдын матриц багана, IN– чөлөөт гишүүдийн матриц багана:

Бичлэгийн вектор хэлбэр:

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

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

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

Нотолгоо:Болъё - PLP-ийн хоёр боломжит шийдлийг матриц хэлбэрээр өгсөн. Дараа нь . Уусмалын гүдгэр шугаман хослолыг авч үзье, i.e.

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

өөрөөр хэлбэл шийдэл Xсистемийг хангасан (1.3). Гэхдээ тэр цагаас хойш X>0, өөрөөр хэлбэл. шийдэл нь сөрөг бус нөхцөлийг хангадаг.

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

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

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

Нотолгоо:Уусмалын олон өнцөгт нь хязгаарлагдмал байна гэж бид таамаглах болно. Түүний булангийн цэгүүдийг үүгээр тэмдэглэе , бөгөөд оновчтой шийдэл нь дамждаг X*. Дараа нь F(X*)³ F(X)бүх онооны хувьд Xуусмалын олон талт. Хэрэв X*нь булангийн цэг бол теоремын эхний хэсэг нотлогдоно.

Ингэж жүжиглэе X*нь булангийн цэг биш тул теорем 1.1 дээр үндэслэсэн болно X*уусмалын олон талт булангийн цэгүүдийн гүдгэр шугаман хослолоор төлөөлж болно, i.e.

Учир нь F(X)нь шугаман функц юм, бид олж авна

Энэ задралд бид утгуудын дунд хамгийн ихийг сонгоно. Энэ нь булангийн цэгтэй тохирч байгаарай Xk(1 фунт к£ R); гэж тэмдэглэе М,тэдгээр. . (1.5) илэрхийлэл дэх утга бүрийг энэ хамгийн их утгаар орлуулъя М.Дараа нь

Таамаглалаар X* нь нэг талаас оновчтой шийдэл боловч нөгөө талаас энэ нь батлагдсан
F(X*)£ М,тиймээс, , хаана Xk- булангийн цэг. Тиймээс булангийн цэг бий Xk, шугаман функц нь хамгийн их утгыг авдаг.

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

Болъё X– эдгээр булангийн цэгүүдийн гүдгэр шугаман хослол, өөрөөр хэлбэл.

Энэ тохиолдолд функцийг өгсөн F(X)– шугаман, бид авдаг

тэдгээр. шугаман функц Фдурын цэг дээр хамгийн их утгыг авдаг X, энэ нь булангийн цэгүүдийн гүдгэр шугаман хослол юм.

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

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

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

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

Нотолгоо:ХК-ийн хязгаарлалтын системийн зөвшөөрөгдөх үндсэн шийдэл (1.4), үүнд эхнийх нь байна. Тбүрэлдэхүүн хэсэг нь үндсэн хувьсагч ба бусад нь p - тбүрэлдэхүүн хэсэг - үндсэн шийдэлд тэгтэй тэнцүү үндсэн бус хувьсагч (хэрэв тийм биш бол харгалзах хувьсагчдыг дахин дугаарлаж болно). Үүнийг харуулъя X

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

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

хаана (бид үүнийг таамаглаж байна, учир нь өөрөөр хэлбэл Xцэгтэй давхцаж байна X 1 эсвэл X 2).

Векторын тэгш байдлыг (1.6) координат хэлбэрээр бичье.

Учир нь бүх хувьсагч ба коэффициентүүд сөрөг биш, дараа нь сүүлчийнхээс p-tтэгшитгэл нь үүнийг дагадаг, i.e. шийдвэрүүдэд X 1 , X 2 ба Xтэгшитгэлийн систем (1.4) утгууд p - тЭнэ тохиолдолд бүрэлдэхүүн хэсгүүд нь тэгтэй тэнцүү байна. Эдгээр бүрэлдэхүүн хэсгүүдийг үндсэн бус хувьсагчийн утгууд гэж үзэж болно. Гэхдээ үндсэн бус хувьсагчдын утгууд нь үндсэн хувьсагчдын утгыг өвөрмөц байдлаар тодорхойлдог тул

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

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

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

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

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

мөн эдгээр хувьсагчдын шугаман функцийг дээд зэргээр нэмэгдүүлэх

Энгийн байхын тулд бид бүх нөхцөл (1) нь шугаман хамааралгүй (r=m) гэж үздэг бөгөөд бид энэ таамаглалын дагуу дүгнэлтээ хийх болно.

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

Энэ асуудал үргэлж шийдэлтэй байдаг уу? Үгүй ээ, үргэлж биш.

ZLP нь шийдвэрлэх боломжгүй (оновчтой шийдэл байхгүй):

Хязгаарлалтын системд нийцэхгүй байгаатай холбоотой. Тэдгээр. 1-р зурагт үзүүлсэн шиг системд ганц шийдэл байхгүй.

Зураг 1 - Хязгаарлалтын тогтолцооны зөрчил

Шийдлийн багц дээрх зорилгын функцийн хязгааргүй байдлаас шалтгаалан. Өөрөөр хэлбэл, LLP-ийг max-д шийдвэрлэх үед зорилгын функцийн утга нь хязгааргүйд, харин LLP-ийн хувьд min - хасах хязгааргүйд хүрэх хандлагатай байгааг Зураг 2-т үзүүлэв.

Зураг 2 - Шийдлийн олонлог дээрх зорилгын функцийн хязгааргүй байдал

ZLP нь шийдвэрлэх боломжтой:

Шийдлийн багц нь нэг цэгээс бүрдэнэ. Энэ нь мөн 3-р зурагт үзүүлсэн шиг оновчтой юм.

Зураг 3 - Шийдлийн багц нь нэг цэгээс бүрдэнэ

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

Зураг 4 - Цорын ганц оновчтой шийдэл

ZLP-ийн оновчтой шийдэл нь өвөрмөц биш юм. N вектор нь шийдлийн олонлогийн аль нэгэнд перпендикуляр байна. Энэ тохиолдолд AB сегментийн аль ч цэг нь 5-р зурагт үзүүлсэн шиг оновчтой байна.

Зураг 5 - Хамгийн оновчтой шийдэл нь өвөрмөц биш юм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дараагийн боломжит шийдэлд шилжих алгоритм нь дараах байдалтай байна.

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

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

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

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

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

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

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

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

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

Даалгаврын параметрүүд нь дараахь хязгаарын үзүүлэлтүүдээр хязгаарлагддаг.

• үл мэдэгдэх тоо - 200;
• үл мэдэгдэх хязгаарлалтын тоо - 100;
• үл мэдэгдэх нөхцлийн хязгаарын тоо 400 байна.

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

• бэлтгэл ажил;
• шийдлийг дибаг хийх;
• шийдлийн шинжилгээ.

MS Excel ашиглан эдийн засаг, математик загварчлалын асуудлыг шийдвэрлэхэд шаардлагатай бэлтгэл ажлын дарааллыг Зураг 1.6-ийн блок диаграммд үзүүлэв.

Цагаан будаа. 1.6.

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

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

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

Тиймээс, "Шийдэл хайх" оновчлолын програмын харилцах цонхонд бид дараах зорилтот алгоритмыг тохируулах ёстой.

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

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

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

Системийн анхны элементүүдийн тоо

Тодорхойлсон нөөцийн төрлүүдийн тоо

Програм нь сөрөг үр дүнгийн тухай мессежийг харуулах үед шийдлийг дибаг хийх шаардлагатай (Зураг 1.7):

Цагаан будаа. 1.7.

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

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

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

Эдийн засгийн шинжилгээ нь дараахь зорилготой.

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

Шинжилгээний боломжит аргуудыг Зураг 1.8 дахь диаграммд үзүүлэв.

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

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

• "Хэрэв юу болох вэ ..."
• "Үүнд юу хэрэгтэй вэ ..."

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

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

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

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

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

Оновчлолын даалгавар: ерөнхий мэдээлэл

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

Функцуудын шинж чанараас хамааран оновчлолын асуудлыг хоёр төрөлд хувааж болно.

• шугаман програмчлалын асуудал (бүх функц нь шугаман);
• шугаман бус програмчлалын асуудал (ядаж нэг функц нь шугаман биш).

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

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

PPP: томъёолол, ангилал

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

Ерөнхий ZLP нь маягтын асуудал юм

хязгаарлалт дор

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

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

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

• хольцтой холбоотой асуудлууд (жишээлбэл, бүтээгдэхүүний найрлагыг төлөвлөх);
• үйлдвэрлэлийн төлөвлөлтөд нөөцийг оновчтой хуваарилах асуудал;

PAP: жишээнүүд

Холимог асуудал

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

Нөөцийн хуваарилалтын асуудал

Тус компани үйлдвэрлэдэг nүйлдвэрлэхэд шаардлагатай төрөл бүрийн бүтээгдэхүүн мтөрөл бүрийн нөөц. Ашигласан нөөцийн нөөц хязгаарлагдмал бөгөөд тус тусын хэмжээгээр байна б 1, б 2,…, б м c.u. Үүнээс гадна технологийн коэффициентүүд мэдэгдэж байна a ij, энэ нь хэдэн нэгжийг харуулдаг би-Нэг нэгж бүтээгдэхүүн үйлдвэрлэхэд нөөц шаардлагатай j-р төрөл (). Аж ахуйн нэгж бүтээгдэхүүн борлуулахдаа олж буй ашиг j-р төрөл, хэмжээ в жмөнгөний нэгж Бүтээгдэхүүн үйлдвэрлэх төлөвлөгөө гаргах шаардлагатай бөгөөд үүнийг хэрэгжүүлэх явцад аж ахуйн нэгжийн ашиг хамгийн их байх болно.

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

Нөөц	Хэрэгцээ			Нөөц
	Б 1	…	Bn
А 1				б 1
…				…
Ам				б м
Ашиг	в 1	…	c n

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

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

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

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

Ерөнхийдөө тээврийн асуудлыг шийдвэрлэх нь хэд хэдэн үе шаттайгаар явагддаг.

• I үе шат: анхны жишиг төлөвлөгөөг барих;
• II үе шат: лавлагаа төлөвлөгөөг оновчтой эсэхийг шалгах;
• III үе шат: хэрэв оновчтой биш бол жишиг төлөвлөгөөг тодруулах.

Анхны жишиг төлөвлөгөөг олж авах хэд хэдэн арга байдаг, тухайлбал, баруун хойд булангийн арга, Vogel арга, хамгийн бага зардлын арга.

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

- эзлэгдсэн эсийн хувьд,
- эзэнгүй эсийн хувьд.

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

Дүгнэлт

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

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

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

1. Bandi B. Шугаман програмчлалын үндэс: Транс. англи хэлнээс – М.: Радио, харилцаа холбоо, 1989. – 176 х.
2. Кремер Н.Ш. Эдийн засгийн үйл ажиллагааны судалгаа: Proc. их дээд сургуулиудад зориулсан гарын авлага / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Эд. проф. Н.Ш. Кремер. – М.: НЭГДЭЛ, 2005. – 407 х.

Захиалгат оновчлолын аргуудын шийдэл

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

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

Тиймээс шугаман програмчлалын ерөнхий бодлогыг (GLP) дараах байдлаар томъёолж болно.

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

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

Мэдэгдэж байгаагаар үнэт зүйлсийн эрэмблэгдсэн цуглуулга nхувьсагч , , … нь n хэмжээст орон зайн цэгээр илэрхийлэгдэнэ. Дараах зүйлд бид энэ цэгийг тэмдэглэх болно X=( , , … ).

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

, А- хэмжээ матриц,

Цэг X=( , , … ) бүх нөхцөлийг хангасан бол гэж нэрлэдэг хүчинтэй цэг . Бүх зөвшөөрөгдөх цэгүүдийн багцыг дуудна хүчинтэй газар .

Оновчтой шийдэл (оновчтой төлөвлөгөө)шугаман програмчлалын асуудлыг шийдэл гэж нэрлэдэг X=( , , … ), зөвшөөрөгдөх мужид хамаарах ба шугаман функцтэй Qоновчтой (хамгийн их эсвэл хамгийн бага) утгыг авдаг.

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

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

Цэг Xдуудсан гүдгэр шугаман хослол нөхцөл хангагдсан тохиолдолд оноо

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

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

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

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

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

Дээрх теоремуудаас чухал үр дүн гарч байна.

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

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