algorytm sympleks programowanie liniowe

0

Próbuje przetestować działanie algorytmu. Opis na stronie
A) https://stexplained.wordpress.com/2014/07/25/metoda-simplex-explained/
jest prawdopodobnie prawidłowy za wyjątkiem warunków stopu.
Powinny być trzy warunki stopu 1) znaleziono rozwiązanie 2) brak rozwiązań 3) funkcja rośnie do nieskończoności
Ze stron
http://www.phpsimplex.com/en/simplex_method_example.htm
https://smart--grid.net/cours-lessons-theory/linear-programming/simplex-method/
wynika że 1) zostaje osiągnięte gdy nie ma wartości ujemnych w rzędzie opisanym w A) jako Zj-Cj i rozwiązanie odczytuje się z kolumny X0. Czyli przykład z A) powinien iść dalej i niepotrzebnie został zatrzymany, bo warunek 3) nie został spełniony, mamy dodatnią wartość w kolumnie X4 wynoszącą 0,5 i nie ma znaczenia że w kolumnie jest zero. 3) byłoby spełnione gdyby w kolumnie nie byłoby żadnych dodatnich wartości. Czy to się zgadza co do tej pory napisałem? No i nie wiem gdzie sprawdzić warunek że nie ma rozwiązań.

Jeśli to możliwe, BARDZO prosiłbym o szybką odpowiedź, bo potrzebuje zaprogramować to zadanie w najbliższych dniach.

0

Pewnie nie takiej odpowiedzi oczekujesz, ale ja się uczyłem na zupełnie innej tablicy tej metody Simplex, więc dam odpowiedź do tej wersji, jaką ja znam.

Bazuję na skrypcie "Metody obliczeniowe optymalizacji" - Dariusz Horla (nie wiem, czy występuje w necie w postaci PDFa - ja mam wersję analogową). Tam jest temat "Postać tablicowa metody simplex, dwufazowa metoda simplex", a od siebie dodam, że jest to forma prymalna (istnieje jeszcze podejście dualne, jak również prymalno-dualne).

Początek jest standardowy, czyli dodanie zmiennych dopełniających (x_3, x_4, x_5). Prawa strona ograniczeń jest wszędzie dodatnia, więc tego nie trzeba zmieniać. Natomiast "maksymalizację" trzeba zamienić na "minimalizację" (poprzez pomnożenie funkcji celu przez minus 1), a na końcu trzeba pamiętać, że wynik będzie z odwrotnym znakiem.

Ze względu na brak informacji o "dopuszczalnym rozwiązaniu początkowym", trzeba skorzystać z metody dwufazowej (tym bardziej, że jeden z wniosków, o których piszesz, jest właśnie na końcu pierwszej fazy metody dwufazowej).

W pierwszej fazie metody Simplex dodajemy tyle kolejnych zmiennych sztucznych, ile jest ograniczeń (w tym przypadku: 3) i zakładamy, że właśnie te trzy zmienne sztuczne są zmiennymi Bazowymi, a tym samym dają punkt dopuszczalny.

W linku masz rozwiązany ten przykład z linku oraz dwa inne przykłady - jeden jako zadanie nieograniczone, drugie jako zadanie sprzeczne (w zadaniu sprzecznym po zakończeniu pierwszej fazy ceny przy zmiennych sztucznych są niezerowe).

https://drive.google.com/file/d/1JH36tTyZcZ60XxGU9dgzsWT5nEzuw5Ld/view?usp=sharing

1 użytkowników online, w tym zalogowanych: 0, gości: 1