Курсовая работа: Аналіз методів рішення задачі лінійного програмування симплекс методом

2. Функціональне призначення

Задача лінійного програмування широко використовується для рішення задач прикладної математики.

В сучасній ринковій економіці в умовах жорсткої конкуренції і боротьби за кожен відсоток рентабельності – а, значить, конкурентної здатності – ефективність вирішення задач з багатьма взаємопов’язаними факторами набуває вирішального значення, коли потрібно прорахувати ефективність виробничого процесу з огляду на різні фактори ризику – кон’юнктуру ринку, наявність сировини, доступ до джерел енергії, демографічну ситуацію та навіть наслідки глобального потепління.

3. Аналіз методів розв’язання даної задачі

3.1 Метод потенціалів

Метод потенціалів — розроблений в 1940 радянськими вченими Канторовічем Л. В. та Гавуріним Л. В. в застосуванні до транспортної задачі;

Розглянемо алгоритм даного методу:

1. Порівнюють загальний запас вантажу з сумарним попитом іі у випадку порушення балансу приводять задачу до закритої моделі.

2. Умову задачі записують у формі транспортної таблиці.

3. Будують початковий опорний план перевезень

4. Перевіряють умову для базисних клітин (їх повинно бути m+n-1): якщо ця умова не виконується, то в одну з вільних клітинок (як правило, в клітинку з найменшим тарифом) вписуюють число 0, і така клітина вважається базисною. Однак число 0 записуюють тільки в ті вільні клітинки, які не утворюють циклів з раніше зайнятими клітинками.

5. Обчислюють потенціали u_i iv_j . Кожному постачальнику (кожній стрічці) ставлять у відповідність деяке число u_i , яке називають потенціалом постачальника А_і (і=1,m), і записуюють праворуч таблиці, а кожному споживачу (або стовпчику) – деяке число v_j , яке називають потенціалом споживача В_j (j=1,n), і записують під таблицею. Числа u_i iv_j вибирають так, щоб у будь-якій базисній клітинці їх сума дорівнювала тарифу, тобто u_i +v_j =с_{і j} . Так, як кількість всіх потенціалів u_i iv_j складає m+n, а зайнятих клітинок m+n-1, то для визначення чисел u_i iv_j доведется вирішувати систему із m+n-1 рівнянь з m+n невідомими. Тому одному із невідомих потенціалів надають довільне значення. Тоді інші визначаються однозначно.

6. Для перевірки оптимальності плану переглядають вільні клітинки, для яких визначають оцінки ∆_{і j} – різниця між тарифом клітинки і сумою потенціалів строки і стовпчика, тобто ∆_{і j} = с_{і j} -( u_i +v_j ). Економічно, оцінка покаже на скільки грошових одиниць змінятся транспортні витрати від завантаження даної клітинки одиницею вантажу. Якщо всі оцінки невід′ємні, тобто ∆_{і j} ≥0, то план оптимальний і залишається підрахувати транспортні витрати. Інакше переходять до пункту 7.

7. З від′ємних оцінок ∆_{і j} ≤0 вибирають мінімальну. Нехай це буде ∆_{і k} . Тоді клітинку (1, k) вводять в число базисних, тобто будують цикл по завантаженим клітинкам з початком в цій клітинці і перерозподіляють поставки так, щоб баланс циклу зберігався. Для цьогго вершинам циклу приписують знаки „+” і ”-”, які чергуються, (вільній клітинці (1, k) приписують позитивний знак „+”). В „мінусових” клітинках віднаходять найменший вантаж w , тобто w =minx_{і j} =x_st , який і переміщається клітинками замкнутого циклу, тобто додається до перевозок x_{і j} в клітинках зі знаком „+” (включаючи вільну) і віднімається з перевозок x_{і j} в клітинках із знаком ”-”. З цього слідує, що клітинка (s, t) стане вільною і змінна x_st вийде з базису. Значення інших базисних змінних переписуюються. Таким чином, отримуюють або одержують нову транспортну таблицю с поліпшеним планом, для якого транспортні витрати змінюються на величину ∆_{1 k} *x_st . Переходять до пункту №4.

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

Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.

Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.

Розглянемо опис методу:

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:

(3.2.1)

(3.2.2)

де X = (x₁ , …, x_n ) — вектор змінних, C = (c₁ , …., c_n ), B = (b₁ , …, b_m )T, A_j = (a_{1 j} , …, a_mj )T, j = 1, …, n — задані вектори, T — знак транспонування, та відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану — Тоді

(3.2.3)

(3.2.4)

де значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов A_j розкладається по ним єдиним чином:

(3.2.5)

(3.2.6)

(3.2.7)

де x_ij - коефіцієнт розкладання. Система умов