Linear programming

Men eng yaxshisini oxirigacha saqlab qoldim. Chiziqli dasturlash men bilgan eng ajoyib narsalardan biridir.

Chiziqli dasturlash ba'zi cheklovlarni hisobga olgan holda biror narsani maksimal darajada oshirish uchun ishlatiladi. Misol uchun, sizning kompaniyangiz ikkita mahsulot, ko'ylak va sumka ishlab chiqaradi deylik. Ko'ylaklarga 1 metr mato va 5 ta tugma kerak. Totes uchun 2 metr mato va 2 tugma kerak. Sizda 11 metr mato va 20 tugma bor. Siz har bir ko'ylak uchun 2 dollar va sumka uchun 3 dollar olasiz. Daromadingizni oshirish uchun qancha ko'ylak va sumka tikishingiz kerak?

Bu erda siz maksimal foyda olishga harakat qilyapsiz va sizda mavjud bo'lgan materiallar miqdori bilan cheklanasiz.

Yana bir misol: siz siyosatchisiz va siz olgan ovozlar sonini maksimal darajada oshirishni xohlaysiz. Sizning tadqiqotingiz shuni ko'rsatdiki, San-Fransiskalikdan har bir ovoz yoki Chikagolikdan 1,5 soat/ovoz uchun o'rtacha bir soatlik ish (marketing, tadqiqot va hokazo) kerak bo'ladi. Sizga kamida 500 ta San-Fransiskalik va kamida 300 ta Chikagolik kerak. Sizda 50 kun bor. Shuningdek, u sizga $2/San-Fransiskaga nisbatan $1/Chikagoga tushadi. Sizning umumiy byudjetingiz 1500 dollar. Siz olishingiz mumkin bo'lgan umumiy ovozlarning maksimal soni (San-Fransisko + Chikago)?

Bu erda siz ovozlarni maksimal darajada oshirishga harakat qilyapsiz va vaqt va pul bilan cheklanasiz.

Siz shunday deb o'ylayotgandirsiz: "Siz ushbu kitobda ko'plab optimallashtirish mavzulari haqida gapirgansiz. Ular chiziqli dasturlash bilan qanday bog'liq?" Barcha grafik algoritmlari chiziqli dasturlash orqali amalga oshirilishi mumkin. Chiziqli dasturlash ancha umumiy asos bo'lib, grafik muammolar uning kichik to'plamidir. Umid qilamanki, aqlingiz puchga chiqdi!

Chiziqli dasturlash Simpleks algoritmidan foydalanadi. Bu murakkab algoritm, shuning uchun men uni ushbu kitobga kiritmadim. Agar siz optimallashtirishga qiziqsangiz, chiziqli dasturlashni qidiring!