Программная реализация симплекс-метода (стр. 1 из 3)
Содержание
Введение
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.7.Конец решения.
3. Проектирование интерфейса
Разработанное приложение имеет простой однооконный интерфейс с набором всех необходимых инструментов для работы с программой.