Další metody řešení úloh lineárního programování

17.4.7

Další metody řešení úloh lineárního programování

Doc. Ing. Alois Fiala, CSc.

Pro řešení úloh LP existuje kromě popsané verze simplexové metody ještě řada dalších metod. Jsou to jednak další verze simplexové metody, jednak metody pro řešení speciálních a rozsáhlých úloh a také metody s polynomiální výpočetní složitostí.

Další verze simplexové metody:

• Revidovaná simplexová metoda: Při použití této metody se neuchovává a neupravuje celá simplexová tabulka, ale pouze matice B^-1. Na základě maticového vyjádření simplexové tabulky se počítá pouze to, co je aktuálně zapotřebí.

• Metoda pro řešení úloh s explicitními mezemi proměnných: Jedná se o úlohy, v nichž se vyskytují podmínky tvaru a_j ≤ x_j, x_j ≤ b_j. V této metodě se uvedené podmínky neuvažují explicitně, ale jsou zohledněny v algoritmu metody. Naproti tomu při použití normální simplexové metody musíme s těmito podmínkami zacházet jako s vlastními omezeními, tj. přidat do nich doplňkové a případně pomocné proměnné a upravovat je v průběhu výpočtu.

• Metody založené na teorii duality: duálně simplexová metoda, primárně duální metoda.

 NahoruMetody pro řešení speciálních úloh

Pro úlohy se speciální strukturou byly vyvinuty…