Симплекс метод

Извор: ВикиЕТФ

Симплекс метод је назив за алгоритам који служи за решавање једне врсте оптимизациониих проблема. Проблем који треба решити је овакав: треба максимизовати или минимизовати неки израз, уз услове који су дати. Проблем који се често наводи као пример је следећи (транспортни проблем):

Нека су S1 и S2 стоваришта неке робе, а P1, P2 и P3 потрошачи. Количина робе у стоваришту Si једнака је ai (i = 1, 2), а потрошач Pj има потребу за количином bj (j = 1 ,2 ,3), при чему је a1 + a2 = b1 + b2 + b3. Цена превоза јединице количине ове робе из стоваришта Si до потрошача Pj је једнака cij. Коју количину робе из ког складишта треба превести до ког произвођача, а да цена буде најмања?

Математичка представа проблема

Математички, проблем који се решава овом методом записује се овако: Наћи максимум/минимум функције:

Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): F = c_1 x_1 + c_2 x_2 + ... + c_n x_n


уз услове:

Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n = b_2 \\ . \\ . \\ . \\ a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n = b_m \\ x_1 \ge 0, x_2 \ge 0, ..., x_n \ge 0


Функција F назива се функција циља. Овај проблем је дат у каноничном облику. Проблем може бити предтсављен и на другачије начине. О другим начинима представљања проблема и трансофрмацијама којима се проблем овде дат пребацује у други облик погледајте у другом делу овог текста.

Симплекс метод

Овде нећемо приказати како се дошло до овог алгоритма. Ако читаоца то интересује, препорука је књига професора Д. Цветковића и С. Симића Одабрана поглавља из дискретне математике.

Алгоритам је итеративан, т.ј. почиње се од једног решења које се, применом одговарајућих трансформација, покушава да побољша.

За рачунање се користе симплекс таблица, у којој је на неки начин предтсављен проблем. Затим се, корак по корак, подаци из ове таблице побољшавају тако да задовоље услове задатка. Први корак који ваља урадити је припремити почетну симплекс таблицу. Из улазних ограничења, симплекс таблица се попуњава овако:

Почетна симплекс таблица
-d Column heading 2 Column heading 3
Row heading 1 Cell 2 Cell 3
Row heading A Cell B Cell C
Личне алатке
Именски простори
Варијанте
Акције
Навигација
Алатке