ЗМІСТ
Введення
1. Постановка завдання лінійного програмування
1.1 Форми завдання лінійного програмування
1.2 Перехід до канонічної формі
2. Симплекс-метод
2.1 Теоретичні основи симплекс-методу
2.2 Прямий алгоритм симплексного методу
3. Метод Гоморі
4. Математична і технічна постановка задачі. Програмна реалізація. Опис проекту
4.1 Запуск
4.2 Опис графічного інтерфейсу
4.3 Опис створених функцій
Висновок
Список літератури
В
ВСТУП
Колосальні темпи технічного прогресу породили проблему створення систем управління складними системами. Ця проблема призводить до необхідності побудови математичних моделей прийняття оптимальних рішень.
Сукупність математичних методів, що займаються питаннями вибору на заданій множині допустимих рішень того рішення, яке за встановленими критеріями є оптимальним, становить математичну дисципліну В«дослідження операційВ».
У свою чергу, дослідження операцій поділяється на ряд самостійних дисциплін, а в даній роботі ми зіткнемося із завданням розв'язання лінійної програми симплексним методом у звичайному, целочисленном і частково целочисленном варіантах.
В
1. ПОСТАНОВКА ЗАВДАННЯ Лінійного програмування [2]
В
1.1 Форми завдання лінійного програмування
У загальному вигляді задача лінійного програмування (надалі ЗЛП) може бути сформульована як задача знаходження найбільшого значення лінійної функції
(1.1)
на деякій множині D ГЊ R n , де x ГЋ D задовольняють системі обмежень
В В В В
(1.2)
і, можливо, обмеженням
(1.3)
He применшуючи спільності, можна вважати, що в системі (1.2) перші т обмежень є нерівностями, а наступні - l-рівняннями. Очевидно, цього завжди можна домогтися за рахунок простого переупорядковування обмежень. Щодо направлення знака нерівності будемо припускати, що ліва частина менша або дорівнює правій. Домогтися цього можна, помноживши на (-1) обидві частини тих нерівностей, які мають протилежний знак. Обмеження (1.3), взагалі кажучи, можуть бути розглянуті як окремий випадок обмежень у формі нерівностей, але в силу особливої вЂ‹вЂ‹структури їх зазвичай виділяють окремо і називають умовами невід'ємності (або тривіальними обмеженнями).
Додатково слід зауважити, що вибір типу шуканого екстремуму (максимуму або мінімуму) також носить відносний характер. Так, завдання пошуку максимуму функції
(1.4)
еквівалентна задачі пошуку мінімуму функції
(1.5)
Часто умови задачі (1.1) - (1.3), що містить обмеження тільки типу нерівностей, буває зручно записувати у скороченій матричної формі
(1.6)
де з і x - вектори з простору R n , b - вектор з простору R m , a А...
