Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


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


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

Для розв’язування задач лінійного програмування взагалі використовують алгебраїчні методи (для графічний метод використати трудно). Один з універсальних методів є симплексний метод (або метод послідовного поліпшення плану). Ідея цього методу була пропонована ще у 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. Банківська система України і її характеристика




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

<== попередня сторінка | наступна сторінка ==>
Графоаналітичний метод | Алгоритм розв’язання задачі

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

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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