Симплексний метод розв’язування ЗЛП (СМ)

1.4.1.Загальні положення СМ

СМ є універсальним методом розв’язування ЗЛП. При його реалізації здійснюється орієнтований перебір вершин многогранника планів задачі. Оскільки кількість вершин многогранника планів є скінченною, то алгоритм СМ володіє властивістю скінченності (за скінченну кількість кроків реалізації алгоритму ми одержимо оптимальний розв’язок або покажемо, що цільова функція на множині планів необмежена). Виняток становить явище зациклювання, яке полягає в можливому повторенні циклу обстеження тих самих вершин. На практиці таке явище трапляється дуже рідко.

Обстеження вершин можна почати лише після знаходження початкового опорного плану задачі. Тому весь алгоритм СМ поділяють на два етапи: на першому – знаходять початковий опорний план, а на другому – оптимальний.

В наступних пунктах ми розглянемо реалізацію СМ для ЗЛП, представлених в різних формах.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Геометрична інтерпретація ЗЛП. Графічний метод розв’язування	\|	Алгоритм СМ у формі тотожних перетворень

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.