Ang linear programming, matematikal na pagmomolde ng diskarte kung saan ang isang linear function ay na-maximize o mai-minimize kapag sumasailalim sa iba't ibang mga hadlang. Ang pamamaraan na ito ay naging kapaki-pakinabang para sa paggabay ng dami ng mga pagpapasya sa pagpaplano ng negosyo, sa pang-industriya na engineering, at — sa isang mas mababang sukat — sa sosyal at pisikal na mga agham.
pag-optimize: Programming ng linya
Bagaman malawak na ginagamit ngayon upang malutas ang mga problema sa pang-araw-araw na desisyon, ang linear programming ay medyo hindi kilala bago ang 1947. Walang gawa ng anumang kabuluhan
Ang solusyon ng isang linear na problema sa programming ay binabawasan sa paghahanap ng pinakamabuting halaga na halaga (pinakamalaking o pinakamaliit, depende sa problema) ng linear expression (na tinatawag na ang layunin na function)
napapailalim sa isang hanay ng mga hadlang na ipinahayag bilang hindi pagkakapantay-pantay:
Ang mga a, b's, at c ay mga itinutukoy ng mga kapasidad, pangangailangan, gastos, kita, at iba pang mga kinakailangan at paghihigpit ng problema. Ang pangunahing palagay sa aplikasyon ng pamamaraang ito ay ang magkakaibang mga ugnayan sa pagitan ng hinihingi at pagkakaroon ay magkakasunod; iyon ay, wala sa x i ay itinaas sa isang kapangyarihan maliban sa 1. Upang makuha ang solusyon sa problemang ito, kinakailangan upang mahanap ang solusyon ng system ng mga linear na hindi pagkakapantay-pantay (iyon ay, ang hanay ng mga halaga ng n ang mga variable x i na sabay na nagbibigay-kasiyahan sa lahat ng mga hindi pagkakapantay-pantay). Ang layunin na pagpapaandar ay susuriin sa pamamagitan ng paghahalili ng mga halaga ng x i sa equation na tumutukoy sa f.
Ang mga aplikasyon ng paraan ng pag-programming ng linear ay unang sineseryoso na tinangka noong huling bahagi ng 1930 sa pamamagitan ng Soviet matematika na si Leonid Kantorovich at ng ekonomistang Amerikano na si Wassily Leontief sa mga lugar ng mga iskedyul ng pagmamanupaktura at ng ekonomiya, ayon sa pagkakabanggit, ngunit ang kanilang gawain ay hindi pinansin ng maraming mga dekada. Sa panahon ng World War II, ang linear programming ay malawak na ginamit upang harapin ang transportasyon, pag-iskedyul, at paglalaan ng mga mapagkukunan na napapailalim sa ilang mga paghihigpit tulad ng mga gastos at pagkakaroon. Ang mga application na ito ay nagawa nang malaki upang maitaguyod ang katanggap-tanggap sa pamamaraang ito, na nagkamit ng karagdagang impetus noong 1947 kasama ang pagpapakilala ng American matematiko na si George Dantzig ng simplex na pamamaraan, na lubos na pinasimple ang solusyon ng mga problema sa pag-programming ng linear.
Gayunpaman, habang ang mas maraming masalimuot na mga problema na kinasasangkutan ng higit pang mga variable ay tinangka, ang bilang ng mga kinakailangang operasyon ay lumawak nang malaki at lumampas sa computational na kapasidad ng kahit na ang pinakamalakas na computer. Pagkatapos, noong 1979, natuklasan ng dalubhasang matematiko na si Leonid Khachiyan ang isang polynomial-time algorithm - kung saan lumalaki ang bilang ng mga hakbang sa computational bilang isang kapangyarihan ng bilang ng mga variable kaysa sa exponentially - sa gayon pinapayagan ang solusyon ng hanggang sa hindi ma-access na mga problema. Gayunpaman, ang algorithm ni Khachiyan (tinawag na pamamaraan ng ellipsoid) ay mas mabagal kaysa sa simpleng pamamaraan kung praktikal na inilalapat. Noong 1984 ang matematiko na taga-India na si Narendra Karmarkar ay natuklasan ang isa pang polynomial-time algorithm, ang interior point method, na napatunayan na mapagkumpitensya sa simpleng pamamaraan.
