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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

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