Шугаман програмчлалын асуудлын шийдэл. График аргаар функцийн экстремумыг ол
зорилгын функц- Оновчлолын зарим асуудлыг шийдвэрлэхийн тулд оновчлох (багасгах эсвэл нэмэгдүүлэх) шаардлагатай хэд хэдэн хувьсагчийн бодит эсвэл бүхэл функц. Энэ нэр томъёог математикийн програмчлал, үйл ажиллагааны судалгаа, шугаман програмчлал, онолд ашигладаг статистикийн шийдвэрүүдболон математикийн бусад салбарууд, голчлон хэрэглээний шинж чанартай боловч оновчлолын зорилго нь математикийн асуудлын шийдэл байж болно. Оновчлолын асуудалд зорилгын функцээс гадна хувьсагчид тэгш байдал, тэгш бус байдлын систем хэлбэрээр хязгаарлалттай байж болно. AT ерөнхий тохиолдолзорилгын функцийн аргументуудыг дурын олонлог дээр зааж өгч болно.
Жишээ
Гөлгөр функц ба тэгшитгэлийн систем
Аливаа тэгшитгэлийн системийг шийдэх асуудал
( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\эхлэх(матриц)F_(1)(x_(1),x_(2),\ldots,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots,x_(M))=0\төгсгөл(матриц) )\зөв.)
зорилгын функцийг багасгах асуудал гэж томъёолж болно
S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots,x_(M))\qquad(1))
Хэрэв функцууд жигд байвал багасгах асуудлыг градиент аргаар шийдэж болно.
Аливаа гөлгөр зорилгын функцийн хувьд бүх хувьсагчийн хувьд хэсэгчилсэн деривативуудыг 0 (\displaystyle 0)-тай тэнцүүлж болно. Оновчтой зорилгын функц нь ийм тэгшитгэлийн системийн шийдлүүдийн нэг байх болно. (1) (\displaystyle (1)) функцийн хувьд энэ нь аргын тэгшитгэлийн систем болно. хамгийн бага квадратууд(MNK). Анхны системийн аливаа шийдэл нь хамгийн бага квадратуудын системийн шийдэл юм. Хэрэв анхны систем нь нийцэхгүй бол үргэлж шийдэлтэй байдаг LSM систем нь анхны системийн ойролцоо шийдлийг олж авах боломжийг олгодог. LSM системийн тэгшитгэлийн тоо нь үл мэдэгдэх тоотой давхцдаг бөгөөд энэ нь заримдаа хамтарсан анхны системийг шийдвэрлэхэд хялбар болгодог.
Шугаман програмчлал
Бусад алдартай жишээЗорилгын функц нь даалгаварт тохиолддог шугаман функц юм шугаман програмчлал. Квадрат зорилгын функцээс ялгаатай нь шугаман функцийг оновчлох нь шугаман тэгшитгэл эсвэл тэгш бус байдлын систем хэлбэрээр хязгаарлалт байгаа тохиолдолд л боломжтой юм.
Комбинаторын оновчлол
Комбинаторын зорилгын функцийн ердийн жишээ бол аялагч худалдагчийн асуудлын зорилгын функц юм. Энэ функц нь график дээрх Гамильтоны мөчлөгийн урттай тэнцүү байна. Энэ нь графикийн оройн n − 1 (\displaystyle n-1) солих багц дээр өгөгдсөн бөгөөд графикийн ирмэгийн уртын матрицаар тодорхойлогддог. Иймэрхүү асуудлын тодорхой шийдэл нь ихэвчлэн сонголтуудыг тоолоход хүргэдэг.
Бүлэг 1. Шугаман програмчлалын үндсэн асуудлын мэдэгдэл
Шугаман програмчлал
Шугаман програмчлал нь математик програмчлалын нэг салбар бөгөөд хэт туйлшралтай асуудлыг шийдвэрлэх аргуудыг судалдаг. шугаман хамааралхувьсагчдын хооронд болон шугаман шалгуур. Иймэрхүү асуудал нь өргөн хүрээний хэрэглээг олдог янз бүрийн талбаруудхүний үйл ажиллагаа. Энэ төрлийн асуудлыг системтэй судалж 1939-1940 онд эхэлсэн. L.V-ийн бүтээлүүдэд. Канторович.
Шугаман програмчлалын математикийн асуудлууд нь тодорхой үйлдвэрлэл, эдийн засгийн нөхцөл байдлын судалгааг агуулдаг бөгөөд үүнийг нэг хэлбэрээр эсвэл өөр хэлбэрээр тайлбарладаг. оновчтой хэрэглээхязгаарлагдмал нөөц.
Шугаман програмчлалын аргуудыг ашиглан шийддэг асуудлын хүрээ нэлээд өргөн бөгөөд жишээлбэл:
үйлдвэрлэлийн төлөвлөлтөд нөөцийг оновчтой ашиглах асуудал;
хольцын асуудал (бүтээгдэхүүний найрлагыг төлөвлөх);
оновчтой хослолыг олох асуудал төрөл бүрийнагуулахад хадгалах бүтээгдэхүүн (бараа материалын менежмент эсвэл);
тээврийн даалгавар (аж ахуйн нэгжийн байршил, барааны хөдөлгөөнд дүн шинжилгээ хийх).
Шугаман програмчлал нь математик програмчлалын хамгийн хөгжсөн, өргөн хэрэглэгддэг хэсэг юм (үүнээс гадна үүнд: бүхэл тоо, динамик, шугаман бус, параметрт програмчлал орно). Үүнийг дараах байдлаар тайлбарлав.
математик загварууд их тоо эдийн засгийн даалгаваршаардлагатай хувьсагчийн хувьд шугаман;
Энэ төрлийн асуудлууд одоогоор хамгийн их судлагдсан байна. Түүний хувьд эдгээр асуудлыг шийдвэрлэх тусгай аргуудыг боловсруулж, холбогдох компьютерийн программуудыг боловсруулсан;
шугаман програмчлалын олон асуудал шийдэгдэж, өргөн хэрэглээтэй болсон;
Анхны томъёололд шугаман бус зарим асуудлууд хэд хэдэн нэмэлт хязгаарлалт, таамаглалуудын дараа шугаман болж эсвэл шугаман програмчлалын аргаар шийдэж болох хэлбэрт оруулж болно.
Шугаман програмчлалын аливаа бодлогын эдийн засаг-математик загварт: оновчтой утгыг (хамгийн их эсвэл хамгийн бага) олох ёстой зорилгын функц; тогтолцооны хэлбэрийн хязгаарлалт шугаман тэгшитгэлэсвэл тэгш бус байдал; хувьсагчийн сөрөг бус байх шаардлага.
AT ерөнхий үзэлзагварыг дараах байдлаар бичнэ.
зорилгын функц
(1.1) хязгаарлалтын дагуу
(1.2) сөрөг бус байх шаардлага
(1.3) хаана x j– хувьсагч (үл мэдэгдэх);
- шугаман програмчлалын бодлогын коэффициентүүд.
Асуудал нь (1.2) ба (1.3) хязгаарлалтад хамаарах функцийн (1.1) оновчтой утгыг олох явдал юм.
Хязгаарлалтын системийг (1.2) бодлогын функциональ хязгаарлалт, (1.3) хязгаарлалтыг шууд хязгаарлалт гэнэ.
(1.2) ба (1.3) хязгаарлалтыг хангасан векторыг шугаман програмчлалын асуудлын боломжит шийдэл (төлөвлөгөө) гэнэ. Функц (1.1) хамгийн их (хамгийн бага) утгад хүрэх төлөвлөгөөг оновчтой гэж нэрлэдэг.
1.2. Шугаман програмчлалын асуудлыг шийдвэрлэх симплекс арга
Симплекс аргыг 1947 онд Америкийн математикч Ж.Данзиг боловсруулж бодлого бодоход анх хэрэглэж байжээ.
Хоёр хэмжээст шугаман програмчлалын асуудлыг графикаар шийддэг. N=3 тохиолдлын хувьд бид гурван хэмжээст орон зайг авч үзэх ба зорилгын функц нь олон өнцөгтийн аль нэг орой дээр хамгийн оновчтой утгад хүрнэ.
Өгөгдсөн LP-ийн асуудлын зөвшөөрөгдөх шийдэл (зөвшөөрөгдөх төлөвлөгөө). стандарт хэлбэр, нь хязгаарлалтыг хангадаг тоонуудын дараалсан багц (x1, x2, ..., xn); нь n хэмжээст орон зайн цэг юм.
Зөвшөөрөгдөх шийдлүүдийн багц нь LP-ийн асуудлын зөвшөөрөгдөх шийдлүүдийн (SDR) хэсгийг бүрдүүлдэг. ODR нь гүдгэр олон өнцөгт (олон өнцөгт) юм.
Ерөнхийдөө N-үл мэдэгдэх зүйл асуудалд оролцох үед бид хязгаарлах нөхцлийн системээр тодорхойлсон боломжит шийдлүүдийн талбайг n хэмжээст орон зайд гүдгэр олон өнцөгт хэлбэрээр дүрсэлсэн гэж хэлж болно. функцийг нэг буюу хэд хэдэн орой дээр гүйцэтгэдэг.
Хэрэв бүх чөлөөт хувьсагч тэгтэй тэнцүү байвал шийдлийг үндсэн гэж нэрлэдэг.
Лавлах шийдэл нь сөрөг бус үндсэн шийдэл юм. Дэмжлэгийн шийдэл нь доройтохгүй, доройтох боломжтой. Туслах шийдлийг тэгээс өөр координатын тоо нь системийн зэрэгтэй тэнцүү бол доройтдоггүй гэж нэрлэдэг.
Зорилгын функц нь туйлын утгад хүрэх боломжтой шийдлийг оновчтой гэж нэрлэж, тэмдэглэнэ 
.
Хувьсагчийн тоо 3-аас дээш байвал эдгээр асуудлыг графикаар шийдвэрлэхэд маш хэцүү байдаг. Шугаман програмчлалын асуудлыг шийдвэрлэх түгээмэл арга байдаг бөгөөд үүнийг симплекс арга гэж нэрлэдэг.
Симплекс арга нь бүх нийтийн арга LP асуудлуудыг шийдвэрлэх нь нэг шийдлээр эхэлж, хамгийн сайн хувилбарыг хайж олохын тулд боломжит шийдлүүдийн талбайн булангийн цэгүүдийн дагуу оновчтой утгад хүрэх хүртэл хөдөлдөг давтагдах процесс юм.
Үүнийг шугаман програмчлалын аливаа асуудлыг шийдвэрлэхэд ашиглаж болно.
Симплекс арга нь үүссэн шийдлийг дараалан сайжруулах санаан дээр суурилдаг.
Симплекс аргын геометрийн утга нь хязгаарлагдмал олон өнцөгтийн нэг оройноос хөрш зэргэлдээх цэг рүү дараалан шилжих бөгөөд хамгийн оновчтой шийдийг олох хүртэл зорилгын функц нь хамгийн сайн (эсвэл ядаж хамгийн муу биш) утгыг авдаг. оновчтой утга нь зорилгын функцэд хүрнэ (хэрэв асуудал нь хязгаарлагдмал оновчтой байвал).
Тиймээс, хязгаарлалтын системийг каноник хэлбэрт оруулснаар (бүх функциональ хязгаарлалтууд нь тэгш байдлын хэлбэртэй байдаг) энэ системийн ямар ч үндсэн шийдлийг олох бөгөөд зөвхөн үүнийг аль болох энгийн байдлаар олоход анхаардаг. Эхний олдсон үндсэн шийдэл нь хэрэгжих боломжтой гэж үзвэл оновчтой эсэхийг шалгана. Хэрэв энэ нь оновчтой биш бол өөр, заавал зөвшөөрөгдөх, үндсэн шийдэлд шилжих болно. Симплекс арга нь энэхүү шинэ шийдлээр зорилгын функц нь оновчтой хэмжээнд хүрэхгүй бол түүнд ойртож (эсвэл ядаж түүнээс холдохгүй) баталгаа өгдөг. Зөвшөөрөгдөх шинэ үндсэн шийдлийн хувьд оновчтой шийдэл олтол мөн адил хийнэ.
Симплекс аргыг хэрэглэх үйл явц нь түүний гурван үндсэн элементийг хэрэгжүүлэх явдал юм.
Асуудлыг шийдвэрлэх анхны боломжтой үндсэн шийдлийг тодорхойлох арга;
хамгийн сайн (илүү нарийвчлалтай, хамгийн муу биш) шийдэлд шилжих дүрэм;
олсон шийдлийн оновчтой байдлыг шалгах шалгуур.
Симплекс арга нь хэд хэдэн алхмуудыг багтаасан бөгөөд тодорхой алгоритм (дараалсан үйлдлийг гүйцэтгэх тодорхой заавар) хэлбэрээр томъёолж болно. Энэ нь компьютер дээр амжилттай програмчлах, хэрэгжүүлэх боломжийг олгодог. Цөөн тооны хувьсагч ба хязгаарлалттай асуудлыг симплекс аргаар гараар шийдэж болно.
6.1 Танилцуулга
Оновчлол. 1-р хэсэг
Оновчлолын аргууд нь танд сонгох боломжийг олгодог хамгийн сайн сонголтбүгдээс загвар сонголтууд. AT өнгөрсөн жилэдгээр аргуудад ихээхэн анхаарал хандуулж, үр дүнд нь a бүхэл бүтэн шугамолох өндөр үр ашигтай алгоритмууд хамгийн сайн сонголткомпьютер ашиглан дизайн хийх. Энэ бүлэгт оновчлолын онолын үндсийг тоймлон, оновчтой шийдлийн алгоритмыг бүтээх үндсэн зарчмуудыг авч үзэн, хамгийн алдартай алгоритмуудыг тайлбарлаж, тэдгээрийн давуу болон сул талуудад дүн шинжилгээ хийсэн.
6.2 Оновчлолын онолын үндэс
Уран зохиолын "оновчлол" гэсэн нэр томъёо нь нарийн шийдлийг олж авах боломжийг олгодог үйл явц эсвэл үйл ажиллагааны дарааллыг хэлдэг. Хэдийгээр эцсийн зорилгооновчлол гэдэг нь хамгийн сайн буюу "оновчтой" шийдлийг олох явдал бөгөөд та ихэвчлэн мэддэг шийдлүүдийг төгс болгохын оронд сайжруулахад сэтгэл хангалуун байх хэрэгтэй. Тиймээс оновчлолыг төгс төгөлдөрт хүрэх эрэл хайгуул гэж ойлгох магадлал өндөр байдаг бөгөөд энэ нь амжилтанд хүрэхгүй байх магадлалтай.
n үл мэдэгдэх m тэгшитгэлээр дүрслэгдсэн зарим дурын системийг авч үзвэл үндсэн гурван төрлийн бодлогыг ялгаж болно. Хэрэв m=n бол асуудлыг алгебрийн гэж нэрлэнэ. Ийм асуудал нь ихэвчлэн нэг шийдэлтэй байдаг. Хэрэв m>n бол асуудал дахин тодорхойлогдсон бөгөөд дүрмээр бол шийдэлгүй болно. Эцэст нь, м-ийн хувьд
Оновчлолын асуудлыг хэлэлцэхээс өмнө бид хэд хэдэн тодорхойлолтыг танилцуулж байна.
Дизайн параметрүүд
Энэ нэр томъёо нь шийдэгдэж буй дизайны асуудлыг бүрэн бөгөөд хоёрдмол утгагүй тодорхойлдог бие даасан хувьсах параметрүүдийг илэрхийлдэг. Дизайн параметрүүд нь үл мэдэгдэх хэмжигдэхүүнүүд бөгөөд тэдгээрийн утгыг оновчтой болгох явцад тооцдог. Системийг тоон байдлаар дүрслэх аливаа үндсэн эсвэл дериватив хэмжигдэхүүн нь дизайны параметр болж чаддаг. Тиймээс энэ нь урт, масс, цаг хугацаа, температурын үл мэдэгдэх утгууд байж болно. Загварын параметрүүдийн тоо нь энэхүү дизайны асуудлын нарийн төвөгтэй байдлын түвшинг тодорхойлдог. Ихэвчлэн дизайны параметрийн тоог n-ээр, дизайны параметрүүдийг х-ээр харгалзах индексээр тэмдэглэдэг. Тиймээс энэ асуудлын n загварын параметрийг дараах байдлаар тэмдэглэнэ
X1, x2, x3,...,xn.
зорилгын функц
Энэ бол инженерийн үнэ цэнийг нэмэгдүүлэх эсвэл багасгахыг эрэлхийлдэг илэрхийлэл юм. Зорилгын функц нь хоёр өөр шийдлийг тоон байдлаар харьцуулах боломжийг олгодог. Математикийн үүднээс авч үзвэл зорилгын функц нь зарим (n + 1) - хэмжээст гадаргууг дүрсэлдэг. Түүний утгыг дизайны параметрүүдээр тодорхойлно
M=M(x 1 , x 2 ,...,x n).
Инженерийн практикт ихэвчлэн тулгардаг зорилгын функцүүдийн жишээ бол өртөг, жин, хүч чадал, хэмжээс, үр ашиг юм. Хэрэв зөвхөн нэг загварын параметр байгаа бол зорилгын функцийг хавтгай дээрх муруйгаар дүрсэлж болно (Зураг 6.1). Хэрэв дизайны хоёр параметр байгаа бол зорилтот функц нь гурван хэмжээст орон зайд гадаргуугаар дүрслэгдэх болно (Зураг 6.2). Гурав ба түүнээс дээш загварын параметртэй бол зорилгын функцээр тодорхойлсон гадаргууг гипер гадаргуу гэж нэрлэдэг бөгөөд дүрслэх боломжгүй юм.
zheniya уламжлалт арга хэрэгсэл. Зорилгын функцийн гадаргуугийн топологийн шинж чанарууд тоглодог том үүрэгхамгийн үр дүнтэй алгоритмыг сонгох нь тэдгээрээс хамаардаг тул оновчлолын процесст.
Зорилгын функц нь зарим тохиолдолд хамгийн гэнэтийн хэлбэрийг авч болно. Жишээлбэл, үүнийг үргэлж илэрхийлэх боломжгүй байдаг
Зураг 1. Нэг хэмжээст зорилгын функц.
Зураг.6.2.Хоёр хэмжээст зорилгын функц.
хаалттай математик хэлбэр, бусад тохиолдолд энэ нь байж болно
хэсэгчилсэн гөлгөр функц байх. Зорилгын функцэд заримдаа техникийн өгөгдлийн хүснэгт (жишээлбэл, уурын төлөвийн хүснэгт) шаардлагатай эсвэл туршилт хийх шаардлагатай байж болно. Зарим тохиолдолд дизайны параметрүүд зөвхөн бүхэл тоон утгыг авдаг. Жишээ нь араа дахь шүдний тоо эсвэл фланцын боолтны тоо байж болно. Заримдаа дизайны параметрүүд нь зөвхөн хоёр утгатай байдаг - тийм эсвэл үгүй. Хэрэглэгчийн сэтгэл ханамж, найдвартай байдал, гоо зүй гэх мэт чанарын үзүүлэлтүүдийг тоон үзүүлэлтээр тодорхойлох бараг боломжгүй тул оновчлолын явцад харгалзан үзэхэд хэцүү байдаг. Гэсэн хэдий ч, зорилгын функцийг ямар ч хэлбэрээр харуулсан, энэ нь дизайны параметрүүдийн нэг утгатай функц байх ёстой.
Оновчлолын хэд хэдэн асуудалд нэгээс олон зорилгын функцийг нэвтрүүлэх шаардлагатай байдаг. Заримдаа тэдний нэг нь нөгөөтэйгөө таарахгүй байж болно. Үүний жишээ бол хамгийн их хүч чадал, хамгийн бага жин, хамгийн бага зардлыг нэгэн зэрэг хангах шаардлагатай нисэх онгоцны загвар юм. Ийм тохиолдолд дизайнер нь тэргүүлэх чиглэлүүдийн системийг нэвтрүүлж, зорилгын функц бүрт зарим хэмжээсгүй үржүүлэгч оноох ёстой. Үүний үр дүнд оновчлолын явцад нэг нийлмэл зорилгын функцийг ашиглах боломжийг олгодог "буулгах функц" гарч ирнэ.
Хамгийн бага ба дээд хэмжээг олох
Зарим оновчлолын алгоритмууд нь хамгийн ихийг, бусад нь хамгийн бага хэмжээг олоход зориулагдсан байдаг. Гэсэн хэдий ч, шийдэгдэж буй экстремумын бодлогын төрлөөс үл хамааран нэг алгоритмыг ашиглаж болно, учир нь багасгах бодлого нь зорилгын функцийн тэмдгийг эргүүлснээр хамгийн их олох бодлого болгон хувиргах боломжтой. Энэ техникийг Зураг 6.3-т үзүүлэв.
Дизайн орон зай
Энэ нь бүх n загварын параметрээр тодорхойлогдсон талбайн нэр юм. Дизайн орон зай нь санагдсан шиг тийм ч том биш, учир нь энэ нь ихэвчлэн хэд хэдэн тоогоор хязгаарлагддаг
холбоотой нөхцөлүүд бие махбодьдаалгавар. Хязгаарлалт нь маш хүчтэй байж болох тул даалгаварт ямар ч хязгаарлалт байхгүй болно
Зураг.6.3.Зориулалтын функцийн тэмдгийг эсрэгээр өөрчлөх
Хамгийн их даалгавар нь хамгийн бага даалгавар болдог.
хангалттай шийдэл. Хязгаарлалтуудыг хоёр бүлэгт хуваадаг: хязгаарлалт - тэгш байдал ба хязгаарлалт - тэгш бус байдал.
Хязгаарлалт - тэгш байдал
Хязгаарлалт - тэгш байдал - шийдлийг олоход анхаарах ёстой дизайны параметрүүдийн хоорондын хамаарал юм. Тэд байгаль, эдийн засаг, эрх, зонхилох амт, хүртээмжийн хууль тогтоомжийг тусгасан байдаг шаардлагатай материал. Хязгаарлалтын тоо - тэгш байдал нь ямар ч байж болно. Тэд харагдаж байна
C 1 (x 1 , x 2 ,...,x n)=0,
C 2 (x 1 , x 2 ,...,x n)=0,
..................
C j (x 1 , x 2 ,...,x n)=0.
Хэрэв эдгээр харилцааны аль нэгийг дизайны параметрүүдийн аль нэгтэй нь холбож шийдэж чадвал энэ параметрийг оновчлолын процессоос хасах боломжийг танд олгоно. Энэ нь дизайны орон зайн хэмжээсийн тоог багасгаж, асуудлын шийдлийг хялбаршуулдаг.
Хязгаарлалт - тэгш бус байдал
Энэ бол тэгш бус байдлаар илэрхийлэгддэг тусгай төрлийн хязгаарлалт юм. Ерөнхий тохиолдолд тэдгээрийн аль ч тоо байж болох бөгөөд бүгд хэлбэр дүрстэй байдаг
z 1 r 1 (x 1 , x 2 ,...,x n) Z 1
z 2 r 2 (x 1 , x 2 ,...,x n) Z 2
.......................
z k r k (x 1 , x 2 ,...,x n) Z k
Ихэнх тохиолдолд хязгаарлалтын улмаас түүний гадаргуу нь тэг градиенттэй бол зорилгын функцийн оновчтой утгад хүрдэггүй гэдгийг тэмдэглэх нь зүйтэй. Ихэнхдээ хамгийн сайн шийдэлзураг төслийн талбайн хилийн аль нэгтэй тохирч байна.
Орон нутгийн оновчтой
Энэ бол ойр орчмын бусад бүх цэгүүдийн утгуудтай харьцуулахад зорилгын функц нь хамгийн их утгатай байх дизайны орон зайн цэгийн нэр юм.
Зураг.6.4 Дурын зорилгын функц хэд хэдэн байж болно
орон нутгийн оптима.
Зураг дээр. Зураг 6.4-т хоёр орон нутгийн оптимумтай нэг хэмжээст зорилгын функцийг үзүүлэв. Ихэнхдээ дизайны орон зайд олон орон нутгийн оптимумууд байдаг бөгөөд эхнийх нь асуудлыг хамгийн оновчтой шийдэл гэж андуурахаас болгоомжлох хэрэгтэй.
Глобал оновчтой
Глобал оновчтой бол бүхэл бүтэн дизайны орон зайд хамгийн оновчтой шийдэл юм. Энэ нь орон нутгийн оптима-д тохирсон бусад бүх шийдлүүдээс илүү сайн бөгөөд үүнийг дизайнер хайж байгаа зүйл юм. -д байрлах хэд хэдэн тэнцүү дэлхийн оптимуудын тохиолдол өөр өөр хэсгүүддизайны орон зай. Оновчлолын асуудал хэрхэн тавигдаж байгааг жишээгээр хамгийн сайн дүрсэлсэн болно.
Жишээ 6.1
Савлаагүй эслэгийг зөөвөрлөх зориулалттай 1 м хэмжээтэй тэгш өнцөгт савыг зохион бүтээх шаардлагатай. Ийм савыг үйлдвэрлэхэд аль болох их мөнгө зарцуулах нь зүйтэй юм бага материал(ханын тогтмол зузаантай гэж үзвэл энэ нь гадаргуугийн талбай хамгийн бага байх ёстой гэсэн үг юм), учир нь энэ нь хямд байх болно. Савыг сэрээтэй зөөвөрлөхөд тохиромжтой болгохын тулд түүний өргөн нь дор хаяж 1.5 м байх ёстой.
Энэ асуудлыг оновчтой болгох алгоритмыг хэрэглэхэд тохиромжтой хэлбэрээр томъёолъё.
Дизайн параметрүүд: x 1 , x 2 , x 3 .
Зорилгын функц (багасгах шаардлагатай) нь савны хажуугийн гадаргуугийн талбай юм.
A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), м2.
Хязгаарлалт - тэгш байдал:
Эзлэхүүн \u003d x 1 x 2 x 3 \u003d 1м3.
Хязгаарлалт - тэгш бус байдал:
Шугаман програмчлалын асуудлууд
Шугаман програмчлал (LP)нь математик програмчлалын нэг хэсэг юм - экстремаль (оновчтой) асуудлуудыг судалж, тэдгээрийг шийдвэрлэх аргуудыг боловсруулдаг салбар юм.
Оновчлолын асуудал- энэ бол математикийн асуудал, энэ нь зорилгын функцийн оновчтой (жишээ нь, хамгийн их эсвэл хамгийн бага) утгыг олохоос бүрддэг бөгөөд хувьсагчдын утгууд нь тодорхой бүсэд хамаарах ёстой. зөвшөөрөгдсөн утгууд(ОДЗ).
Ерөнхийдөө математик програмчлалын экстремаль бодлогыг томъёолох нь хамгийн том буюу хамгийн бага утгагэж нэрлэгддэг функц зорилгын функц, нөхцөл (хязгаарлалт) дагуу, хаана болон - урьдчилан тодорхойлсон функцууд, мөн тогтмолууд өгөгдсөн. Үүний зэрэгцээ тэгш ба тэгш бус байдлын хэлбэрийн хязгаарлалтууд нь боломжит шийдлүүдийн багц (бүс нутаг) -ийг тодорхойлдог бөгөөд үүнийг нэрлэдэг. дизайны параметрүүд.
Функцийн төрлөөс хамааран математик програмчлалыг хэд хэдэн ангилалд хуваадаг (шугаман, шугаман бус, гүдгэр, бүхэл тоо, стохастик, динамик програмчлал гэх мэт).
AT ерөнхий үзэл LP асуудалтай байна дараагийн харах:
, (5.1)
, , (5.2)
, 
, (5.3)
Энд , , тогтмолууд өгөгдсөн.
(5.1) функцийг зорилгын функц гэж нэрлэдэг; систем (5.2), (5.3) - хязгаарлалтын системээр; нөхцөл (5.4) нь тооцооны параметрүүдийн сөрөг бус байх нөхцөл юм.
(5.2), (5.3) ба (5.4) хязгаарлалтуудыг хангасан загварын параметрүүдийн багцыг гэнэ. хүлээн зөвшөөрөгдсөн шийдэлэсвэл төлөвлө.
Хамгийн оновчтой шийдэл эсвэл оновчтой төлөвлөгөө LP асуудлыг хэрэгжүүлэх боломжтой шийдэл гэж нэрлэдэг бөгөөд үүнд зорилгын функц (5.1) нь оновчтой (хамгийн их эсвэл хамгийн бага) утгыг авдаг.
Стандарт даалгавар LP-ийг (5.2) ба (5.4) нөхцлөөр зорилгын функцийн (5.1) хамгийн их (хамгийн бага) утгыг олох асуудал гэж нэрлэдэг бөгөөд энд , , i.e. тэдгээр. Зөвхөн тэгш бус байдлын хэлбэрийн хязгаарлалт (5.2) ба дизайны бүх параметрүүд нь сөрөг бус нөхцөлийг хангаж байгаа бөгөөд тэгш байдлын хэлбэрийн нөхцөл байхгүй.
,
, , (5.5)
.
Каноник (үндсэн) даалгавар LP-ийг (5.3) ба (5.4) нөхцлөөр зорилгын функцийн (5.1) хамгийн их (хамгийн бага) утгыг олох асуудал гэж нэрлэдэг бөгөөд энд , , i.e. тэдгээр. Зөвхөн тэгш байдлын (5.3) хэлбэрийн хязгаарлалтууд ба дизайны бүх параметрүүд нь сөрөг бус нөхцөлийг хангаж байгаа бөгөөд тэгш бус байдлын хэлбэрээр ямар ч нөхцөл байхгүй:
,
.
Каноник LP бодлогыг мөн матриц болон вектор хэлбэрээр бичиж болно.
Каноник LP бодлогын матриц хэлбэр нь дараах хэлбэртэй байна.
Каноник LP асуудлын вектор хэлбэр.
Лабораторийн №1 Шугаман програмчлалын бодлого бодох
ЗорилгоГрафик, симплекс арга, Excel хэрэглүүрийг ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх ур чадварыг олж авах.
Шугаман програмчлалын даалгавар бол шугаман хязгаарлалттай үед шугаман функцын хамгийн их эсвэл хамгийн бага утгыг хэрхэн олохыг сурах явдал юм. Зорилгын функц нь хамгийн их эсвэл хамгийн бага утгыг олдог функц юм. Хамгийн их буюу хамгийн бага утгад хүрэх хувьсах утгуудын багцыг оновчтой шийдэл (оновчтой төлөвлөгөө) гэж нэрлэдэг бөгөөд хязгаарлалтыг хангасан бусад бүх утгыг хүлээн зөвшөөрөгдөх шийдэл (боломжтой төлөвлөгөө) гэж нэрлэдэг.
Геометрийн шийдлийн арга IШугаман програмчлалын асуудлыг жишээгээр авч үзье.
Жишээ. Зорилгын функцийн хамгийн их утгыг ол Л=2x 1 +2xӨгөгдсөн хязгаарлалтын дагуу 2
Шийдэл.Тэгш бус байдлын тэмдгүүдийг яг тэгш байдлын тэмдэг болгон өөрчлөх замаар хязгаарлалтын системийн шийдлийн мужийг байгуулъя.
л 1: 3x 1 -2x 2 +6=0,
л 2: 3x 1 +x 2 -3=0,
л 3:x 1 -3=0.
ДFROM
2 0 1 3 X 1
(л 1) (л 3)
Чигээрээ л 1 нь онгоцыг хуваана XО цагт(3) системийн эхний тэгш бус байдлыг хангах нэгийг сонгох ёстой хоёр хагас хавтгайд. Үүний тулд бид т. О(0; 0) ба тэгш бус байдалд орлуулна. Хэрэв энэ нь үнэн бол та шулуун шугамаас хагас хавтгайг сүүдэрлэх хэрэгтэй. О(0; 0). Шулуун шугамтай ижил зүйлийг хий. л 2 ба л 3 . Тэгш бус байдлын шийдлийн муж (3) нь олон өнцөгт юм ABCД. Хавтгайн цэг бүрийн хувьд функц Лтогтмол утгыг авдаг Л=Лнэг . Бүх цэгийн гүйдлийн багц нь шулуун шугам юм Л=в 1 x 1 +в 2 x 2 (бидний тохиолдолд Л=2x 1 +2x 2) векторт перпендикуляр FROM(-тай 1 ;-тай 2) (FROM(2; 2)), гарал үүслээс гарч ирсэн. Хэрэв энэ шугамыг векторын эерэг чиглэлд шилжүүлбэл -тай, дараа нь зорилгын функц Лнэмэгдэх болно, эс бөгөөс буурах болно. Тиймээс манай тохиолдолд олон өнцөгтөөс гарах үед шулуун шугам ABCДшийдвэрүүд гарах болно AT(3; 7.5), тиймээс, орно. ATзорилгын функц нь хамгийн их утгыг авдаг, өөрөөр хэлбэл. Лхамгийн их =2ּ3+2ּ7,5=21. Үүний нэгэн адил функц нь хамгийн бага утгыг авах нь тодорхойлогддог, өөрөөр хэлбэл, Д(1; 0) ба Лмин=2ּ1+2ּ0=2.
Шугаман програмчлалын асуудлыг шийдэх симплекс аргын алгоритм нь дараах байдалтай байна.
1. Ерөнхий даалгаваршугаман програмчлал нь хязгаарлалтын системд тэгш бус байдал байгаатай адил олон туслах хувьсагчийг оруулснаар каноник бодлого (хязгаарлалтуудад тэнцүү тэмдэгтүүд байдаг) болж буурдаг.
2. Зорилгын функцийг үндсэн болон туслах хувьсагчаар илэрхийлнэ.
3. Эхний симплекс хүснэгтийг эмхэтгэсэн. Хязгаарлалтын системийг зөвшөөрдөг суурь болгон хувьсагчдыг бичдэг (туслах хувьсагчдыг үндсэн хувьсагч болгон авах нь дээр). Хүснэгтийн эхний мөрөнд бүх хувьсагчдыг жагсааж, чөлөөт гишүүдэд зориулсан багана өгдөг. Хүснэгтийн сүүлчийн мөрөнд эсрэг тэмдгээр зорилгын функцийн коэффициентүүдийг бичнэ
4. Симплекс хүснэгт бүр нь шугаман програмчлалын асуудлын шийдлийг өгдөг: чөлөөт хувьсагч нь тэгтэй тэнцүү, үндсэн хувьсагч нь чөлөөт гишүүдтэй тэнцүү байна.
5. Оновчтой байдлын шалгуур нь асуудлыг шийдвэрлэх хүснэгтийн сүүлийн эгнээнд сөрөг элемент байхгүй, хамгийн ихдээ эерэг элемент байхгүй байна.
6. Шийдвэрийг сайжруулахын тулд нэг симплекс хүснэгтээс нөгөө рүү шилжих шаардлагатай. Үүнийг хийхийн тулд өмнөх хүснэгтэд хүснэгтийн сүүлчийн эгнээний хамгийн бага сөрөг элемент болон хамгийн бага бодлогын хамгийн том эерэг коэффициенттэй тохирох гол багана олдсон. Дараа нь чөлөөт нэр томъёоны гол баганын харгалзах эерэг элементүүдийн хамгийн бага харьцаатай тохирох гол мөрийг ол. Түлхүүр багана ба гол мөрний огтлолцол дээр гол элемент байна.
7. Бид суурь бөглөх замаар дараагийн симплекс хүснэгтийг бөглөж эхэлнэ: үндсэн мөрөнд тохирох хувьсагчийг үндсэн дээр нь гаргаж, оронд нь гол баганад тохирох хувьсагчийг оруулна. Өмнөх түлхүүрийн хэлхээний элементүүдийг өмнөх элементийг түлхүүрийн мөрөнд хуваах замаар олж авдаг. Өмнөх гол баганын элементүүд нь нэг гол элементээс бусад нь тэг болно. Бусад бүх элементүүдийг тэгш өнцөгтийн дүрмийн дагуу тооцоолно.
8. Симплекс хүснэгтүүдийг оновчтой төлөвлөгөө гартал хувиргана.
Жишээ. Функцийн хамгийн их утгыг ол 
хувьсагч бол 
хязгаарлалтын тогтолцоог хангах:
Шийдэл. 1. Шинэ хувьсагчдыг нэвтрүүлэх 
, үүний тусламжтайгаар бид системийн тэгш бус байдлыг тэгшитгэл болгон хувиргадаг.
Бид зорилгын функцийн коэффициентүүдийн тэмдгийг өөрчлөх эсвэл хэлбэрээр бичнэ 
. Бид эхний симплекс хүснэгтийг бид бичсэн тэг мөрөнд бөглөнө X 1 ,X 2 ба 
(чөлөөт коэффициентүүд). Тэг баганад X 3 ,X 4 ,X 5 ба Ф. Бид энэ хүснэгтийг олж авсан тэгшитгэлийн систем болон хувиргасан зорилгын функцийн дагуу бөглөнө.
|
|
|
|
|
|
| |||
|
| |||
|
| |||
|
|
Бид олохын тулд оновчтой байдлын шалгуурыг шалгадаг хамгийн их утга: сүүлийн эгнээнд бүх коэффициент эерэг байх ёстой. Энэ шалгуур хангагдаагүй тул бид хоёр дахь хүснэгтийн эмхэтгэлийг үргэлжлүүлнэ.
2. Бид эхний хүснэгтийн шийдвэрлэх элементийг дараах байдлаар олно. Сүүлийн эгнээний элементүүдээс бид үнэмлэхүй утгын хамгийн том сөрөг коэффициентийг (энэ нь -3) сонгож, хоёр дахь баганыг шийдвэрлэх гэж хүлээн зөвшөөрдөг. Хэрэв баганын бүх коэффициент эерэг биш байвал 
.
Шийдвэрлэх мөрийг тодорхойлохын тулд бид чөлөөт коэффициентүүдийг шийдвэрлэх баганын харгалзах элементүүдээр хувааж, хамгийн бага харьцааг сонгох боловч сөрөг коэффициентийг авдаггүй. Бидэнд байгаа 
, хоёр дахь мөр нь зөвшөөрөгдсөн байна. Зөвшөөрөгдсөн мөр ба баганын огтлолцол нь зөвшөөрөгдөх элементийг өгдөг - энэ нь 3.
3. Хоёр дахь симплекс хүснэгтийг бөглөнө үү. Уулзвар дээр бид шийдвэрлэх элементийг олж авдаг хувьсагчид, харилцан солилцох, i.e. 
болон 
. Бид идэвхжүүлэх элементийг урвуугаар нь орлуулдаг, өөрөөр хэлбэл. дээр. Зөвшөөрөгдөх мөр ба баганын элементүүд (зөвшөөрөх элементээс бусад) зөвшөөрөгдөх элементээр хуваагдана. Энэ тохиолдолд бид шийдвэрлэх баганын коэффициентүүдийн тэмдгийг өөрчилдөг.
Хоёрдахь хүснэгтийн үлдсэн элементүүдийг эхний хүснэгтийн элементүүдээс тэгш өнцөгтийн дүрмээр олж авна. Дүүргэгдсэн нүд болон шийдвэрлэх элемент бүхий нүдний хувьд бид тэгш өнцөгтийг хийдэг. Дараа нь бөглөх нүдэнд зориулсан элементээс бусад хоёр оройн элементүүдийн үржвэрийг шийдвэрлэх элементээр хуваана. Хоёрдахь хүснэгтийн эхний мөрийг бөглөхдөө энэ дүрмийн дагуу тооцооллыг үзүүлье.
.
Шалгуурт нийцэх хүртэл бид эдгээр дүрмийн дагуу хүснэгтүүдийг бөглөнө. Бидэнд даалгаврын хувьд дахиад хоёр ширээ байна.
|
X 1 |
X 4 |
X 3 |
X 2 | ||||||
|
X 3 |
X 1 |
| |||||||
|
X 2 |
|
X 2 |
|
|
|
||||
|
X 5 |
|
X 5 |
| ||||||
|
|
4. Энэхүү алгоритмын үр дүнг дараах байдлаар бичнэ. Эцсийн хүснэгтэд эгнээний огтлолцол дахь элемент 
ба багана б, зорилгын функцийн хамгийн их утгыг өгнө. Манай тохиолдолд 
. Мөр дэх хувьсагчдын утгууд нь чөлөөт коэффициентүүдтэй тэнцүү байна. Бидний даалгавар бол бидэнд байгаа 
.
Симплекс хүснэгтийг эмхэтгэх, бөглөх өөр аргууд байдаг. Жишээлбэл, 1-р үе шатанд бүх хувьсагч ба чөлөөт коэффициентийг хүснэгтийн тэг мөрөнд тэмдэглэнэ. Дараах хүснэгтийн ижил дүрмийн дагуу шийдвэрлэх элементийг олсны дараа бид тэг баганад хувьсагчийг орлуулах боловч мөрөнд биш. Зөвшөөрөгдсөн шугамын бүх элементүүдийг зөвшөөрөгдөх элементээр хувааж, шинэ хүснэгтэд бичнэ. Идэвхжүүлэх баганын үлдсэн элементүүдийн хувьд бид тэг бичдэг. Дараа нь бид эдгээр дүрмийг харгалзан заасан алгоритмыг гүйцэтгэдэг.
Шугаман програмчлалын асуудлыг хамгийн бага хэмжээгээр шийдвэрлэхдээ хамгийн том эерэг коэффициентийг сүүлчийн мөрөнд сонгож, заасан алгоритмыг сүүлчийн мөрөнд эерэг коэффициент байхгүй болтол гүйцэтгэнэ.
Excel ашиглан шугаман програмчлалын бодлогуудын шийдлийг дараах байдлаар гүйцэтгэнэ.
Шугаман програмчлалын асуудлыг шийдвэрлэхийн тулд Search for Solution нэмэлтийг ашигладаг. Эхлээд та энэ нэмэлт нь Анализ бүлгийн Мэдээллийн таб дээр байгаа эсэхийг шалгах хэрэгтэй (2003 оны "Хэрэгслүүд" хэсгийг үзнэ үү). Хэрэв Шийдвэрлэх команд эсвэл Шинжилгээ хийх бүлэг байхгүй бол та энэ нэмэлтийг татаж авах ёстой.
Үүнийг хийхийн тулд Файл дээр дарна уу Microsoft Office(2010), дараа нь Excel Options товчийг дарна уу. Гарч ирэх Excel Options цонхноос зүүн талд байгаа Нэмэлтүүдийг сонгоно уу. Цонхны баруун талд байгаа "Удирдах" талбарын утгыг Excel-ийн нэмэлт хэрэгсэл болгон тохируулах ёстой бөгөөд энэ талбарын хажууд байрлах "Явах" товчийг дарна уу. Нэмэлт хэрэгслүүдийн цонхонд Шийдэл олох хажуугийн нүдийг сонгоод OK дарна уу. Дараа нь та суулгасан Find Solutions нэмэлттэй ажиллах боломжтой.
Хайлтын шийдлүүдийг дуудахаасаа өмнө шугаман програмчлалын асуудлыг шийдэхийн тулд өгөгдлийг бэлтгэх шаардлагатай математик загвар) ажлын хуудсан дээр:
1) Үүний тулд шийдлийн үр дүнг байрлуулах нүдийг тодорхойлж, эхний мөрөнд хувьсагч ба зорилгын функцийг оруулна. Эдгээр нүднүүдэд хоёр дахь мөрийг бөглөөгүй (солих боломжтой нүднүүд) оновчтой үр дүнд хүрэх болно. Дараагийн мөрөнд зорилгын функцын өгөгдлийг, дараагийн мөрөнд хязгаарлалтын системийг (үл мэдэгдэхгүй коэффициент) оруулна. Баруун талхязгаарлалт (чөлөөт коэффициент) -ийг нэвтрүүлж, хязгаарлалтын системийн коэффициентийг тэмдэглэсний дараа чөлөөт нүдийг үлдээдэг.
2) Зорилгын функцын хувьсах нүднүүдийн хамаарлыг, үлдсэн чөлөөт нүднүүдэд хязгаарлалтын системийн зүүн хэсгүүдийн хувьсах нүднүүдийн хамаарлыг оруулна. Хамааралтай томьёог нэвтрүүлэхийн тулд SUMPRODUCT математик функцийг ашиглах нь тохиромжтой.
Дараа нь та шийдэл хайх нэмэлт хэрэгслийг ашиглах хэрэгтэй. Мэдээллийн табын Шинжилгээ хийх бүлгийн Шийдвэрлэгчийг сонгоно уу. Шийдэл хайх харилцах цонх гарч ирэх бөгөөд үүнийг дараах байдлаар бөглөх ёстой.
1) "Зорилтын функцийг оновчтой болгох" талбарт зорилгын функц агуулсан нүдийг зааж өгнө үү (энэ нүд нь зорилгын функцийн томъёог агуулсан байх ёстой). Зорилтот нүдний утгыг оновчтой болгох сонголтыг сонгоно уу (томруулах, багасгах):
2) "Хувьсагчийн нүдийг өөрчлөх" талбарт хувьсагчийн нүдийг оруулна уу. Дараагийн талбарт "Хязгаарлалтын дагуу" "Нэмэх" товчийг ашиглан заасан хязгаарлалтыг оруулна уу. Гарч ирэх цонхонд хязгаарлалтын системийн томъёог агуулсан нүднүүдийг оруулаад, хязгаарлалтын тэмдэг ба хязгаарлалтын утгыг (чөлөөт коэффициент) сонгоно уу.
3) "Хязгаарлалтгүй хувьсагчийг сөрөг биш болгох" хайрцгийг чагтална уу. Шийдлийн аргыг "Шугаман бодлогын шийдлийг симплекс аргаар хайх" сонгоно. "Шийдлээ олох" товчийг дарсны дараа асуудлыг шийдэх процесс эхэлнэ. Үүний үр дүнд "Шийдлийн эрэл хайгуулын үр дүн" харилцах цонх гарч ирэх ба хувьсагчдын утгууд болон зорилгын функцийн оновчтой утгыг дүүргэсэн нүднүүдийн эх хүснэгт гарч ирнэ.
Жишээ. Excel Solver нэмэлтийг ашиглан шугаман програмчлалын асуудлыг шийд: функцийн хамгийн их утгыг ол 
хязгаарлалт дор
,
;
,
.
Шийдэл. Excel-ийн ажлын хуудсан дээрх асуудлыг шийдэхийн тулд бид заасан алгоритмыг гүйцэтгэх болно. Бид анхны өгөгдлийг хүснэгт хэлбэрээр оруулна
Бид зорилгын функц болон хязгаарлалтын системийн хамаарлыг танилцуулж байна. Үүнийг хийхийн тулд C2 нүдэнд томьёог оруулна уу =SUMPRODUCT(A2:B2;A3:B3). С4 ба С5 нүдэнд тус тус томъёонууд нь: =ДҮГНЭЛТ(A2:B2;A4:B4) ба =ДҮГНЭЛТ(A2:B2;A5:B5). Үр дүн нь хүснэгт юм.
Бид "Шийдвэр хайх" командыг ажиллуулж, "Шийдэл хайх" цонхыг дараах байдлаар бөглөнө. "Зориулалтын функцийг оновчтой болгох" талбарт C2 нүдийг оруулна уу. Бид "Хамгийн их" зорилтот нүдний утгыг оновчтой болгохоор сонгосон.
"Хувьсагчийн нүднүүдийг өөрчлөх" талбарт A2:B2 хувьсагчийн нүдийг оруулна. "Хязгаарлалтын дагуу" талбарт "Нэмэх" товчийг ашиглан заасан хязгаарлалтыг оруулна уу. Нүдний лавлагаа $C$4:$C$5 Хязгаарлалтын лавлагаа =$D$4:$D$5 тэдгээрийн хоорондох тэмдэг<= затем кнопку «ОК».
"Хязгаарлагдаагүй хувьсагчийг сөрөг биш болгох" нүдийг шалгана уу. Шийдлийн аргыг "Шугаман бодлогын шийдлийг симплекс аргаар хайх" сонгоно.
"Шийдлээ олох" товчийг дарснаар асуудлыг шийдэх процесс эхэлнэ. Үүний үр дүнд "Шийдлийн эрэл хайгуулын үр дүн" харилцах цонх гарч ирэх ба хувьсагчдын утгууд болон зорилгын функцийн оновчтой утгыг дүүргэсэн нүднүүдийн эх хүснэгт гарч ирнэ.
"Шийдлийн эрэл хайгуулын үр дүн" харилцах цонхонд бид үр дүнг хадгална x1=0.75, x2=0.75 , F=1.5 - зорилгын функцийн хамгийн их утгатай тэнцүү.
Бие даасан ажилд зориулсан даалгавар
Дасгал 1.Функцийн хамгийн их ба хамгийн бага утгыг олох график, симплекс аргууд болон Excel хэрэгслүүд Ф(x) өгөгдсөн хязгаарлалтын системийн хувьд.
1. Ф(x)=10x 1 +5x 2 2. Ф(x)=3x 1 -2x 2
3. Ф(x)=3x 1 +5x 2 4. Ф(x)=3x 1 +3x 2
5. Ф(x)=4x 1 -3x 2 6. Ф(x)=2x 1 -x 2
7. Ф(x)=-2x 1 +4x 2 8. Ф(x)=4x 1 -3x 2
9. Ф(x)=5x 1 +10x 2 10. Ф(x)=2x 1 +x 2
11. Ф(x)=x 1 +x 2 12. Ф(x)=3x 1 +x 2
13. Ф(x)=4x 1 +5x 2 14. Ф(x)=3x 1 +2x 2
15. Ф(x)=-x 1 -x 2 16. Ф(x)=-3x 1 -5x 2
17. Ф(x)=2x 1 +3x 2 18. Ф(x)=4x 1 +3x 2
19. Ф(x)=-3x 1 -2x 2 20. Ф(x)=-3x 1 +4x 2
21. Ф(x)=5x 1 -2x 2 22. Ф(x)=-2x 1 +3x 3
23. Ф(x)=2x 1 +3x 2 24. Ф(x)=4x 1 +3x 2
25. Ф(x)=-3x 1 -2x 2 26. Ф(x)=-3x 1 +4x 2
27. Ф(x)=-2x 1 +4x 2 28. Ф(x)=4x 1 -3x 2
29. Ф(x)=-x 1 -x 2 30. Ф(x)=-3x 1 -5x 2
Туршилтын асуултууд.
1. Шугаман програмчлалын бодлого гэж ямар даалгавруудыг нэрлэх вэ?
2. Шугаман програмчлалын бодлогын жишээг өг.
3. Шугаман програмчлалын асуудлыг график аргаар хэрхэн шийддэг вэ?
4. Шугаман програмчлалын асуудлыг шийдвэрлэх симплекс аргын алгоритмыг тайлбарлана уу.
5. Excel ашиглан шугаман програмчлалын бодлого бодох алгоритмыг тайлбарла.
СЭДЭВ: Шугаман ПРОГРАМЧЛАЛ
ДААЛГАВАР 2.А. Шугаман програмчлалын асуудлыг график аргаар шийдвэрлэх
Анхаар!
Энэ бол 2073 тоот ажлын ТАНИЛЦУУЛГА ХУВИЛБАР бөгөөд анхны үнэ нь 200 рубль юм. Microsoft Word дээр зохион бүтээгдсэн.
Төлбөр. Харилцагчид.
Сонголт 7. Хамгийн их ба хамгийн бага утгыг олшугаман функц Ф \u003d 2x 1 - 2 x 2хязгаарлалттай: x 1 + x 2 ≥ 4;
- x 1 + 2 x 2 ≤ 2;
x 1 + 2 x 2 ≤ 10;
x i ≥ 0, i = 1.2.
Шийдэл:
Тэгш бус байдлын нөхцөлт тэмдгийг тэгш байдлын тэмдгээр сольж, бид x1 + x2 = 4 тэгшитгэлийн системийг олж авна;
- x1 + 2 x2 = 2;
x1 + 2 x2 = 10.
Бид эдгээр тэгшитгэлээс шулуун шугамуудыг барьж, тэгш бус байдлын тэмдгүүдийн дагуу хагас хавтгайг сонгож, тэдгээрийг олж авдаг. ерөнхий хэсэг– ODT-ийн зөвшөөрөгдөх шийдлийн домэйн – дөрвөлжин MNPQ.
Функцийн хамгийн бага утга
tsii - M цэг дээр (2; 2)
Ф мин = 2 2 - 2 2 = 0.
Хамгийн их утга нь N цэг дээр хүрсэн (10; 0),
Ф max \u003d 2 10 - 2 0 \u003d 20.
Сонголт 8. Хамгийн их ба хамгийн бага утгыг ол
шугаман функц Ф \u003d x 1 + x 2
хязгаарлалттай: x 1 - 4 x 2 - 4 ≤ 0;
3 x 1 - x 2 ≥ 0;
x 1 + x 2 - 4 ≥ 0;
x i ≥ 0, i = 1.2.
Шийдэл:
Тэгш бус байдлын нөхцөлт тэмдгүүдийг тэгшитгэлийн тэмдгээр сольж, бид x1 - 4 x2 = 4 тэгшитгэлийн системийг олж авна;
3 x1 - x2 = 0;
Бид эдгээр тэгшитгэлийн дагуу шулуун шугамуудыг барьж, дараа нь тэгш бус байдлын тэмдгүүдийн дагуу хагас хавтгайг сонгож, тэдгээрийн нийтлэг хэсгийг - ODE-ийн зөвшөөрөгдөх шийдлийн муж - хязгааргүй MNPQ олон өнцөгтийг олж авдаг.
Функцийн хамгийн бага утга
tions - жишээлбэл, шулуун шугам дээр NP
цэг дээр Р(4; 0)
Ф мин = 4 + 0 = 4.
ODE нь дээрээс хязгаарлагдахгүй тул Ф max = + ∞.
Сонголт 10. Хамгийн их ба хамгийн бага утгыг ол
шугаман функц Ф \u003d 2 x 1 - 3 x 2
хязгаарлалттай: x 1 + 3 x 2 ≤ 18;
2 x 1 + x 2 ≤ 16;
x 2 ≤ 5;
x i ≥ 0, i = 1.2.
Тэгш бус байдлын тэмдгүүдийг тэгшитгэлийн тэмдгээр нөхцлөөр сольж тэгшитгэлийн системийг олж авна.
x 1 + 3 x 2 = 18 (1);
2 x 1 + x 2 = 16 (2);
3 x 1 = 21 (4).
Бид эдгээр тэгшитгэлийн дагуу шулуун шугамуудыг барьж, дараа нь тэгш бус байдлын тэмдгүүдийн дагуу хагас хавтгайг сонгож, тэдгээрийн нийтлэг хэсгийг - ODE-ийн зөвшөөрөгдөх шийдлийн муж - MNPQRS полигоныг олж авдаг.
Г(2; -3) векторыг байгуулж эхийг нь зурна түвшний шугам- Чигээрээ.
Бид түвшний шугамыг чиглэлд шилжүүлж, F-ийн утга нэмэгддэг. S(7; 0) цэгт зорилгын функц хамгийн ихдээ хүрнэ Ф max =2·7–3·0= = 14. Бид түвшний шугамыг чиглэлд хөдөлгөж байхад Ф-ийн утга буурна. Функцийн хамгийн бага утга нь N(0; 5) цэг дээр байна.
Ф мин = 2 0 – 3 5 = –15.
ДААЛГАВАР 2.Б. Шугаман програмчлалын асуудлыг шийдвэрлэх
аналитик симплекс арга
Сонголт 7. Зорилгын функцийг багасгах Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6
хязгаарлалт дор: x 1 + x 4 +6 x 6 = 9,
3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,
x 1 + 2 x 3 + x 5 + 2 x 6 = 6.
Шийдэл:
Үл мэдэгдэх тоо n=6, тэгшитгэлийн тоо m=3. Иймд r = n-m = 3 үл мэдэгдэхийг чөлөөтэй гэж авч болно. x 1 , x 3 болон x 6 -г сонгоцгооё.
Бид x 2, x 4, x 5 үндсэн хувьсагчдыг чөлөөт хувьсагчаар илэрхийлж, системийг нэгжийн суурьт шилжүүлдэг.
x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6
x 4 \u003d 9 - x 1 - 6 x 6 (*)
x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6
Зорилгын функц нь дараах байдлаар харагдах болно.
Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =
13 + 2 x 1 - 5 x 3 - 7 x 6
x 1 \u003d x 3 \u003d x 6 \u003d 0 гэж оруулъя, харин үндсэн хувьсагчид x 2 \u003d 2 утгыг авна; x 4 \u003d 9; x 5 \u003d 6, өөрөөр хэлбэл эхний боломжит шийдэл (0; 2; 0; 9; 6; 0), зорилгын функц Ф 1 \u003d 13.
Х 3 ба x 6 хувьсагч нь сөрөг коэффициент бүхий зорилгын функцэд багтсан тул тэдгээрийн утга нэмэгдэх тусам Ф-ийн утга буурах болно. Жишээлбэл, x 6-г ав. Системийн 1-р тэгшитгэлээс (*) харахад x 6-ийн утгыг x 6 \u003d 1 (x 2 ³ 0) хүртэл нэмэгдүүлэх боломжтой. Энэ тохиолдолд x 1 ба x 3 нь тэгтэй тэнцүү утгыг хадгална. Одоо үндсэн хувьсагчийн хувьд бид x 4, x 5, x 6-г үнэгүй, x 1, x 2, x 3 гэж авна. Шинэ үндсэн хувьсагчдыг шинэ чөлөөт хувьсагчаар илэрхийлье. Авах
x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3
x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3
x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3
Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3
Чөлөөт хувьсагчдад тэг утгыг оноох, өөрөөр хэлбэл x 1 \u003d x 2 \u003d x 3 \u003d 0, харин x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, өөрөөр хэлбэл гурав дахь нь. хүчинтэй шийдэл (0; 0; 0; 3; 4; 1). Энэ тохиолдолд Ф 3 \u003d 6.
Х 3 хувьсагч нь сөрөг коэффициенттэй зорилгын функцэд орсон тул тэгтэй харьцуулахад x 3-ийн өсөлт нь F-ийн бууралтад хүргэнэ. 2-р тэгшитгэлээс x 3 нь 1/ хүртэл нэмэгдэж болохыг харж болно. 4, 3-р тэгшитгэлээс - 2/3 хүртэл. Хоёр дахь тэгшитгэл нь илүү чухал юм. Бид x 3 хувьсагчийг үндсэн тоо, x 4 хувьсагчийг чөлөөт тоо болгон хөрвүүлдэг.
Одоо бид x 1 , x 2 ба x 4-ийг шинэ чөлөөт хувьсагч болгон авч байна. x 3 , x 5 , x 6 гэсэн шинэ үндсэн хувьсагчдыг тэдгээрээр илэрхийлье. Системээ авч үзье
x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4
x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4
x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4
Зорилгын функц нь хэлбэрийг авна
Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4
Х 1 ба x 2 хувьсагч нь сөрөг коэффициент бүхий зорилгын функцэд багтсан тул тэдгээрийн утга нэмэгдэх тусам Ф-ийн утга буурах болно. Жишээлбэл, x 2-ыг ав. Системийн 2-р тэгшитгэлээс харахад x 2-ийн утгыг x 2 \u003d 5 хүртэл нэмэгдүүлэх боломжтой (х 5 ³ 0 хүртэл). Энэ тохиолдолд x 1 ба x 4 нь тэг утгыг хадгалж, бусад хувьсагчдын утгууд x 3 = 3/2-тэй тэнцүү байна; x 5 \u003d 0, x 6 \u003d 3/2, өөрөөр хэлбэл дөрөв дэх хүчинтэй шийдэл (0; 5; 3/2; 0; 0; 3/2). Энэ тохиолдолд Ф 4 \u003d 5/4.
Одоо бид x 1 , x 4 болон x 5-ыг шинэ чөлөөт хувьсагч болгон авч байна. x 2 , x 3 , x 6 гэсэн шинэ үндсэн хувьсагчдыг тэдгээрээр илэрхийлье. Системээ авч үзье
x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5
x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5
x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4
Зорилгын функц нь хэлбэрийг авна
F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5
Ф-ийн илэрхийлэл дэх хоёр хувьсагчийн коэффициентүүд эерэг тул Ф-ийн утгыг цаашид бууруулах боломжгүй юм.
Өөрөөр хэлбэл, Ф мин = - 5-ийн хамгийн бага утга, хамгийн сүүлийн боломжит шийдэл (0; 5; 3/2; 0; 0; 3/2) оновчтой байна.
Хувилбар 8. Зорилгын функцийг Ф = 4 x 5 + 2 x 6 болгон ихэсгэ
хязгаарлалттай: x 1 + x 5 + x 6 = 12;
x 2 + 5 x 5 - x 6 \u003d 30;
x 3 + x 5 - 2 x 6 \u003d 6;
2 x 4 + 3 x 5 - 2 x 6 \u003d 18;
Шийдэл:
Тэгшитгэлийн тоо 4, үл мэдэгдэх тоо 6. Иймд r = n - m = 6 - 4 = 2 хувьсагчийг чөлөөт, 4 хувьсагчийг үндсэн гэж сонгож болно. Бид x 5 ба x 6-г үнэгүй, x 1, x 2, x 3, x 4-ийг үндсэн гэж сонгоно. Бид үндсэн хувьсагчдыг чөлөөт хувьсагчаар илэрхийлж, тэгшитгэлийн системийг нэгжийн суурь болгон бууруулна
x 1 \u003d 12 - x 5 - x 6;
x 2 \u003d 30 - 5 x 5 + x 6;
x 3 \u003d 6 - x 5 + 2 x 6;
x 4 \u003d 9 - 3/2 x 5 + x 6;
Бид зорилгын функцийг Ф = 4 x 5 + 2 x 6 хэлбэрээр бичнэ. Бид x 5 = x 6 = 0 чөлөөт хувьсагчдад тэг утгыг оноодог. Энэ тохиолдолд үндсэн хувьсагчид x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 утгуудыг авна. , өөрөөр хэлбэл, бид эхний боломжтой шийдлийг (12, 30, 6, 9, 0,) болон Ф 1 = 0 авах болно.
Чөлөөт хувьсагч хоёулаа зорилтот функцэд эерэг коэффициентээр ордог, өөрөөр хэлбэл F-ийн цаашдын өсөлт боломжтой. Жишээлбэл, x 6-г үндсэн тоо болгон хөрвүүлье. Тэгшитгэл (1) нь x 5 = 12 үед x 1 = 0, (2) ÷ (4) x 6-д эерэг коэффициенттэй орж байгааг харуулж байна. Шинэ суурь руу шилжье: үндсэн хувьсагчид - x 6, x 2, x 3, x 4, free - x 1, x 5. Шинэ үндсэн хувьсагчдыг шинэ үнэгүй хэлбэрээр илэрхийлье.
x 6 \u003d 12 - x 1 - x 5;
x 2 \u003d 42 - x 1 - 6 x 5;
x 3 \u003d 30 - 2 x 1 - 3 x 5;
x 4 \u003d 21 - x 1 - 5/2 x 5;
Зорилгын функц нь Ф = 24 - 2 x 1 + 2 x 5 хэлбэртэй байна;
Бид x 1 = x 5 = 0 чөлөөт хувьсагчдад тэг утгыг оноодог. Энэ тохиолдолд үндсэн хувьсагчид x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 утгуудыг авна. , өөрөөр хэлбэл бид хоёр дахь боломжит шийдлийг (0, 42, 30, 21, 0, 12) олж авах ба Ф 2 = 24 болно.
Зорилтот функц x 5 нь эерэг коэффициентээр ордог, өөрөөр хэлбэл F-ийн цаашдын өсөлт боломжтой. Шинэ суурь руу шилжье: үндсэн хувьсагч - x 6, x 5, x 3, x 4, чөлөөт хувьсагч - x 1 , x 2. Шинэ үндсэн хувьсагчдыг шинэ үнэгүй хэлбэрээр илэрхийлье
x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;
x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;
x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;
x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;
Зорилгын функц нь Ф = 38 - 7/2 x 1 - 1/3 x 2 хэлбэртэй байна;
Чөлөөт хувьсагчид x 1 = x 2 = 0 гэсэн тэг утгыг онооно. Энэ тохиолдолд үндсэн хувьсагчид x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ утгуудыг авна. 2, өөрөөр хэлбэл бид X 3 = (0, 0, 9, 7/2, 7, 5) ба Ф 3 = 38 гэсэн гурав дахь боломжит шийдлийг авах болно.
Хоёр хувьсагч хоёулаа сөрөг коэффициент бүхий зорилтот функцэд ордог, өөрөөр хэлбэл Ф-ийг цаашид нэмэгдүүлэх боломжгүй юм.
Тиймээс хамгийн сүүлийн боломжит шийдэл нь оновчтой, өөрөөр хэлбэл Х opt = (0, 0, 9, 7/2, 7, 5) ба Ф max = 38 байна.
Сонголт 10. Ф \u003d x 2 + x 3 зорилгын функцийг хамгийн их болгох
хязгаарлалт дор: x 1 - x 2 + x 3 \u003d 1,
x 2 - 2 x 3 + x 4 \u003d 2.
Шийдэл:
Тэгшитгэлийн систем - хязгаарлалтууд нь тууштай байдаг, учир нь тэгшитгэлийн системийн матриц ба өргөтгөсөн матрицын зэрэглэлүүд ижил бөгөөд 2-той тэнцүү байна. Тиймээс хоёр хувьсагчийг чөлөөтэй, бусад хоёр хувьсагчийг - үндсэн - байж болно. хоёр чөлөөт нэгээр шугаман байдлаар илэрхийлэгдэнэ.
x 2 ба x 3-ыг чөлөөт хувьсагч гэж авъя.Тэгвэл x 1 ба x 2 хувьсагч нь үндсэн хувьсагч болох бөгөөд үүнийг бид чөлөөт хэлбэрээр илэрхийлэх болно.
x 1 \u003d 1 + x 2 - x 3; (*)
x 4 \u003d 2 - x 2 + 2 x 3;
Зорилтот функцийг аль хэдийн x 2 ба x 3, өөрөөр хэлбэл Ф = x 2 + x 3 хэлбэрээр илэрхийлсэн.
x 2 \u003d 0 ба x 3 \u003d 0 үед үндсэн хувьсагч нь x 1 \u003d 1, x 4 \u003d 2-тэй тэнцүү байх болно.
Бидэнд эхний боломжит шийдэл X 1 = (1, 0, 0, 2), харин Ф 1 = 0 байна.
Ф-ийн өсөлт нь жишээлбэл, эерэг коэффициент бүхий Ф-ийн илэрхийлэлд орсон x 3-ийн утгыг нэмэгдүүлэх замаар боломжтой (x 2 нь тэгтэй тэнцүү хэвээр байна). Системийн эхний тэгшитгэлээс (*) харахад x 3-ийг 1 хүртэл нэмэгдүүлэх боломжтой (х 1 ³0 нөхцөлөөс), өөрөөр хэлбэл энэ тэгшитгэл нь x 3-ийн утгыг нэмэгдүүлэхэд хязгаарлалт тавьдаг. Системийн эхний тэгшитгэл (*) шийдэгдэж байна. Энэ тэгшитгэлийн үндсэн дээр бид x 1 ба x 3 байрыг сольж шинэ суурь руу шилждэг. Одоо үндсэн хувьсагчид x 3 ба x 4, чөлөөт - x 1 ба x 2 байх болно. Одоо бид x 3 ба x 4-ийг x 1 ба x 2-оор илэрхийлдэг.
Бид авна: x 3 \u003d 1 - x 1 + x 2; (**)
x 4 \u003d 4 - 2 x 1 + x 2;
Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2
Чөлөөт хувьсагчдыг тэгтэй тэнцүүлснээр бид хоёр дахь зөвшөөрөгдөх үндсэн шийдлийг олж авна X 2 = (0; 0; 1; 4), үүнд Ф 2 =1 байна.
F-ийн өсөлт нь x 2-ийн өсөлтөөр боломжтой. Сүүлчийн тэгшитгэлийн системээс (**) харахад x 2-ын өсөлт хязгаарлагдмал биш юм. Тиймээс Ф нь бүх том эерэг утгыг авна, өөрөөр хэлбэл Ф max = + ¥.
Тэгэхээр Ф зорилгын функц нь дээрээс хязгаарлагдаагүй тул оновчтой шийдэл байхгүй.
ДААЛГАВАР 2.D. Өгөгдсөнтэй давхар бодлого бич.
анхны даалгавар.
Хувилбар 7. Зорилгын функцийг Ф = 2 хамгийн их болго× x 1 - x 4
хязгаарлалттай: x 1 + x 2 \u003d 20,
x 2 + 2× x 4 ≥ 5,
x 1 + x 2 + x 3 ≤ 8,
x i ≥ 0 (i = 1, 2, 3, 4)
Шийдэл:
Бид хязгаарлалтын системийг нэг, жишээлбэл, 2, 3-р тэгшитгэлд нэмэлт хувьсагч оруулах замаар каноник хэлбэрт оруулдаг.
x 1 + x 2 = 20,
x 2 + 2 × x 4 - x 5 \u003d 5,
- x 1 + x 2 + x 3 + x 6 \u003d 8.
Бид 2-р төрлийн тэгш бус асуудалтай болсон. Давхар асуудал дараах байдлаар харагдах болно.
Зорилгын функцийг багасгах F = 20 × y 1 + 5 × y 2 + 8 × y 3
y 1 - y 3-ийн хувьд ≥ 2,
y1 + y2 + y3 ≥ 0,
y 3 ≥ 0,
2× y2 ≥ 1,
Y2 ≥ 0,
y 3 ≥ 0.
Сонголт 8. Ф \u003d x 2 - x 4 - 3 зорилгын функцийг дээд зэргээр нэмэгдүүлэх× x 5
хязгаарлалттай: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,
— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,
3 × x 2 + x 5 + x 6 = 5,
x i ≥ 0, (би = 1, 6)
Шийдэл:
Бидэнд тэгшитгэл хэлбэрийн хязгаарлалтын систем бүхий хамгийн их байлгах анхны бодлого байна, өөрөөр хэлбэл хос бодлого нь 2-р төрлийн тэгш бус хэлбэртэй, математик загвар нь матриц хэлбэрээр дараах хэлбэртэй байна.
Анхны асуудал: Давхар асуудал:
F = C × X max F = B T × Ymin
дээр А × X \u003d B, A T × Y ≥ C T
Анхны бодлогод зорилгын функц дэх хувьсагчдын коэффициентүүдийн матриц-мөр нь С = (0; 1; 0; -1; -3; 0) хэлбэртэй байна.
Чөлөөт нөхцлийн баганын матриц болон хязгаарлалтын систем дэх хувьсагчдын коэффициентийн матриц нь хэлбэртэй байна.
B \u003d 2, A \u003d 0 - 4 1 2 -1 0
Коэффициентийн шилжүүлсэн матриц, зорилгын функц дэх хувьсагчдын коэффициентүүдийн матриц-мөр, чөлөөт гишүүдийн матриц-баганыг ол.
0 1 0 0 V T \u003d (1; 2; 5)
A T = -1 2 0 C T = -1
Хос бодлогыг дараах хэлбэрээр бичиж болно.
F = y 1 + 2 зорилгын функцийн хамгийн бага утгыг ол × y 2 + 5 × y 3
хязгаарлалт дор y 1 ≥ 0,
2× y 1-4 × y 2 + 3 × y 3 ≥ 1,
- y 1 + 2 × y 2 ≥ -1,
y 1 - y 2 + y 3 ≥ -3,
Сонголт 10. Ф = x 1 + x 2 + x 3 функцийг багасга
хязгаарлагдмал: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,
6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,
8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,
Шийдэл:
Бидэнд тэгш бус байдлын хэлбэрийн хязгаарлалтын системтэй анхны багасгах бодлого байна, өөрөөр хэлбэл хос бодлого нь 3-р төрлийн тэгш хэмтэй хэлбэртэй, математик загвар нь матриц хэлбэрээр дараах хэлбэртэй байна.
Анхны асуудал Хос асуудал
F = C × X мин F \u003d Б Т × Ymax
дээр А × X ≥ B дээр A T × Ю ≤ C T
X ≥ 0 Y ≥ 0
Анхны бодлогод зорилгын функц дэх хувьсагчдын коэффициентийн матриц-мөр, чөлөөт гишүүний матриц-багана, хязгаарлалтын систем дэх хувьсагчдын коэффициентийн матриц хэлбэртэй байна.
C \u003d (1; 1; 1), B \u003d 3, A \u003d 6 4 5
Хос бодлогын матрицуудыг олъё
B T = (2; 3; 4) C T = 3 A T = 9 4 2
Хос асуудлыг дараах байдлаар томъёолсон болно.
Зорилгын функцийг хамгийн их болгох F = 2y 1 + 3y 2 + 4y 3
хязгаарлалт дор 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,
9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,
7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,
y би ≥ 0 (i = 1, 2, 3)
ДААЛГАВАР 2.C. Симплекс хүснэгтийг ашиглан шугаман програмчлалын асуудлыг шийдвэрлэх.
Сонголт 7. Зорилгын функцийг ихэсгэх Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4
хязгаарлалттай: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,
x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,
4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.
Шийдэл:
Бид хязгаарлалтын системийг каноник хэлбэрт оруулдаг
2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)
x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)
4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)
Бидэнд 7 үл мэдэгдэх 3 тэгшитгэлийн систем бий. Бид x 1 , z 1 , z 3-ийг үндсэн 3 хувьсагчаар, x 2 , x 3 , x 4 , z 2-г чөлөөт хувьсагчаар сонгож, үндсэн хувьсагчдыг түүгээр дамжуулан илэрхийлдэг.
(2) -аас бид x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6 байна.
(1) ба (3)-д орлуулснаар бид авна
x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,
z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,
z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,
Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.
Симплекс хүснэгт зохио
I давталтын хүснэгт 1
| Үндсэн АС | Эрх чөлөө. АС | |||||||||
| x 1 | 1 | 1 | — 2 | 5 | — 3 | 0 | — 1 | 0 | 3/8 | |
| z1 | 2 | 0 | 7 | -11 | 1 | 2 | 0 | 1/ 4 | 1/8 | |
| z3 | 4 | 0 | 18 | -17 | 13 | 0 | 4 | 1 | 4/13 | 13/8 |
| Ф | 2 | 0 | — 3 | 7 | — 8 | 0 | — 2 | 0 | 1 |
X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.
II давталт Хүснэгт 2
| x 1 | 14/8 | 1 | 5/8 | 7/8 | 0 | 3/8 | -2/8 | 0 | 2 | — 1 |
| x4 | 1/ 4 | 0 | 7/8 | -11/8 | 1 | 1/8 | 2/8 | 0 | 11/7 | |
| z3 | 6/8 | 0 | 53/8 | 0 | -13/8 | 6/8 | 1 | 6/7 | 8/7 | |
| Ф | 4 | 0 | 4 | — 4 | 0 | 1 | 0 | 0 | 32/7 |
X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.
III давталт Хүснэгт 3
| x 1 | 1 | 1 | — 6 | 0 | 0 | -1 | — 1 | 1/2 | ||
| x4 | 10/ 7 | 0 | 79/7 | 0 | 1 | -17/7 | 10/7 | 11/7 | 11/7 | |
| x 3 | 6/7 | 0 | 53/7 | 1 | 0 | -13/7 | 6/7 | 8/7 | 13/14 | |
| Ф | 52/7 | 0 | 240/7 | 0 | 0 | -45/7 | 24/7 | 32/7 | 45/14 |
X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.
IV давталт Хүснэгт 4
| z1 | 1/ 2 | 1/2 | — 3 | 0 | 0 | 1 | -1/2 | -1/2 | ||
| x4 | 37/ 14 | 17/14 | 56/14 | 0 | 1 | 0 | 3/14 | 5/14 | ||
| x 3 | 25/14 | 13/14 | 28/14 | 1 | 0 | 0 | -1/14 | 3/14 | ||
| Ф | 149/14 | 45/14 | 15 | 0 | 0 | 0 | 3/14 | 19/14 |
X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.
Сүүлийн хүснэгтийн индексийн мөрөнд сөрөг тоо байхгүй, өөрөөр хэлбэл зорилгын функцийн илэрхийлэлд бүгд Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.
Хариулт: Ф max = 149/14,
оновчтой шийдэл (0; 0; 25/14; 37/14; 1/2; 0; 0)
Хувилбар 8. Зорилгын функцийг Ф = 5 x 1 - x 3-ыг багасга
хязгаарлалттай: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,
x 2 + 2 x 4 \u003d 1,
Шийдэл:
Хувьсагчдын тоо 4, матрицын зэрэглэл 2, тиймээс чөлөөт хувьсагчийн тоо r \u003d 4 - 2 \u003d 2, үндсэн хувьсагчдын тоо мөн 2 байна. Бид x 3, x 4-ийг чөлөөт хувьсагчийн хувьд бид x 1, x 2 үндсэн хувьсагчдыг чөлөөт хэлбэрээр илэрхийлж, системийг нэгжийн суурьт шилжүүлнэ.
x 2 \u003d 1 - 2 x 4,
x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4
Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4
Бид тэгшитгэлийн систем ба зорилгын функцийг симплекс хүснэгтэд тохиромжтой хэлбэрээр бичдэг, өөрөөр хэлбэл x 2 + 2 x 4 = 1,
x 1 +2 x 3 - 3 x 4 = 2
Ф + 11 x 3 - 15 x 4 \u003d 10
Ширээ хийцгээе
I давталтын хүснэгт 1
| Үндсэн АС | Эрх чөлөө. АС | ||||||
| x1 | 2 | 1 | 0 | — 3 | 1/2 | ||
| x2 | 1 | 0 | 1 | 0 | 2 | ||
| Ф | 10 | 0 | 0 | 11 | — 15 | — 11/2 |
X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.
II давталт Хүснэгт 2
| x3 | 1 | 1/2 | 0 | 1 | -3/2 | 3/4 | |
| x2 | 1 | 0 | 1 | 0 | 1/2 | ||
| Ф | — 1 | — 11/2 | 0 | 0 | 3/2 | — 3/4 |
X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.
III давталт Хүснэгт 3
| x3 | 7/4 | 1/2 | 3/4 | 1 | 0 | ||
| x4 | 1/2 | 0 | 1/2 | 0 | 1 | ||
| Ф | — 7/4 | — 11/2 | — 3/4 | 0 | 0 |
X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.
Индексийн мөрөнд сүүлийн хүснэгт байхгүй байна эерэг тоонууд, өөрөөр хэлбэл зорилгын функцийн илэрхийлэлд бүгд Г i > 0. Бидэнд I тохиолдол байгаа тул сүүлийн үндсэн шийдэл нь оновчтой байна.
Хариулт: Ф мин = -7/4, оновчтой шийдэл (0; 0; 7/4; 1/2)
********************
Сонголт 10. Зорилгын функцийг багасгах Ф \u003d x 1 + x 2,
хязгаарлалттай: x 1 -2 x 3 + x 4 \u003d 2,
x 2 - x 3 + 2 x 4 \u003d 1,
Шийдэл:
Хувьсагчдын тоо 5, матрицын зэрэглэл нь 3, тиймээс чөлөөт хувьсагчийн тоо r \u003d 6-3 \u003d 2 байна. Бид x 3 ба x 4-ийг чөлөөт хувьсагч болгон авдаг, x 1, x 2, x 5 үндсэн үзүүлэлтүүд. Системийн бүх тэгшитгэлийг аль хэдийн нэг суурь болгон бууруулсан (үндсэн хувьсагчдыг чөлөөт хувьсагчаар илэрхийлсэн) боловч симплекс хүснэгтийг ашиглахад тохиромжгүй хэлбэрээр бичигдсэн байдаг. Бид тэгшитгэлийн системийг хэлбэрээр бичнэ
x 1 - 2 x 3 + x 4 \u003d 2
x 2 - x 3 +2 x 4 \u003d 1
x 5 + x 3 - x 4. = 5
Бид зорилгын функцийг чөлөөт хувьсагчаар илэрхийлж Ф - 3 x 3 +3 x 4 = 3 хэлбэрээр бичнэ.
Ширээ хийцгээе
I давталтын хүснэгт 1
| Үндсэн АС | Эрх чөлөө. АС | |||||||
| x 1 | 2 | 1 | 0 | -2 | 1 | 0 | 2 | -1/2 |
| x 2 | 1 | 0 | 1 | -1 | 0 | 1/2 | 1/2 | |
| x 5 | 5 | 0 | 0 | 1 | -1 | 1 | 1/2 | |
| Ф | 3 | 0 | 0 | -3 | 3 | 0 | -3/2 |
X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.
хүснэгт 2
| x 1 | 3/2 | 1 | -1/2 | -3/2 | 0 | 0 | ||
| x 4 | 1/2 | 0 | 1/2 | -1/2 | 1 | 0 | ||
| x 5 | 11/2 | 0 | 1/2 | 1/2 | 0 | 1 | ||
| Ф | 3/2 | 0 | -3/2 | -3/2 | 0 | 0 |
X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.
Сүүлчийн хүснэгтийн индексийн мөрөнд эерэг тоо байхгүй, өөрөөр хэлбэл зорилгын функцийн илэрхийлэлд бүгд Гi > 0 байна. Бидэнд 1-р тохиолдол байгаа тул сүүлийн үндсэн шийдэл оновчтой байна.
Хариулт: Ф мин = 3/2, оновчтой шийдэл нь (3/2; 0; 0; 1/2; 11/2).
Системийн зөвшөөрөгдөх шийдлүүдийн багцыг хавтгай дээр байгуулъя шугаман тэгш бус байдалЗорилгын функцийн хамгийн бага утгыг геометрийн аргаар олно.
Бид координатын системд x 1 oh 2 шугамыг байгуулдаг
Бид системээр тодорхойлсон хагас хавтгайг олдог. Системийн тэгш бус байдал нь харгалзах хагас хавтгайгаас аль ч цэгт хангагдах тул тэдгээрийг аль нэг цэгээр шалгахад хангалттай. Бид (0;0) цэгийг ашигладаг. Түүний координатыг системийн эхний тэгш бус байдалд орлуулъя. Учир нь , тэгвэл тэгш бус байдал нь (0;0) цэгийг агуулаагүй хагас хавтгайг тодорхойлно. Үүний нэгэн адил бид үлдсэн хагас хавтгайг тодорхойлно. Бид боломжит шийдлүүдийн багцыг олж авсан хагас хавтгайн нийтлэг хэсэг болгон олдог - энэ бол сүүдэртэй газар юм.
Бид вектор ба түүнд перпендикуляр тэг түвшний шугамыг бүтээдэг.
(5) шугамыг векторын чиглэлд шилжүүлснээр бид мужийн хамгийн их цэг нь шугам (3) ба шугамын (2) огтлолцлын А цэг дээр байх болно. Бид тэгшитгэлийн системийн шийдлийг олдог.
Тиймээс бид (13;11) гэсэн санааг олж авлаа.
(5) шугамыг векторын чиглэлд шилжүүлснээр бид бүсийн хамгийн бага цэг нь шугам (1) ба шугамын (4) огтлолцлын B цэг дээр байх болно. Бид тэгшитгэлийн системийн шийдлийг олдог.
Тиймээс бид (6; 6) цэгийг олж авлаа.
2. Тавилгын компани хосолсон кабинет, компьютерийн ширээ үйлдвэрлэдэг. Тэдний үйлдвэрлэл нь түүхий эд (өндөр чанартай хавтан, холбох хэрэгсэл) олдоц, тэдгээрийг боловсруулж буй машинуудын ажиллах хугацаа зэргээр хязгаарлагддаг. Кабинет бүрт 5 м2 самбар, ширээний хувьд 2 м2 шаардлагатай. 10 долларын үнэтэй холбох хэрэгслийг нэг шүүгээнд, 8 долларыг нэг ширээнд зарцуулдаг. Тус компани ханган нийлүүлэгчдээсээ сард 600 м2 хавтан, дагалдах хэрэгслийг 2000 доллараар авах боломжтой. Шүүгээ бүрийн хувьд машинд 7 цаг, ширээн дээр 3 цаг ажиллах шаардлагатай. Сард ердөө 840 цагийн машин ашиглах боломжтой.
Нэг кабинет 100 доллар авчирсан бол ширээ бүр 50 долларын орлого олдог бол пүүс ашгаа нэмэгдүүлэхийн тулд сард хэдэн ширхэг хосолсон кабинет, компьютерийн ширээ үйлдвэрлэх ёстой вэ?
- 1. Бодлогын математик загварыг зохиож, симплекс аргаар шийд.
- 2. Хос бодлогын математик загварыг зохиож, эхийн шийдэлд үндэслэн түүний шийдлийг бичнэ үү.
- 3. Ашигласан нөөцийн хомсдлын түвшинг тодорхойлж, оновчтой төлөвлөгөөний ашигт ажиллагааг зөвтгөх.
- 4. Нөөцийн төрөл тус бүрийн ашиглалтаас хамааран гарцыг цаашид нэмэгдүүлэх боломжийг судлах.
- 5. Шинэ төрлийн бүтээгдэхүүн нэвтрүүлэх боломжийг үнэлэх - номын тавиурууд, хэрэв 1 м 2 самбар, дагалдах хэрэгслийг нэг тавиур үйлдвэрлэхэд 5 доллар зарцуулсан бол 0.25 цаг машин ажиллуулах шаардлагатай бөгөөд нэг тавиурыг борлуулснаас олсон ашиг нь 20 доллар болно.
- 1. Энэ бодлогын математик загвар бүтээцгээе.
Х 1 - шүүгээний үйлдвэрлэлийн хэмжээ, х 2 - хүснэгтийн үйлдвэрлэлийн хэмжээ гэж тэмдэглэнэ. Хязгаарлалтын систем ба зорилгын функцийг бүтээцгээе.
Бид симплекс аргыг ашиглан асуудлыг шийддэг. Үүнийг каноник хэлбэрээр бичье:
Даалгаврын өгөгдлийг хүснэгт хэлбэрээр бичье.
Хүснэгт 1
Учир нь Одоо бүх дельта тэгээс их байна, дараа нь f зорилтын функцийн утгыг цаашид нэмэгдүүлэх боломжгүй бөгөөд бид оновчтой төлөвлөгөөг олж авлаа.
Хэрэв зөвхөн нэг хязгаарлах хүчин зүйл байвал (жишээлбэл, ховор машин) шийдлийг энгийн томъёогоор олж болно (өгүүллийн эхэнд байгаа холбоосыг үзнэ үү). Хэд хэдэн хязгаарлах хүчин зүйл байвал шугаман програмчлалын аргыг хэрэглэнэ.
Шугаман програмчлалудирдлагын шинжлэх ухаанд хэрэглэгдэх хэрэгслүүдийн нийлбэрийг нэрлэсэн нэр юм. Энэ арга нь ахиу ашиг, зардал гэх мэт зарим тоон утгыг нэмэгдүүлэх буюу багасгахын тулд өрсөлдөхүйц үйл ажиллагаануудын дунд хомс нөөцийг хуваарилах асуудлыг шийддэг. Бизнесийн хувьд үүнийг ашгийг нэмэгдүүлэхийн тулд үйлдвэрлэлийн төлөвлөлт, зардлыг багасгахын тулд бүрэлдэхүүн хэсгүүдийг сонгох, ашгийг нэмэгдүүлэхийн тулд хөрөнгө оруулалтын багцын сонголт, зайг багасгахын тулд ачаа тээвэрлэлтийг оновчтой болгох, ажлын үр ашгийг нэмэгдүүлэхийн тулд ажилтнуудын хуваарилалт, ажлын хуваарь зэрэг салбарт ашиглаж болно. цаг хэмнэх захиалга.
Тэмдэглэлийг форматаар, зургийг татаж авах
Шугаман програмчлал нь авч үзэж буй асуудлын математик загварыг бүтээхэд оршино. Үүний дараа шийдлийг график хэлбэрээр (доор авч үзэх болно), Excel (тусдаа авч үзэх болно) эсвэл тусгай компьютерийн програмуудыг ашиглан олж болно.
Математик загвар бүтээх нь хамгийн их байж магадгүй юм хэцүү хэсэгавч үзэж буй асуудлыг хувьсагчид, тэгшитгэл, тэгш бус байдлын системд хөрвүүлэхийг шаарддаг шугаман програмчлал - энэ нь эцсийн дүндээ загварыг эмхэтгэгчийн ур чадвар, туршлага, чадвар, зөн совингоос хамаардаг процесс юм.
Шугаман програмчлалын математик загварыг бий болгох жишээг авч үзье
Николай Кузнецов жижиг механикийн үйлдвэр ажиллуулдаг. Ирэх сард тэрээр хоёр бүтээгдэхүүн (А ба В) үйлдвэрлэхээр төлөвлөж байгаа бөгөөд тодорхой ахиу ашгийг тус тус 2500 ба 3500 рубль гэж тооцож байна.
Хоёр бүтээгдэхүүнийг үйлдвэрлэхэд боловсруулах, түүхий эд, хөдөлмөрийн зардал шаардагдана (Зураг 1). А бүтээгдэхүүний нэгж бүрийг үйлдвэрлэхэд 3 цаг машин боловсруулах, 16 нэгж түүхий эд, 6 нэгж хөдөлмөр зарцуулдаг. Б нэгжид тохирох шаардлага нь 10, 4, 6. Николай ирэх сард 330 цагийн машин боловсруулах, 400 нэгж түүхий эд, 240 нэгж хөдөлмөрөөр хангах боломжтой гэж таамаглаж байна. Үйлдвэрлэлийн процессын технологи нь тухайн сард дор хаяж 12 ширхэг В бүтээгдэхүүн үйлдвэрлэх ёстой.
Цагаан будаа. 1. Нөөцийг ашиглах, хангах
Николай ахиу ашгийг нэмэгдүүлэхийн тулд дараагийн сард үйлдвэрлэх ёстой А ба В бүтээгдэхүүнийхээ тоог тодорхойлохын тулд загвар бүтээхийг хүсч байна.
Шугаман загварыг дөрвөн үе шаттайгаар барьж болно.
Үе шат 1. Хувьсагчийн тодорхойлолт
Оновчлох шаардлагатай зорилтот хувьсагч (үүнийг Z гэж тэмдэглэе) байдаг, өөрөөр хэлбэл, хамгийн их эсвэл багасгах (жишээлбэл, ашиг, орлого, зардал). Николай ахиу ашгийг нэмэгдүүлэхийг эрмэлздэг тул зорилтот хувьсагч нь:
Z = А ба В бүтээгдэхүүний үйлдвэрлэлийн үр дүнд дараагийн сард хүлээн авсан нийт ахиу ашиг (рублээр).
Хэд хэдэн үл мэдэгдэх хувьсагч байдаг (бид тэдгээрийг x 1, x 2, x 3 гэх мэтээр тэмдэглэдэг) зорилгын функцийн оновчтой утгыг олж авахын тулд утгыг нь тодорхойлох шаардлагатай бөгөөд бидний хувьд эдгээр нь нийт ахиу ашиг юм. Энэхүү хувь нэмэрийн ахиуц хэмжээ нь үйлдвэрлэсэн А ба В бүтээгдэхүүний тоо хэмжээнээс хамаарна.Эдгээр утгыг тооцоолох шаардлагатай тул загварт сонирхолтой хувьсагч болно. Тиймээс тэмдэглэе:
x 1 = дараагийн сард үйлдвэрлэсэн А бүтээгдэхүүний нэгжийн тоо.
x 2 = дараагийн сард үйлдвэрлэсэн В бүтээгдэхүүний нэгжийн тоо.
Бүх хувьсагчдыг тодорхой тодорхойлох нь маш чухал; Онцгой анхааралхэмжилтийн нэгж болон хувьсагчид хамаарах цаг хугацааны хувьд анхаарлаа хандуулаарай.
Үе шат. 2. Зорилгын функцийг байгуулах
Зорилгын функц нь шугаман тэгшитгэл бөгөөд хамгийн их эсвэл багассан байх ёстой. Энэ нь хүссэн хувьсагчдаараа илэрхийлэгдсэн зорилтот хувьсагчийг, өөрөөр хэлбэл x 1 , x 2 ... шугаман тэгшитгэлээр илэрхийлсэн Z-г агуулдаг.
Бидний жишээн дээр үйлдвэрлэсэн бүтээгдэхүүн бүр А нь 2500 рубль авчирдаг. ахиу ашиг, мөн х 1 нэгж бүтээгдэхүүн А үйлдвэрлэхэд ахиу ашиг нь 2500 * x 1 байх болно. Үүний нэгэн адил, В бүтээгдэхүүний x 2 нэгжийг үйлдвэрлэсний ахиу ашиг нь 3500 * x 2 байх болно. Тиймээс, х 1 нэгж бүтээгдэхүүн А, х 2 нэгж бүтээгдэхүүн үйлдвэрлэсний улмаас дараагийн сард авсан нийт ахиу ашиг, өөрөөр хэлбэл зорилтот хувьсагч Z нь:
Z = 2500 * x 1 + 3500 * x 2
Николай энэ үзүүлэлтийг дээд зэргээр нэмэгдүүлэхийг эрмэлздэг. Тиймээс, бидний загвар дахь зорилгын функц нь:
Z = 2500 * x 1 + 3500 * x 2-ийг дээд зэргээр нэмэгдүүлэх
Үе шат. 3. Хязгаарлалтын тодорхойлолт
Хязгаарлалт гэдэг нь шаардлагатай хувьсагчдын утгыг хязгаарлах шугаман тэгшитгэл ба/эсвэл тэгш бус байдлын систем юм. Эдгээр нь нөөцийн хүртээмж, технологийн хүчин зүйл, маркетингийн нөхцөл болон бусад шаардлагыг математик байдлаар тусгадаг. Хязгаарлалт нь "бага буюу тэнцүү", "илүү их буюу тэнцүү", "хатуу тэнцүү" гэсэн гурван төрөлтэй байж болно.
Бидний жишээн дээр А, В бүтээгдэхүүн үйлдвэрлэхэд боловсруулах хугацаа, түүхий эд, хөдөлмөр шаардагдах ба эдгээр нөөцийн хүртээмж хязгаарлагдмал байдаг. Эдгээр хоёр бүтээгдэхүүний үйлдвэрлэлийн хэмжээ (жишээ нь x 2-ийн утгууд) нь шаардлагатай нөөцийн хэмжээгээр хязгаарлагдах болно. үйлдвэрлэлийн үйл явц, боломжтой зүйлээс хэтэрч болохгүй. Машин боловсруулах хугацаатай холбоотой нөхцөл байдлыг авч үзье. Бүтээгдэхүүний А нэгж бүрийг үйлдвэрлэхэд гурван цаг машин боловсруулах шаардлагатай бөгөөд хэрэв х 1 нэгж үйлдвэрлэсэн бол энэ нөөцийн 3 * х 1 цаг зарцуулагдана. Б бүтээгдэхүүний нэгж бүрийг үйлдвэрлэхэд 10 цаг шаардагдах бөгөөд хэрэв x 2 бүтээгдэхүүн үйлдвэрлэсэн бол 10 * x 2 цаг шаардагдана. Ийнхүү х 1 нэгж бүтээгдэхүүн А, х 2 нэгж бүтээгдэхүүн В үйлдвэрлэхэд шаардагдах машины нийт хугацаа нь 3 * x 1 + 10 * x 2 байна. тэр ерөнхий утгаМашины ажиллах хугацаа 330 цагаас хэтрэхгүй. Математикийн хувьд үүнийг дараах байдлаар бичнэ.
3 * x 1 + 10 * x 2 ≤ 330
Түүхий эд, хөдөлмөрт ижил төстэй анхаарал хандуулж, өөр хоёр хязгаарлалтыг бичих боломжийг олгодог:
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Эцэст нь хэлэхэд, дор хаяж 12 ширхэг В бүтээгдэхүүнийг үйлдвэрлэх нөхцөл байдгийг тэмдэглэх нь зүйтэй.
Үе шат 4. Сөрөг бус байдлын нөхцөлийг бичих
Хүссэн хувьсагч нь сөрөг тоо байж болохгүй, тэдгээрийг x 1 ≥ 0 ба x 2 ≥ 0 тэгш бус байдлаар бичих ёстой. Бидний жишээн дээр x 2 нь 12-оос бага байж болохгүй гэдгийг дээр тодорхойлсон тул хоёр дахь нөхцөл нь илүүц юм.
Николайгийн үйлдвэрлэлийн бодлогын бүрэн шугаман програмчлалын загварыг дараах байдлаар бичиж болно.
Томруулах: Z = 2500 * x 1 + 3500 * x 2
Үүнд: 3 * x 1 + 10 * x 2 ≤ 330
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Шугаман програмчлалын асуудлыг шийдэх график аргыг авч үзье.
Энэ арга нь зөвхөн шаардлагатай хоёр хувьсагчтай асуудлуудад тохиромжтой. Аргыг харуулахын тулд дээр бүтээсэн загварыг ашиглана.
График дээрх тэнхлэгүүд нь үл мэдэгдэх хоёр хувьсагчийг төлөөлдөг (Зураг 2). Аль хувьсагчийг аль тэнхлэгийн дагуу зурах нь хамаагүй. Эцсийн эцэст харааны диаграммыг бүтээх боломжийг олгох масштабыг сонгох нь чухал юм. Хоёр хувьсагч нь сөрөг биш байх ёстой тул зөвхөн 1-р квадратыг зурна.
Цагаан будаа. 2. Шугаман програмчлалын график тэнхлэгүүд
Жишээлбэл, эхний хязгаарлалтыг авч үзье: 3 * x 1 + 10 * x 2 ≤ 330. Энэ тэгш бус байдал нь шугамын доорх талбайг тодорхойлдог: 3 * x 1 + 10 * x 2 = 330. Энэ шугам нь x тэнхлэг 1-ийг огтолж байна. x 2 \u003d 0, өөрөөр хэлбэл тэгшитгэл нь дараах байдалтай байна: 3 * x 1 + 10 * 0 \u003d 330, түүний шийдэл: x 1 \u003d 330/3 \u003d 110
Үүнтэй адилаар бид бүх хязгаарлалтын нөхцөлд x 1 ба x 2 тэнхлэгтэй огтлолцох цэгүүдийг тооцоолно.
| Зөвшөөрөгдөх хүрээ | Зөвшөөрөгдсөн утгын хязгаар | x тэнхлэгтэй огтлолцох 1 | x тэнхлэгтэй огтлолцох 2 |
| 3 * x 1 + 10 * x 2 ≤ 330 | 3 * x 1 + 10 * x 2 = 330 | x 1 = 110; x 2 = 0 | x 1 = 0; x 2 = 33 |
| 16 * x 1 + 4 * x 2 ≤ 400 | 16 * x 1 + 4 * x 2 = 400 | x 1 = 25; x 2 = 0 | x 1 = 0; x 2 = 100 |
| 6 * x 1 + 6 * x 2 ≤ 240 | 6 * x 1 + 6 * x 2 = 240 | x 1 = 40; x 2 = 0 | x 1 = 0; x 2 = 40 |
| x 2 ≥ 12 | x 2 = 12 | хөндлөн гарахгүй; x тэнхлэг 1-тэй параллель гүйдэг | x 1 = 0; x 2 = 12 |
Графикийн хувьд эхний хязгаарлалтыг Зураг дээр үзүүлэв. 3.
Цагаан будаа. 3. Эхний хязгаарлалтын боломжит шийдлүүдийн хүрээг байгуулах
Сонгосон гурвалжин доторх эсвэл түүний хил дээрх аливаа цэг энэ хязгаарлалтыг дагаж мөрдөх болно. Ийм цэгүүдийг хүчинтэй гэж нэрлэдэг ба гурвалжны гаднах цэгүүдийг хүчингүй гэж нэрлэдэг.
Үүний нэгэн адил бид бусад хязгаарлалтыг график дээр тусгасан болно (Зураг 4). ABCDE сүүдэртэй талбайн доторх эсвэл доторх x 1 ба x 2 утгууд нь загварын бүх хязгаарлалтыг дагаж мөрдөх болно. Ийм бүсийг зөвшөөрөгдөх шийдлийн домэйн гэж нэрлэдэг.
Цагаан будаа. 4. Загварыг бүхэлд нь хэрэгжүүлэх боломжтой шийдлийн талбар
Одоо, боломжит шийдлүүдийн талбарт Z-ийг ихэсгэх x 1 ба x 2 утгуудыг тодорхойлох шаардлагатай. Үүнийг хийхийн тулд зорилгын функцийн тэгшитгэлд:
Z = 2500 * x 1 + 3500 * x 2
бид x 1 ба x 2-ын өмнөх коэффициентүүдийг ижил тоогоор хуваадаг (эсвэл үржүүлдэг), үр дүнд нь гарсан утгууд нь график дээр үзүүлсэн мужид багтдаг; манай тохиолдолд ийм хүрээ 0-ээс 120 хүртэл байна; Тиймээс коэффициентийг 100 (эсвэл 50)-д хувааж болно:
Z = 25x 1 + 35x 2
дараа нь x 1 ба x 2 (25 * 35 = 875) -ийн өмнөх коэффициентүүдийн үржвэртэй тэнцүү утгыг Z онооно:
875 = 25x 1 + 35x 2
эцэст нь x 1 ба x 2 тэнхлэгүүдтэй шугамын огтлолцох цэгүүдийг ол.
Өмсгөөд үзье зорилтот тэгшитгэлхязгаарлалттай адил график дээр (Зураг 5):
Цагаан будаа. 5. Боломжит шийдлийн талбарт зорилгын функцийг (хар тасархай шугам) ашиглах
Z утга нь зорилгын функцийн шугамын туршид тогтмол байна. Z-ийг ихэсгэдэг x 1 ба x 2 утгуудыг олохын тулд зорилгын функцийн шугамыг хамгийн дээд цэгт байрлах зөвшөөрөгдөх шийдлийн талбайн хилийн доторх ийм цэг рүү зэрэгцээ шилжүүлэх хэрэгтэй. зорилгын функцийн анхны шугамаас дээш ба баруун тийш, өөрөөр хэлбэл С цэг хүртэлх зай (Зураг 6).
Цагаан будаа. 6. Боломжит шийдлүүдийн муж дотор зорилгын функцийн шугам дээд цэгтээ хүрсэн (С цэг дээр)
Оновчтой шийдэл нь шийдвэр гаргах хэсгийн туйлын цэгүүдийн аль нэгэнд байрлана гэж дүгнэж болно. Аль нь, энэ нь зорилгын функцийн налуугаас, ямар асуудлыг шийдэж байгаагаас хамаарна: нэмэгдүүлэх эсвэл багасгах. Тиймээс, объектын функцийг зурах шаардлагагүй - шаардлагатай бүх зүйл бол диаграммаас унших эсвэл харгалзах хос тэгшитгэлийг шийдвэрлэх замаар туйлын цэг тус бүрийн x 1 ба x 2 утгыг тодорхойлох явдал юм. Дараа нь олдсон x 1 ба x 2 утгуудыг зорилгын функцэд орлуулж Z-ийн харгалзах утгыг тооцоолно. Хамгийн оновчтой шийдэл нь хамгийн их болгох асуудлыг шийдвэрлэх үед Z-ийн хамгийн их утга, хамгийн бага утгыг олж авах шийдэл юм. багасгах асуудлыг шийдвэрлэх үед.
Жишээлбэл, C цэг дээрх x 1 ба x 2 утгыг тодорхойлъё. С цэг нь 3x 1 + 10x 2 = 330 ба 6x 1 + 6x 2 = 240 гэсэн шугамуудын огтлолцол дээр байгааг анхаарна уу. Энэ тэгшитгэлийн системийн шийдэл нь: x 1 = 10, x 2 = 30 болно. Боломжит шийдлийн талбайн бүх оройн тооцооны үр дүнг хүснэгтэд үзүүлэв.
| Цэг | Утга x 1 | Утга x 2 | Z \u003d 2500x 1 + 3500x 2 |
| ГЭХДЭЭ | 22 | 12 | 97 000 |
| AT | 20 | 20 | 120 000 |
| FROM | 10 | 30 | 130 000 |
| Д | 0 | 33 | 115 500 |
| Э | 0 | 12 | 42 000 |
Тиймээс Николай Кузнец төлөвлөх ёстой дараа сар 10 бүтээгдэхүүн А, 30 бүтээгдэхүүн Б үйлдвэрлэх бөгөөд энэ нь түүнд 130 мянган рублийн ахиу ашиг авах боломжийг олгоно.
Товчхондоо шугаман програмчлалын асуудлыг шийдвэрлэх график аргын мөн чанарыг дараах байдлаар нэгтгэн дүгнэж болно.
- Шийдвэрийн хоёр параметрийг харуулсан график дээр хоёр тэнхлэг зурах; зөвхөн 1-р квадратыг зур.
- Хилийн бүх нөхцлийн тэнхлэгүүдтэй огтлолцох цэгүүдийн координатыг тодорхойлж, x 1 = 0 ба x 2 = 0 утгыг хилийн нөхцлийн тэгшитгэлд ээлжлэн орлуулна.
- Диаграм дээр загварын хязгаарлалтын шугамыг зур.
- График дээрх бүх хязгаарлалтыг хангасан талбайг (зөвшөөрөгдөх шийдвэрийн талбай гэж нэрлэдэг) тодорхойлно. Хэрэв ийм бүс байхгүй бол загвар нь шийдэлгүй болно.
- Шийдвэрлэх хэсгийн туйлын цэгүүдэд хүссэн хувьсагчдын утгыг тодорхойлж, тохиолдол бүрт Z зорилтот хувьсагчийн харгалзах утгыг тооцоол.
- Хамгийн их болгох бодлогын хувьд шийдэл нь Z хамгийн их байх цэг, багасгах бодлогын хувьд шийдэл нь Z хамгийн бага байх цэг юм.
