Зміст
Введення
. Опис завдання
. Опис методу рішення
. Проектування інтерфейсу
. Структура програмного модуля
. Тестування
Висновок
Список використаної літератури та програмних засобів
Додаток 1. Інтерфейс програми
Додаток 2. Лістинг класу SimplexSolve
Введення
Лінійне програмування - математична дисципліна, присвячена теорії і методам вирішення екстремальних задач <# "justify"> Робота присвячена найбільш поширеним методом вирішення завдання лінійного програмування - симплекс-методу. Симплекс-метод є класичним і найбільш опрацьованим методом в лінійному програмуванні. p align="justify"> 1. Опис завдання
Задача лінійного програмування (ЛП) виникає з необхідності оптимально використовувати наявні ресурси. Це завдання, пов'язані з целеобразованию і аналізом цілей і функцій; завдання розробки або вдосконалення структур (виробничих структур підприємств, організованих структур об'єднань); задачі проектування (проектування складних робототехнічних комплексів, гнучких виробничих систем). p align="justify"> В якості конкретних прикладів завдань, які відносяться до області лінійного програмування, можна назвати завдання про використання сировини, завдання про використання потужностей, завдання на складання оптимальної виробничої програми.
Задача ЛП полягає у знаходженні вектора, максимизирующего/минимизирующего лінійну цільову функцію
(1)
при наступних лінійних обмеженнях
(2)
(3)
Запис задачі ЛП у вигляді (1) - (3) називається нормальною формою завдання.
Цю ж задачу ЛП можна представити у векторно-матричної запису:
(4)
де - вектор коефіцієнтів цільової функції,
- вектор рішення,
- вектор вільних членів,
- матриця коефіцієнтів.
Область називається областю допустимих значень (ОДЗ) завдань лінійного програмування. Співвідношення (2), (3) називаються системами обмежень задачі ЛП. Так як, то можна обмежитися вивченням завдання одного типу. p> Рішенням задачі ЛП, або оптимальним планом, називається вектор, що задовольняє системі обмежень завдання і оптимізує цільову функцію.
Інша форма подання задачі ЛП - канонічна. Вона має вигляд:
В
У канонічній формі запису задач лінійного програмування всі змінні, що входять в систему обмежень, повинні бути невід'ємними, а всі обмеження повинні бути представлені равенствами. Будь-яку задачу лінійного програмування можна звести до задачі лінійного програмування в канонічній формі. Для цього в загальному випадку потрібно вміти зводити завдання максимізації до задачі мінімізації; переходити від обмежень нерівностей до обмежень рівностей і замінювати змінні, які не підпорядковуються умові незаперечності. br/>
. Опис методу рішення
Симплекс-метод є найбільш поширеним обчислювальним методом, який може бути застосований для вирішення будь-яких завдань ЛП як вручну, так і за допомогою ЕОМ.
Цей метод дозволяє переходити від одного допустимого рішення до іншого, причому так, що значення цільової функції безперервно зростають. В результаті оптимальне рішення знаходять за кінцеве число кроків. Алгоритм симплекс-методу дозволяє також встановити чи є завдання ЛЗ вирішуваною. p align="justify"> Розглянемо задачу ЛП в канонічній формі. Будемо шукати рішення задачі (6), (7), (8). br/>
(6)
(7)
(8)
0.Положім k = 1. Взявши змінні за вільні і поклавши їх рівними нулю, а, переобозначив в, - за базисні, знаходимо першу крайню точку:
.
1. Заповнимо початкову допустиму симплекс-таблицю
... ... ... 0 ... 00 ... 1 ... 0 ...... .................. ... 0 ... 1
де - вектор коефіцієнтів цільової функції,
- вектор вільних членів,
- матриця коефіцієнтів.
. Якщо для k-тієї крайньої точки всі, то ця точка оптимальна, перехід на пункт 7.
В інших випадках перехід до пункту 3.
3.Находім провідний стовпець. Правило вибору: вибираємо стовпець, в якому самий мінімальний коефіцієнт серед негативних:
В
. Знаходимо провідний рядок за правилом:
В
Якщо всі елементи ведучого шпальти, то завдання ЛП не є вирішуваною, тому що цільова функція не обмежена на множині допустимих значень, перехід ...
