Содержание
Введение
1. Описание задачи
2. Описание метода решения
3. Проектирование интерфейса
4. Структура программного модуля
5. Тестирование
Заключение
Список использованной литературы и программных средств
Приложение 1. Интерфейс приложения
Приложение 2. Листинг класса SimplexSolve
Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
Работа посвящена наиболее распространенному методу решения задачи линейного программирования – симплекс-методу. Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании.
Задача линейного программирования (ЛП) возникает из необходимости оптимально использовать имеющиеся ресурсы. Это задачи, связанные с целеобразованием и анализом целей и функций; задачи разработки или совершенствования структур (производственных структур предприятий, организованных структур объединений); задачи проектирования (проектирование сложных робототехнических комплексов, гибких производственных систем).
В качестве конкретных примеров задач, которые относятся к области линейного программирования, можно назвать задачу об использовании сырья, задачу об использовании мощностей, задачу на составление оптимальной производственной программы.
Задача ЛП заключается в отыскании вектора
при следующих линейных ограничениях
Запись задачи ЛП в виде (1)-(3) называется нормальной формой задачи.
Эту же задачу ЛП можно представить в векторно-матричной записи:
где
Область
Решением задачи ЛП, или оптимальным планом, называется вектор, удовлетворяющий системе ограничений задачи и оптимизирующий целевую функцию.
Другая форма представления задачи ЛП – каноническая. Она имеет вид:
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть неотрицательными, а все ограничения должны быть представлены равенствами. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности.
Симплекс-метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.
Этот метод позволяет переходить от одного допустимого решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритм симплекс-метода позволяет также установить является ли задача ЛП разрешимой.
Рассмотрим задачу ЛП в канонической форме. Будем искать решение задачи (6), (7), (8).
0.Положим k = 1. Взяв переменные
1.Заполним начальную допустимую симплекс-таблицу
| … | | | … | | | |
| | … | | 0 | … | 0 | 0 |
| | … | | 1 | … | 0 | |
… | … | … | … | … | … | … | … |
| | … | | 0 | … | 1 | |
где
2.Если для k-той крайней точки все
В остальных случаях переход к пункту 3.
3.Находим ведущий столбец
4.Находим ведущую строку
Если все элементы ведущего столбца
Таким образом, ведущий элемент
5.Выполняем один шаг метода Гаусса: выводим переменную с индексом
Новые значения элементов остальных строк матрицы:
Все элементы в ведущем столбце равны 0, тогда как сам ведущий элемент равен 1.
6.Получаем (k + 1) крайнюю точку
7.Конец решения.
3. Проектирование интерфейса
Разработанное приложение имеет простой однооконный интерфейс с набором всех необходимых инструментов для работы с программой.