Зміст
Введення
1. Опис завдання
2. Опис методу рішення
3. Проектування інтерфейсу
4. Структура програмного модуля
5. Тестування
Висновок
Список використаної літератури та програмних засобів
Додаток 1. Інтерфейс програми
Додаток 2. Лістинг класу SimplexSolve
Введення
Лінійне програмування - Математична дисципліна, присвячена теорії і методам вирішення екстремальних задач на множинах n-мірного векторного простору, що задаються системами лінійних рівнянь і нерівностей.
Лінійне програмування є окремим випадком опуклого програмування, яке в свою чергу є окремим випадком математичного програмування. Термін В«ПрограмуванняВ» потрібно розуміти в сенсі В«плануванняВ». Він був запропонований в середині 1940-х років Джорджем Данцигом, одним із засновників лінійного програмування, ще до того, як комп'ютери були використані для рішення лінійних задач оптимізації.
Робота присвячена найбільш поширеній методу рішення задачі лінійного програмування - симплекс-методу. Симплекс-метод є класичним і найбільш опрацьованим методом в лінійному програмуванні.
1. Опис завдання
Задача лінійного програмування (ЛП) виникає з необхідності оптимально використовувати наявні ресурси. Це завдання, пов'язані з целеобразования і аналізом цілей і функцій; завдання розробки або вдосконалення структур (виробничих структур підприємств, організованих структур об'єднань); завдання проектування (проектування складних робототехнічних комплексів, гнучких виробничих систем).
В Як конкретних прикладів завдань, які ставляться до області лінійного програмування, можна назвати задачу про використання сировини, задачу про використанні потужностей, завдання на складання оптимальної виробничої програми.
Задача ЛП полягає у відшуканні вектора, максимизирующего/мінімізує лінійну цільову функцію
(1)
при наступних лінійних обмеженнях
(2)
(3)
Запис завдання ЛП у вигляді (1) - (3) називається нормальною формою завдання.
Цю ж задачу ЛП можна представити у векторно-матричній запису:
(4)
де - вектор коефіцієнтів цільової функції,
- вектор рішення,
- вектор вільних членів,
- матриця коефіцієнтів.
Область називається областю допустимих значень (ОДЗ) задач лінійного програмування. Співвідношення (2), (3) називаються системами обмежень задачі ЛП. Так як, то можна обмежитися вивченням завдання одного типу.
Рішенням завдання ЛЗ, або оптимальним планом, називається вектор, що задовольняє системі обмежень задачі і оптимізуючий цільову функцію.
Інша форма представлення задачі ЛП - канонічна. Вона має вигляд:
В канонічній формі запису задач лінійного програмування всі змінні, входять у систему обмежень, повинні бути невід'ємними, а всі обмеження повинні бути представлені рівностями. Будь-яку задачу лінійного програмування можна звести до задачі лінійного програмування в канонічній формі. Для цього в загальному випадку потрібно вміти зводити задачу максимізації до задачі мінімізації; переходити від обмежень нерівностей до обмежень рівностей і замінювати змінні, які не підкоряються умові неотрицательности.
2. Опис методу рішення
Симплекс-метод є найбільш поширеним обчислювальним методом, який може бути застосований для вирішення будь-яких задач ЛП як вручну, так і за допомогою ЕОМ.
Цей метод дозволяє переходити від одного припустимого рішення до іншого, причому так, що значення цільової функції безперервно зростають. У результаті оптимальний рішення знаходять за кінцеве число кроків. Алгоритм симплекс-методу дозволяє також встановити чи є задача ЛП вирішуваною.
Розглянемо задачу ЛП в канонічній формі. Будемо шукати рішення задачі (6), (7), (8).
(6)
(7)
(8)
0. Покладемо k = 1. Взявши змінні за вільні і поклавши їх рівними нулю, а, переобозначив в, - за базисні, знаходимо першу крайню точку:
.
1. Заповнимо початкову допустиму симплекс-таблицю
...
...
...
0
...
0
0
...
1
...
0
...
...
...
...
...
...
...
...
...
0
...
1
де - вектор коефіцієнтів цільової функції,
- вектор вільних членів,
- матриця коефіцієнтів.
2. Якщо для k-тої крайньої точки все, то ця точка оптимальна, перехід на пункт 7.
В інших випадках перехід до пункту 3.
3. Знаходимо провідний стовпець. Правило вибору: вибираємо стовпець, в якому самий мінімальний коефіцієнт серед негативних:
4. Знаходимо провідну рядок за правилом:
Якщо всі елементи провідного стовпця, то задача ЛП не є розв'язною, тому що цільова функція не обмежена на множині допустимих значень, перехід на пункт 7.
Таким чином, провідний елемент.
5. Виконуємо один крок методу Гаусса: виводимо змінну з індексом з числа базисних, а змінну з індексом вводимо в базис. Нові елементи провідної рядки знаходяться за формулою:
Нові значення елементів решти рядків матриці:
,
Всі елементи у провідному стовпці рівні 0, тоді як сам ведучий елемент рівний 1.
6. Отримуємо (k + 1) крайню точку. Вважаючи k = k + 1, розбудовуємо симплекс-таблицю і переходимо до пункту 2.
7. Кінець рішення.
3. Проектування інтерфейсу
Розроблене додаток має простий одновіконний інтерфейс з набором всіх необхідних інструментів для роботи з програмою.
Вгорі вікна стандартно розташовується рядок меню (JMenu), містить підменю (JSubMenu) Файл, Режим роботи, Довідка. У підменю Файл доступні наступні пункти меню (JMenuItem): Відкрити файл, Вихід. У підменю Режим роботи з допомогою Групи радіокнопок (JRadioButton Group) здійснюється взаємовиключний вибір одного з двох режимів роботи: автоматичний, режим навчання. З підменю Довідка доступний виклик вікна В«Про програмуВ» (SimplexAboutBox).
Під рядком меню розташовується панель інструментів, дублююча функції, доступні з рядка меню, але надає більш зручне використання і швидкий доступ до них користувачеві. Вона містить кнопку (JButton) В«Завантажити файлВ», а також список (JComboBox) для вибору режиму роботи.
Далі розташовуються панелі (JPanel), що надають інформацію про розв'язуваної задачі, а саме:
В· Панель па...
