Alam mo kung ano ang ibig sabihin ng pag-optimize ng system para makuha ang pinakamagandang resultang posible kung ikaw ay isang engineering student o isang engineer.
Ang pag-optimize ng isang solusyon ay ang susi sa tagumpay sa lahat mula sa pagbuo ng mga tulay hanggang sa paggawa ng software.
Ang ideya ng isang pangunahing magagawang solusyon ay dumating sa puntong ito.
Ito ay isang pangunahing ideya sa linear programming na nagbibigay-daan sa iyong malaman kung alin sa isang hanay ng mga posibleng solusyon ang pinakamahusay.
Ngunit bakit ito mahalaga? Sa artikulong ito, pag-uusapan ko ang tungkol sa mga pangunahing magagawang solusyon at kung paano magagamit ang mga ito upang malutas ang mga problema sa engineering sa totoong mundo.
Pag-uusapan ko kung paano mahahanap ang mga ito, kung saan sila gawa, at kung bakit sila mahalaga.
Kaya, kung ikaw ay isang bihasang inhinyero o isang mag-aaral na nagsisimula pa lamang, sumama sa amin habang ako ay sumisid sa mundo ng mga pangunahing magagawang solusyon at ipakita sa iyo kung paano gamitin ang kapangyarihan ng linear programming.
Pag-unawa sa Basic Feasible Solution
Pormal na kahulugan:
Isang pangunahing solusyon sa isang linear na modelo ng programa kung saan ang lahat ng mga variable ay nonnegative.
Ang basic feasible solution (BFS) ay isang pangunahing ideya sa linear programming na tumutulong sa paghahanap ng mga pinakamahusay na solusyon.
Ang BFS ay isang solusyon na may pinakamaliit na posibleng bilang ng mga di-zero na variable.
Ito ay isang sulok ng polyhedron ng mga magagawang solusyon.
Sa madaling salita, ang BFS ay isang pangunahing solusyon na nakakatugon sa mga di-negatibong hadlang at nasa posibleng rehiyon o lugar ng problema.
Paghahanap ng Pinakamainam na Basic Feasible Solution
Upang mahanap ang pinakamahusay na BFS, kailangan nating gawin ang sumusunod:
- Isulat ang programa sa karaniwang anyo para sa isang linear sequence.
- Gawing isang augmented matrix ang sistema ng mga hindi pagkakapantay-pantay.
- Alamin kung aling mga variable ang basic at alin ang hindi.
- Alamin kung ano ang mga pangunahing variable sa mga tuntunin ng iba pang mga variable.
- Ilagay ang mga expression na ito sa layunin ng function upang makakuha ng function ng mga variable lang na hindi basic.
- Maghanap ng isang di-basic na variable na maaaring dagdagan nang hindi nilalabag ang anumang mga hadlang at na gagawing mas mahusay ang layunin ng function.
Ang variable na ito ay isa na ngayong pangunahing variable, at ang isa sa iba pang mga pangunahing variable ay hindi na isang pangunahing variable.
Kung mayroong pinakamainam na solusyon, dapat itong nasa isa sa mga dulo, o vertices, ng rehiyon kung saan posible ang mga solusyon.
Kaya, kung ang isang LP ay may pinakamainam na solusyon, mayroon itong pinakamainam na solusyon sa isang matinding punto ng magagawa na hanay.
Gayundin, palaging may pinakamainam na BFS kung mayroong pinakamainam na solusyon.
Gamit ang Simplex Method para Makahanap ng Pinakamainam na BFS
Ang Simplex Method ay isang algorithm para sa paglutas ng mga problema sa linear programming.
Lumilipat ito mula sa isang BFS patungo sa isang "katabing" BFS sa pamamagitan ng paggamit ng pivot procedure.
Sa pamamaraang pivot, pinipili ang isang di-basic na variable upang maging pangunahing variable, at pagkatapos ay ginagamit ang kasalukuyang BFS upang malutas ang mga bagong pangunahing variable.
Kapag walang di-basic na variable ang maaaring baguhin upang gawing mas mahusay ang layunin function, ang algorithm ay tapos na.
Bakit Mahalaga ang Mga Pangunahing Magagawang Solusyon para sa Paglutas ng Mga Kumplikadong Problema sa Engineering
Mahirap pa bang intindihin? Hayaan akong baguhin nang kaunti ang pananaw:
Sino pa rin ang nangangailangan ng simple at maisasagawang mga sagot? Ihagis lang ang lahat at umasa sa ikabubuti.
Pagkatapos ng lahat, sino ang nangangailangan ng pag-optimize kapag ang kaguluhan ay mas masaya? Maligayang pagdating sa mundo ng mga di-negatibong variable, kung saan ang lahat ay isang mungkahi lamang at ang kabiguan ay halos tiyak.
O kaya naman?
Tuklasin natin kung bakit ang tila pangunahing konsepto ng mga pangunahing magagawang solusyon ay hindi mahalaga at kung bakit maaaring maging susi lamang ang mga ito sa paglutas kahit na ang pinakamasalimuot na mga problema sa engineering.
Okay, joke lang iyon na ginawang parang TV ad.
Ngayon bumalik tayo sa paliwanag.
Paghahanap ng Basic Feasible Solution
Ang isang basic feasible solution (BFS) ay isang solusyon sa isang linear na problema sa pag-optimize na nakakatugon sa lahat ng mga hadlang at may pinakamaliit na bilang ng mga di-zero na variable.
Ang bawat BFS ay isang sulok ng polyhedron ng mga magagawang solusyon mula sa isang geometric na punto ng view.
Kung mayroong pinakamahusay na solusyon, dapat ding mayroong pinakamahusay na unang hakbang.
Sa artikulong ito, pag-uusapan natin kung paano maghanap ng isang paunang pangunahing solusyon na magagawa, kung paano hanapin ang lahat ng mga pangunahing solusyon na magagawa, at kung paano makahanap ng isang pangunahing solusyon na magagawa na walang mga slack na variable.
Paghahanap ng Initial Basic Feasible Solution
Maaari kaming gumamit ng iba't ibang paraan, depende sa kung paano ise-set up ang problema, upang makahanap ng paunang pangunahing solusyon na gumagana para sa isang linear na problema sa pag-optimize.
Ang isang paraan ay ang magdagdag ng mga slack na variable sa mga hadlang sa hindi pagkakapantay-pantay at itakda ang lahat ng iba pang variable sa zero.
Ang mga slack na variable ay nagiging pangunahing mga variable, at ang iba ay mga di-basic na variable.
Ang two-phase Simplex Method ay isa pang paraan upang malutas ang problema.
Ang pamamaraang ito ay nagsasangkot ng paglutas ng isang karagdagang linear na problema sa programming upang makahanap ng isang paunang pangunahing solusyon na magagawa.
Kapag natagpuan ang isang paunang pangunahing solusyon na magagawa, ang Simplex na Paraan ay maaaring gamitin upang lumipat mula sa isang pangunahing solusyon na magagawa patungo sa susunod at pagkatapos ay sa pinakamahusay na solusyon.
Paghahanap ng Lahat ng Pangunahing Magagawang Solusyon
Maaaring mayroong higit sa isang pangunahing solusyon na gumagana para sa isang linear na programa.
Mababago natin ang system sa pamamagitan ng pagdaragdag ng mga slack na variable at pagkatapos ay gamitin ang bagong system upang mahanap ang lahat ng mga pangunahing magagawang solusyon para sa isang linear na programa.
Pagkatapos, ang mga pangunahing magagawang solusyon na ito ay ginagamit upang mahanap ang mga pangunahing magagawang solusyon para sa orihinal na problema.
Paghahanap ng Basic Feasible Solution na Walang Slack Variable
Kailangan nating gumamit ng mga slack na variable upang maalis ang mga hindi gaanong hadlang upang makahanap tayo ng pangunahing solusyon na gumagana nang walang mga slack na variable.
Ang isang slack variable ay ang pagkakaiba lamang sa pagitan ng kanang bahagi ng isang hadlang at kaliwang bahagi.
Halimbawa, para sa unang pagpilit, tinukoy namin ang isang slack variable x4 = 14 - 2x1 - x2 - x3. Sa mga tuntunin ng bagong variable na ito, ang unang constraint ay katumbas lamang ng x4 ≥ 0, na isang positivity constraint para sa x4.
Kapag idinagdag namin ang mga slack na variable na ito, nakakakuha kami ng linear na programa na kapareho ng orihinal, maliban na ang lahat ng mga hadlang ay alinman sa mga equation o mga hadlang na nagsasabing positibo ang isang bagay.
Ang hanay ng mga pangunahing variable, na may mga halaga maliban sa zero sa pangunahing solusyon, ay tinatawag na batayan.
Ang mga variable na may halagang zero sa pangunahing solusyon ay hindi mga pangunahing variable.
Upang mahanap ang pinakamahusay na solusyon, kailangan nating maghanap ng vector x na nakakatugon sa lahat ng mga panuntunan at nakakakuha ng pinakamalaki o pinakamaliit na halaga para sa layunin.
Ngunit ang paghahanap ng pinakamahusay na solusyon ay nangangailangan ng higit pang mga hakbang kaysa sa paghahanap lamang ng solusyon na gumagana at walang malubay na mga variable.
Hindi laging posible na makahanap ng pangunahing solusyon na walang malubay na mga variable, lalo na para sa mga problema na may mas kaunting mga hadlang.
Upang makahanap ng pangunahing magagawang solusyon, kailangan mong gumamit ng simplex na paraan o isa pang linear programming algorithm upang maghanap ng solusyon na nakakatugon sa lahat ng mga hadlang at may pinakamakaunting di-zero na mga variable.
Mga Katangian at Kahalagahan ng Basic Feasible Solution
Mga Katangian ng Basic Feasible Solution
Ang isang pangunahing magagawang solusyon ay may pinakamaraming m variable na hindi zero at hindi bababa sa nm variable na zero, kung saan ang n ay ang bilang ng mga variable ng desisyon at m ay ang bilang ng mga hadlang.
Ang BFS ay isang sulok ng polyhedron ng mga posibleng solusyon, at ang bawat BFS ay may n aktibong mga hadlang na linearly independent.
Kung mayroong pinakamahusay na solusyon, dapat ding mayroong pinakamahusay na unang hakbang.
Ang pinakamahalagang bagay tungkol sa mga pangunahing magagawa na solusyon ay ang mga ito ang mga dulo ng hanay ng mga convex na solusyon para sa isang linear na problema sa programming.
Upang mahanap ang pinakamahusay na sagot, ang simplex algorithm ay dumadaan sa isang serye ng mga BFS.
Ang Simplex Algorithm ay naghahanap sa lahat ng mga pangunahing posibleng solusyon sa isang organisadong paraan upang mahanap ang pinakamahusay.
Kahalagahan ng Basic Feasible Solution
Ang paghahanap ng pangunahing solusyon na posible ay mahalaga dahil nakakatulong ito na mahanap ang pinakamahusay na sagot sa mga problema sa linear programming.
Nagbibigay din ito ng mga kumplikadong algorithm ng isang lugar upang magsimula at maaaring magamit upang malaman kung ang isang linear na programa ay posible o hindi.
Upang mahanap ang lahat ng pangunahing magagawang solusyon para sa isang linear na programa, maaari mong baguhin ang system sa pamamagitan ng pagdaragdag ng mga slack na variable at pagkatapos ay gamitin ang binagong sistema upang mahanap ang lahat ng pangunahing magagawang solusyon.
Pagkatapos, ang mga pangunahing magagawang solusyon na ito ay ginagamit upang mahanap ang mga pangunahing magagawang solusyon para sa orihinal na problema.
Video: Mga Pangunahing Magagawang Solusyon
Tip: I-on ang caption button kung kailangan mo ito. Piliin ang "awtomatikong pagsasalin" sa button ng mga setting, kung hindi ka pamilyar sa sinasalitang wika. Maaaring kailanganin mong i-click muna ang wika ng video bago maging available ang iyong paboritong wika para sa pagsasalin.
Mga kaso ng paggamit
| Ginamit sa: | Paglalarawan: |
|---|---|
| Paglalaan ng Mga Mapagkukunan: | Ang BFS ay maaaring gamitin upang hatiin ang limitadong mga mapagkukunan sa ilang mga proyekto upang ang pinakamaraming magagawa sa pinakamaliit. Maaaring gamitin ang paraang ito sa maraming iba't ibang larangan, tulad ng transportasyon, pagsasaka, at pananalapi. |
| Pag-optimize ng Network: | Maaaring gamitin ang BFS para mas gumana ang mga network ng komunikasyon, transportasyon, at logistik. Makakatulong ang BFS na mahanap ang pinakamahusay na mga ruta para sa mga produkto at serbisyo, bawasan ang oras at pera na ginugol sa transportasyon, at pabilisin at gumawa ng mas tumpak na mga paghahatid. |
| Pagpaplano para sa Produksyon: | Maaaring gamitin ang BFS upang magplano ng produksyon upang ang mga mapagkukunan tulad ng paggawa, hilaw na materyales, at kagamitan ay magamit sa pinakamahusay na paraan na posible upang masulit ang mga ito. Makakatulong ang BFS na mapababa ang mga gastos sa produksyon, bawasan ang basura, at pahusayin ang kahusayan. |
| Pagpaplanong Pananalapi: | Sa pagpaplano ng pananalapi, maaaring gamitin ang BFS para i-optimize ang mga portfolio ng pamumuhunan, babaan ang panganib, at maibalik ang pinakamaraming pera. Makakatulong ang BFS na mahanap ang pinakamahusay na paraan upang hatiin ang mga asset, babaan ang mga gastos sa transaksyon, at kumita ng mas maraming pera. |
| Pamamahala ng Supply Chain: | Maaaring gamitin ang BFS upang mapabuti ang daloy ng mga produkto at serbisyo mula sa mga supplier patungo sa mga customer bilang bahagi ng pamamahala ng supply chain. Makakatulong ang BFS na malaman ang pinakamainam na dami ng stock na mananatili, paikliin ang mga oras ng lead, at pagbutihin ang serbisyo sa customer. |
Konklusyon
Habang ang pagtingin na ito sa mga pangunahing magagawang solusyon ay malapit nang matapos, malinaw na ang mga ito ay isang mahalagang tool para sa sinumang engineer o engineering student.
Mula sa pag-iisip ng pinakamahusay na paraan upang bumuo ng isang kumplikadong sistema hanggang sa sulitin ang mga mapagkukunang magagamit, ang mga pangunahing magagawang solusyon ay nagbibigay ng isang balangkas para sa pagkuha ng pinakamahusay na posibleng resulta.
Ngunit higit pa sa pagiging kapaki-pakinabang, ipinapakita nila kung gaano kaganda at kaganda ang matematika.
Nakakamangha na maaari mong pakuluan ang mga kumplikadong problema sa isang simpleng hanay ng mga equation at pagkatapos ay gamitin ang mga equation na iyon upang malutas ang mga problema sa totoong mundo.
Ito ay isang magandang paalala na ang engineering ay tungkol sa paglutas ng mga problema, at na sa pamamagitan ng paggamit ng kapangyarihan ng matematika, makakahanap tayo ng mga sagot na dating naisip na imposible.
Kaya, habang natututo ka pa tungkol sa engineering, tandaan kung ano ang iyong natutunan tungkol sa mga simpleng solusyon na gumagana at ginagamit ang mga ito upang gawing mas mahusay, mas mahusay na lugar ang mundo.
Mga link at sanggunian
Mga Aklat:
- Linear Programming: Mga Pundasyon at Extension
- Linear Programming: Teorya at Aplikasyon
Ibahagi sa…
