Контрольная работа: Программная реализация симплекс-метода
Контрольная работа: Программная реализация симплекс-метода
Содержание
Введение
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 |
|