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