• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Загальна характеристика симплекс-методу

Сиплекс-метод розв’язування задач лінійного програмування

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

Розглянемо основну ідею симплекс-методу. Для цього проведемо деякі перетворення задачі лінійного програмування, виділимо основні вимоги алгоритму симплекс методу і введемо деякі спеціальні поняття і терміни.

Будь-яку задачу лінійного програмування можна звести до стандартної форми – основної задачі лінійного програмування (ОЗЛП), де замість обмежень-нерівностей переходять до обмеження-рівностей. Такий запис умов – обмежень зручний для розв’язування задач лінійного програмування симплекс-методом.

Отже, кожне обмеження – нерівність виду

(1)

або у розгорнутому виді:

(1а)

можна замінити рівністю, якщо ввести додаткову змінну . Тоді маємо

(2)

тобто

(3)

Таким чином, система обмежень приймає вигляд:

(4)

а цільову функцію можна записати так:

(5)

Система рівнянь (4), (5) відповідає всім вимогам задач лінійного програмування і використовується для розв’язання симплекс-методом

Вимоги алгоритму симплекс-метода:

обмеження представляються у вигляді системи лінійних рівнянь;

вільні члени повинні бути не менше нуля: ;

всі змінні повинні бути не менше нуля: .

Для запису алгоритму введемо поняття плану задачі та його різновидностей.

План задачі – будь-яке рішення (розв’язок) системи рівнянь.

Компоненти плану – окремі значення змінних.

Допустимий план – план, всі компоненти якого не менше 0, тобто .

Опорний план – план, в якому кількість відмінних від нуля компонентів дорівнює числу рівнянь в системі основних обмежень.

Оптимальний план – допустимий план, при якому цільова функція приймає екстремальне значення.

4.2. Методика побудови симплекс-таблиці

Нехай дана система обмежень у стандартній формі: (див. (3)):

(3а)

де - небазисні (вільні)змінні (НБЗ);

- базисні змінні (БЗ).

*

Аналогічно представимо ЦФ у вигляді: .

У розгорнутому вигляді для та задача на :

(6)

Відповідно системі (6) будуємо симплекс-таблицю:

БЗ	ЗБЗ (значення БЗ)	НБЗ	СВ (симплексне відношення)
		–	–

Приклад.

Представимо модель задачі у вигляді системи (6)

у канонічній формі: (7)

Таблиця 1

БЗ	ЗБЗ	НБЗ	СВ
		–3	–2

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

1. I. Загальна характеристика політичної та правової думки античної Греції.
2. II. ВИРОБНИЧА ХАРАКТЕРИСТИКА ПРОФЕСІЇ
3. II. Морфофункціональна характеристика відділів головного мозку
4. Ni - загальна кількість періодів, протягом яких діє процентна ставка ri.
5. Аварії на хімічно-небезпечних об’єктах та характеристика зон хімічного зараження.
6. Автобіографія. Резюме. Характеристика. Рекомендаційний лист
7. Автокореляційна характеристика системи
8. Амплітудно-частотна характеристика, смуга пропускання і загасання
9. Аплікація як вид образотворчої діяльності дошкільнят, його характеристика.
10. Архітектура СЕП та характеристика АРМ-1, АРМ-2, АРМ-3
11. Афіксальні морфеми. Загальна характеристика
12. Банківська система України і її характеристика

Переглядів: 1221