dnes je 29.3.2024

Input:

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

11.1.2008, , Zdroj: Verlag Dashöfer

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 ajxj, xjbj. 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.

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

Pro úlohy se speciální strukturou byly vyvinuty

Nahrávám...
Nahrávám...