Программная реализация симплекс-метода - Контрольная работа

Линейное программирование - математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n-мерного векторного пространства , задаваемых системами линейных уравнений и неравенств. Термин «программирование» нужно понимать в смысле «планирования».Задача линейного программирования (ЛП) возникает из необходимости оптимально использовать имеющиеся ресурсы. Это задачи, связанные с целеобразованием и анализом целей и функций; задачи разработки или совершенствования структур (производственных структур предприятий, организованных структур объединений); задачи проектирования (проектирование сложных робототехнических комплексов, гибких производственных систем). В качестве конкретных примеров задач, которые относятся к области линейного программирования, можно назвать задачу об использовании сырья, задачу об использовании мощностей, задачу на составление оптимальной производственной программы. Задача ЛП заключается в отыскании вектора , максимизирующего/минимизирующего линейную целевую функцию Эту же задачу ЛП можно представить в векторно-матричной записи: (4) где - вектор коэффициентов целевой функции, - вектор решения, - вектор свободных членов, - матрица коэффициентов.Симплекс-метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ. Этот метод позволяет переходить от одного допустимого решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритм симплекс-метода позволяет также установить является ли задача ЛП разрешимой. Находим ведущую строку по правилу: Если все элементы ведущего столбца , то задача ЛП не является разрешимой, т.к. целевая функция не ограничена на множестве допустимых значений, переход на пункт 7.Разработанное приложение имеет простой однооконный интерфейс с набором всех необходимых инструментов для работы с программой. Вверху окна стандартно располагается строка меню (JMENU), содержащая подменю (JSUBMENU) Файл, Режим работы, Справка. В подменю Режим работы с помощью Группы радиокнопок (JRADIOBUTTON Group) осуществляется взаимоисключающий выбор одного из двух режимов работы: автоматический, режим обучения. Под строкой меню располагается панель инструментов, дублирующая функции, доступные из строки меню, но предоставляющая более удобное использование и быстрый доступ к ним пользователю. В центральной части окна расположена таблица (JTABLE), отображающая симплекс-таблицу на текущем шаге, и набор кнопок (JBUTTON) для работы с таблицей: В автоматическом режиме: · Кнопка «решить».В рамках поставленной задачи был разработан программный модуль, осуществляющий решение задачи линейного программирования на основе начального допустимого базисного решения. Входными данными является текстовый файл, содержащий начальное допустимое базисное решение (на входные данные накладываются следующие ограничения: максимальное количество свободных переменных - 5, базисных - 8). В режиме обучения (Приложение 1, рис.3) решение выполняется пошагово с привлечением участия пользователя на каждом шаге. Пользователь осуществляет выбор ведущего столбца, затем ведущей строки, после чего симплекс таблица перестраивается и итерация повторяется. Класс SIMPLEXSOLVE содержит следующие методы: static void INITSOLUTION(int VARCOUNT) - создает вектор решения необходимой размерности. static float[][] Solve(float[][] matrix) - осуществляет решение задачи в автоматическом режиме.Вход: Загружаем корректный файл с начальным допустимым базисным решением data1.txt. Выход: В панели «Решение» отображается вектор решения. В поле подсказки отображается информация о том, что задача решена и полученное решение оптимально. Вход: Загружаем некорректный файл с начальным допустимым базисным решением data2.txt. Вход1: Загружаем корректный файл с начальным допустимым базисным решением data5.txt, целевая функция не ограничена на множестве допустимых решений..По итогам данной работы был разработан программный модуль, реализующий решение задач линейного программирования симплекс-методом на основе начального допустимого базисного решения. Симплекс-метод является наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования. Алгоритм метода прост в понимании и легок в реализации, при программировании алгоритма никаких сложностей принципиального характера не возникло. Однако, несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.Рис. Автоматический режим работы программы Режим обучения линейный программирование симплекс метод//решение задачи в автоматическом режиме static float[][] Solve(float[

Содержание

Введение

1. Описание задачи

2. Описание метода решения

3. Проектирование интерфейса

4. Структура программного модуля

5. Тестирование

Заключение

Список использованной литературы и программных средств

Приложение 1. Интерфейс приложения

Приложение 2. Листинг класса SIMPLEXSOLVE

Линейное программирование - математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n-мерного векторного пространства , задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем выпуклого программирования , которое в свою очередь является частным случаем математического программирования. Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом , одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации .

Работа посвящена наиболее распространенному методу решения задачи линейного программирования - симплекс-методу. Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании.

По итогам данной работы был разработан программный модуль, реализующий решение задач линейного программирования симплекс-методом на основе начального допустимого базисного решения.

Симплекс-метод является наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования. Алгоритм метода прост в понимании и легок в реализации, при программировании алгоритма никаких сложностей принципиального характера не возникло. Однако, несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения. Таким образом, данный метод эффективен на небольшом наборе входных данных, при увеличении же их сложность алгоритма будет возрастать скачкообразно.

В рамках поставленной задачи были выполнены все требования, реализованы все функциональные составляющие. Интерфейс разработанного программного продукта интуитивно понятен и легок в использовании. Модульность приложения предоставляет возможности для его дальнейшей доработки расширения и встраивания в вычислительные комплексы.

Список использованной литературы и программных средств

1. Исенбаева Е.Н. МЕТОДИЧЕСКИЕ УКАЗАНИЯ к проведению практических занятий по курсу "Системный анализ" на тему "Симплекс-метод решения задачи линейного программирования"/ Е.Н. Исенбаева. - Ижевск: ИЖГТУ, 1999. - 14с.

2. Электронный ресурс: Симплекс метод: программная реализация симплекс-метода на языке Java - 3. Электронный ресурс: Wikipedia - Линейное программирование - 4. Электронный ресурс: Wikipedia - Задача линейного программирования

5. Среда разработки NETBEANS IDE 6.9.1