Создать компьютерную программу для реализации симплекс метода решения задач линейной оптимизации

Обновлено: 22.01.2025

Тема: Решение задач линейного программирования симплексным методом с помощью программы M ICROSOFT EXCEL .

Разработал: преподаватель Контанистова Е.П.

Рассмотрена на заседании ПЦК профессиональных дисциплин ППССЗ 09.02.01 ,09.02.03 ,08.02.01

Протокол от «28» августа 2017 г. № 1

Председатель ПЦК_____________Никитина С.Ю.

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

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

Процесс подготовки и проведения практического занятия включает несколько этапов:

Подготовка к практическому занятию;

Проверка уровня усвоения теоретического материала и подготовки к практическому занятию;

Решение тренировочных задач, предназначенных для приобретения практических навыков в освоении алгоритмов и методов;

Решение прикладных задач экономического содержания;

Решение задач, ориентированных на использование пакета компьютерной математики;

Выдача домашнего задания.

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

Учебно – методический план занятия

Тема: Решение задач линейного программирования симплексным методом с помощью программы M ICROSOFT EXCEL .

Образовательная: Сформировать практические навыки по решению задач линейного программирования симплекс-методом с помощью программы MICROSOFT EXCEL и провести контроль знаний умений и навыков.

Воспитательная: Формирование сознательного отношения к процессу обучения.

Развивающая: Развивать умение самостоятельно подбирать необходимую для профессиональной деятельности информацию и применять ее с позиции решения профессиональных проблемных задач.

Требования ФГОС к уровню подготовки учащегося:

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

Формируемые компетенции: Общекультурные компетенции:

ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.

ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.

ОКЗ. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.

ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.

ОК 6. Работать в коллективе и в команде, эффективно общаться с коллегами, руководством, потребителями.

ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), за результат выполнения заданий.

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

ОК 10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).

Профессиональные компетенции:

ПК 1.1. Выполнять разработку спецификаций отдельных компонент.

ПК 1.2. Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля.

ПК 5.1. Производить инсталляцию, настройку и обслуживание программного обеспечения компьютерных систем.

ПК 5.3. Выполнять работы по модификации отдельных компонент программного обеспечения.

ПК 5.4. Обеспечивать защиту программного обеспечения компьютерных систем.

Методическое обеспечение занятия : Индивидуальные задания для учащихся по данной теме, контрольные вопросы, тесты.

Домашнее задание : Работа над учебным материалом

М.: ФОРУМ: ИНФРА-М, 2005

Задания для внеаудиторной работы студентов : подготовить отчет по практической работе.

Основные источники (ОИ):

Издательство, год издания

Математические методы в программировании

М.: ИД «ФОРУМ», 2010

Исследование операций в экономике: Учеб. Пособие для вузов.

Кремер Н.Ш., Путко Б.А.

Партыка Т.Л., Попов И.И.

М.: ФОРУМ: ИНФРА-М, 2005

Дополнительные источники (ДИ):

Издательство, год издания

Шикин Е.В.. Шикина Г.Е.

М.: ТК ВЕЛБИ, Проспект, 2008

Теория игр и исследование операций

М.: Гелиос АРВ, 2006

Экономико-математические методы и прикладные модели

Федосеев В.В., Гармаш А.Н., Орлова И.В.

М.: ЮНИТИ-ДАНА, 2005

Исследование операций: задачи, принципы, методология

Математические методы моделирования экономических систем

Бережная Е.В., Бережной В.И.

М.: Финансы и статистика 2001

MATHCAD : математический практикум

Плис А.И., Сливина Н.А.

М.: Финансы и статистика 1999

Вопросы для самопроверки.

Какие задачи ЛП можно решать симплексным методом?

Каков признак оптимальности в симплексном методе?

Как строится опорный план?

Как определяется ведущий столбец и ведущая строка симплексной таблице?

Как осуществляется перерасчет элементов симплексной таблицы?

Для выполнения работы учащиеся должны знать:

общий вид задач линейного программирования, вид основной задачи линейного программирования;

сводить произвольную задачу линейного программирования к основной задаче линейного программирования;

решать задачу линейного программирования симплекс–методом с помощью программы M ICROSOFT EXCEL .

Для изготовления изделий А и В используется три типа сырья.

На производство единицы изделия А расходуется кг сырья первого вида, кг сырья второго вида, кг сырья третьего вида. На производство единицы изделия В расходуется

кг сырья первого вида, кг сырья второго вида, кг сырья третьего вида.

Производство обеспечено сырьём первого вида в количестве кг, сырьем второго вида- кг, сырьем третьего вида- кг.

Прибыль от реализации единицы изделия А составляет рублей, а от реализации единицы изделия В прибыль равна рублей.

Спланировать производство изделия А и В так, чтобы прибыль от реализации изделий была бы максимальной.

a ) Сформулировать математическую постановку задачи с ограничениями- неравенствами.

b ) Сформулировать математическую постановку задачи с ограничениями- равенствами.

Недавно появилась необходимость создать с нуля программу, реализующую алгоритм симплекс-метода. Но в ходе решения я столкнулся с проблемой: в интернете не так уж много ресурсов, на которых можно посмотреть подробный теоретический разбор алгоритма (его обоснование: почему мы делаем те или иные шаги) и советы по практической реализации — непосредственно, алгоритм. Тогда я дал себе обещание — как только завершу задачу, напишу свой пост на эту тему. Об этом, собственно, и поговорим.

Замечание. Пост будет написан достаточно формальным языком, но будет снабжен комментариями, которые должны внести некоторую ясность. Такой формат позволит сохранить научный подход и при этом, возможно, поможет некоторым в изучении данного вопроса.

§1. Постановка задачи линейного программирования

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

Общая задача линейного программирования (далее – ЛП) имеет вид:

§2. Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

1. Неравенства с отрицательными умножаем на (-1).
2. Если неравенство вида (≤), то к левой части добавляем – добавочную переменную, и получаем равенство.
3. Если неравенство вида (≥), то из левой части вычитаем , и получаем равенство.
4. Делаем замену переменных:

• Если , то
• Если — любой, то , где

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

Определение: Точка называется угловой точкой, если представление возможно только при .

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит (т.е. – не внутренняя точка).

Графический способ решения задачи ЛП показывает, что нахождение оптимального решения ассоциируется с угловой точкой. Это является основной концепцией при разработке симплекс-метода.

Определение: Пусть есть система m уравнений и n неизвестных (m < n). Разделим переменные на два множества: (n-m) переменные положим равными нулю, а остальные m переменных определяются решением системы исходных уравнений. Если это решение единственно, то тогда ненулевые m переменных называют базисными; нулевые (n-m) переменных – свободными (небазисными), а соответствующие результирующие значения переменных называют базисным решением.

§4. Симплекс-метод

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

Необходимые условия для применения симплекс-метода:

1. Задача должна иметь каноническую форму.
2. У задачи должен быть явно выделенный базис.

Замечание: Базисный вектор имеет размерность (m*1), где m – количество уравнений в системе ограничений.

Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами:

• В первой строке указывают «наименование» всех переменных.
• В первом столбце указывают номера базисных переменных, а в последней ячейке – букву Z (это строка функционала).
• В «середине таблицы» указывают коэффициенты матрицы ограничений — aij.
• Последний столбец – вектор правых частей соответствующих уравнений системы ограничений.
• Крайняя правая ячейка – значение целевой функции. На первой итерации ее полагают равной 0.

Замечание: Если ограничения в исходной задаче представлены неравенствами вида ≤, то при приведении задачи к канонической форме, введенные дополнительные переменные образуют начальное базисное решение.

Замечание: Коэффициенты в строке функционала берутся со знаком “-”.

Алгоритм симплекс-метода:

1. Выбираем переменную, которую будем вводить в базис. Это делается в соответствии с указанным ранее принципом: мы должны выбрать переменную, возрастание которой приведет к росту функционала. Выбор происходит по следующему правилу:

• Если задача на минимум – выбираем максимальный положительный элемент в последней строке.
• Если задача на максимум – выбираем минимальный отрицательный.

Замечание: Хотя мы и берем минимальное отрицательное число в задаче на максимум, этот коэффициент показывает направление роста функционала, т.к. строка функционала в симплекс-таблице взята со знаком “-”. Аналогичная ситуация с минимизацией.

Определение: Столбец симплекс-таблицы, отвечающий выбранному коэффициенту, называется ведущим столбцом.

2. Выбираем переменную, которую будем вводить в базис. Для этого нужно определить, какая из базисных переменных быстрее всего обратится в нуль при росте новой базисной переменной. Алгебраически это делается так:

• Вектор правых частей почленно делится на ведущий столбец
• Среди полученных значений выбирают минимальное положительное (отрицательные и нулевые ответы не рассматривают)

Замечание: Фактически, мы выражаем старые базисные переменные из каждого уравнения системы ограничений через остальные переменные и смотрим, в каком уравнении возрастание новой базисной переменной быстрее всего даст 0. Попадание в такую ситуацию означает, что мы «наткнулись» на новую вершину. Именно поэтому нулевые и отрицательные элементы не рассматриваются, т.к. получение такого результата означает, что выбор такой новой базисной переменной будет уводить нас из области, вне которой решений не существует.

3. Ищем элемент, стоящий на пересечении ведущих строки и столбца.

Определение: Такой элемент называется ведущим элементом.

4. Вместо исключаемой переменной в первом столбце (с названиями базисных переменных) записываем название переменной, которую мы вводим в базис.

5. Далее начинается процесс вычисления нового базисного решения. Он происходит с помощью метода Жордана-Гаусса.

• Новая Ведущая строка = Старая ведущая строка / Ведущий элемент
• Новая строка = Новая строка – Коэффициент строки в ведущем столбце * Новая Ведущая строка

6. После этого проверяем условие оптимальности. Если полученное решение неоптимально – повторяем весь процесс снова.

§5. Интерпретация результата работы симплекс-метода

1. Оптимальность

Условие оптимальности полученного решения:

• Если задача на максимум – в строке функционала нет отрицательных коэффициентов (т.е. при любом изменении переменных значение итогового функционала расти не будет).
• Если задача на минимум – в строке функционала нет положительных коэффициентов (т.е. при любом изменении переменных значение итогового функционала уменьшаться не будет).

Однако, стоит отметить, что заданный функционал может не и достигать максимума/минимума в заданной области. Алгебраический признак этого можно сформулировать следующим образом:

При выборе ведущей строки (исключаемой переменной) результат почленного деления вектора правых частей на ведущий столбец содержит только нулевые и отрицательные значения.

Фактически, это значит, что какой бы рост мы не задавали новой базисной переменной, мы никогда не найдем новую вершину. А значит, наша функция не ограничена на множестве допустимых решений.

3. Альтернативные решения

При нахождении оптимального решения возможен еще один вариант – есть альтернативные решения (другая угловая точка, дающая то же самое значение функционала).

Алгебраический признак существования альтернативы:

После достижения оптимального решения имеются нулевые коэффициенты при свободных переменных в строке функционала.

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

Эпилог

Данная статья направлена на более глубокое понимание теоретической части. В замечаниях и пояснениях здесь можно получить ответы на вопросы, которые обычно опускают при изучении этого метода и принимают априори. Однако, надо понимать, что многие методы численной оптимизации основаны на симплекс-методе (например, метод Гомори, М-Метод) и без фундаментального понимания вряд ли получится сильно продвинуться в дальнейшем изучении и применении всех алгоритмов этого класса.

Чуть позже напишу статью о практической реализации симплекс-метода, а также несколько статей о Методе искусственных переменных (М-Метод), Методе Гомори и Методе ветвей и границ.

Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах 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.

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

Разработанное приложение имеет простой однооконный интерфейс с набором всех необходимых инструментов для работы с программой.

Вверху окна стандартно располагается строка меню (JMenu), содержащая подменю (JSubMenu) Файл, Режим работы, Справка. В подменю Файл доступны следующие пункты меню (JMenuItem): Открыть файл, Выход. В подменю Режим работы с помощью Группы радиокнопок (JRadioButtonGroup) осуществляется взаимоисключающий выбор одного из двух режимов работы: автоматический, режим обучения. Из подменю Справка доступен вызов окна «О программе» (SimplexAboutBox).

Под строкой меню располагается панель инструментов, дублирующая функции, доступные из строки меню, но предоставляющая более удобное использование и быстрый доступ к ним пользователю. Она содержит кнопку (JButton) «Загрузить файл», а также список (JComboBox) для выбора режима работы.

Далее располагаются панели (JPanel), предоставляющие информацию о решаемой задаче, а именно:

·Панель параметров. Отображает количество свободных и базисных переменных и количество ограничений с помощью JLabel.

·Панель «Целевая функция» отображает вид целевой функции с помощью группы надписей (JLabel) и текстовых полей (JTextField).

·Панель «Решение» отображает вектор решения на текущем шаге выполнения задачи (для автоматического режима – оптимальное решение).

В центральной части окна расположена таблица (JTable), отображающая симплекс-таблицу на текущем шаге, и набор кнопок (JButton) для работы с таблицей:

В автоматическом режиме:

В режиме обучения:

·«перестроить симплексную таблицу». Осуществляет один шаг метода Гаусса для замены базисной переменной.

Внизу окна расположено поле для вывода многострочного текста (JTextArea), в котором отображается вспомогательная информация о текущем состоянии выполнения программы, а также о правилах выбора ведущих столбца и строки.

Рис. 1. Главное окно разработанного приложения.

Скриншоты интерфейса разработанного приложения при разных вариантах работы программы представлены в Приложении 1.

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

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

Разработанный программный модуль предоставляет пользователю возможность выбора одного из двух режимов работы:

В программе предусмотрена обработка следующих исключительных ситуаций:

·загружен некорректный входной файл (Приложение 1, рис.4);

·целевая функция не ограничена на множестве допустимых решений (Приложение 1, рис.5).

Также реализована система подсказок, предоставляющая пользователю более лёгкую работу с программным средством.

В качестве среды разработки была выбрана NetBeansIDE, являющаяся средой разработки приложений на языке Java.

Структура созданного программного модуля представляет собой совокупность следующих классов:

·SimplexApp – главный класс приложения, осуществляющий запуск приложения, создание и отображение главного окна приложения.

·SimplexView – класс главного окна приложения, инициализирует все компоненты интерфейса, осуществляет их настройку, а также обработку событий, вызванных пользователем.

·SimplexAboutBox– класс, инициализирующий окно «О программе».

·SimplexSolve – класс, реализующий выполнение симплекс-метода.

·ReadFile– класс для обработки входного файла.

·TableView – реализует вывод симплекс-таблицы.

·Help – реализует вывод подсказок о ходе выполнения решения и о работе программы.

Класс SimplexSolve содержит следующие методы:

staticvoidinitSolution(intvarCount) - создаёт вектор решения необходимой размерности.

staticfloat[][] Solve(float[][] matrix) - осуществляет решение задачи в автоматическом режиме. Получая на вход начальную симплекс-таблицу, возвращает преобразованную симплекс-таблицу с полученным решением.

staticbooleanuserChooseRow(float[][] matrix, JTabletableName) – проводит проверку ограниченности целевой функции на множестве допустимых решений, выполняет выбор ведущей строки и сравнивает полученный результат с выбором пользователя. Возвращает истину, если выбор был осуществлён верно, иначе ложь. В случае если результаты не совпали, сообщает пользователю об ошибке.

staticvoiduserBuildNewTable(float[][] matrix, JTabletableName)– перестраивает симплексную таблицу и обновляет вектор решения.

staticbooleancheckSolved(floatmatrix[][])– проверяет текущее решение на оптимальность. Возвращает истину, если решение оптимально, иначе ложь.

Класс ReadFile содержит следующие методы:

staticString[] doVarCol(), staticString[] doVarRow() – создают вспомогательные строку и столбец обозначения переменных для отображения симплекс-таблицы.

static int getVarCount() – возвращает количество свободных переменных.

static int getBvarCount() – возвращает количество базисных переменных.

static int getCondCount() – возвращает количество ограничений.

Класс TableViewсодержит следующие методы:

static void clearTable(JTable tableName) – очищаеттаблицу.

static void setNames (JTable tableName) – заполняетшапкутаблицы.

static void fillTable(JTable tableName, float[][] matrix) – заполняетсимплекстаблицу.

static void fillProportion(JTable tableName, float[] proportion, int tempCInd) – заполняетвспомогательныйстолбецотношения(вобучающемрежиме).

Класс Helpсодержит метод

staticStringshowHelp(intevent) – осуществляет вывод подсказки в зависимости от произошедшего события.

Листинг класса SimplexSolve, содержащего алгоритм симплекс-метода, приведёт в Приложении 2.

Выход: В панели «Решение» отображается вектор решения. В таблицу выводится симплекс-таблица на последней итерации выполнения алгоритма. В поле подсказки отображается информация о том, что задача решена и полученное решение оптимально.

(Приложение 1, рис. 2)

(Приложение 1, рис.4)

Выход2: В таблице выводится дополнительный столбец отношения.

(Приложение 1, рис. 5)

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

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

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

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

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

Рис. 2. Автоматический режим работы программы

Рис. 3. Режим обучения

линейный программирование симплекс метод

Рис. 4. Обработка события «Ошибка входных данных»

Рис. 5. Обработка события «Целевая функция не ограничена на множестве допустимых решений».

Программирование на Python использует симплексный метод и библиотеку scipy для сравнения и анализа максимальных и оптимальных решений линейного программирования.

Программирование на Python использует симплексный метод и библиотеку scipy для сравнения и анализа максимальных и оптимальных решений линейного программирования.

1. Что такое симплекс-метод

Симплексный метод Симплексный метод Общий метод решения задач линейного программирования. Симплекс был впервые предложен американским математиком Дж. Б. Данзиком в 1947 году. Его теоретическая основа: допустимая область задачи линейного программирования - это многогранное выпуклое множество в n-мерном векторном пространстве Rn, и его оптимальное значение должно достигаться в вершине выпуклого множества, если оно существует. Допустимое решение, соответствующее вершина называется основным допустимым решением.

2. Симплексный метод

Сначала найдите базовое возможное решение и определите его, чтобы увидеть, является ли оно оптимальным решением; если это не так, переключитесь на другое улучшенное базовое выполнимое решение в соответствии с определенными правилами, а затем определите; если это все еще не так, затем переключитесь снова, нажмите здесь Повторить. Поскольку количество основных возможных решений ограничено, оптимальное решение задачи может быть получено после конечного числа преобразований. Если проблема не имеет оптимального решения, этот метод также можно использовать для оценки. Согласно принципу симплекс-метода в задаче линейного программирования значение переменных решения (управляющих переменных) x1, x2, . xn называется решением, а решение, удовлетворяющее всем ограничениям, называется допустимым решением. . Возможное решение, при котором целевая функция достигает максимума (или минимума), называется оптимальным решением. Таким образом, оптимальное решение может привести к достижению целевой функцией максимума (или минимума) во всей допустимой области, определяемой ограничениями.Цель решения задачи линейного программирования - найти оптимальное решение.

3. Шаги симплексного метода

(1) Выразите систему уравнений ограничений задачи линейного программирования как систему канонических уравнений и найдите основное допустимое решение в качестве начального основного допустимого решения.
(2) Если базовое возможное решение не существует, т. е. условия ограничения противоречивы, проблема не имеет решения.
(3) Если базовое допустимое решение существует, возьмите начальное базовое допустимое решение в качестве отправной точки и в соответствии с условиями оптимальности и выполнимости введите неосновные переменные для замены базовой переменной. найти цель Другое базовое возможное решение с лучшим значением функции
(4) Выполняйте итерации согласно шагу 3, пока соответствующий номер теста не будет соответствовать условию оптимальности (значение целевой функции не может быть улучшено в настоящее время), то есть оптимальное решение проблемы полученный.
(5) Если значение целевой функции задачи окажется неограниченным во время итерации, итерация будет прекращена.

Примечание. Количество итераций, необходимых для решения задачи линейного программирования с помощью симплекс-метода, в основном зависит от количества ограничений. Теперь общие задачи линейного программирования решаются на компьютере с использованием стандартного программного обеспечения симплекс-метода.Задача линейного программирования с 106 переменными решения и 104 условиями ограничений может быть решена на компьютере.

4. Возможная ситуация оптимального решения.

(1) Есть оптимальное решение
(2) Оптимальных решений бесконечно много.
(3) Оптимального решения не существует

Примечание: оптимального решения не существует, и оно встречается только в двух случаях, то есть нет допустимого решения или ограничения не препятствуют неограниченному увеличению значения целевой функции (или бесконечному увеличению в отрицательном направлении).

Решите максимальное и оптимальное решения линейного программирования со следующими ограничениями

Общие шаги по решению проблем:
(1) Линейная стандартизация спецификации: введите резервные переменные: s1, s2, s3.

(2) Извлеките коэффициент и заполните форму.

Ответы в области выше:

Среди них s1, s2 и s3 используются как базовые:

(3) Перейти к другому базовому допустимому решению X1 из исходного базового допустимого решения X0 и определить, является ли X1 оптимальным решением.

Оптимальное решение этой задачи: Z = 27500, X1 = 50, X2 = 250, S1 = 50, s2 = s3 = 0

1. Напишите файлы данных и заполните стандартизованную модель анализа линейной регрессии.

Создайте новый файл txt и заполните стандартизованную модель анализа линейной регрессии.

2. Напишите код Python

Библиотека импорта

Определите модельную функцию, которая перечисляет коэффициенты линейной регрессии

Определите и обновите функцию базовой переменной: начиная с начального полюса, продолжайте находить лучшие соседние полюса, пока не будет найден оптимальный полюс (или крайняя линия)

Определите функцию вывода и печати результата

Импортировать модель линейной регрессии, функцию вызова, найти оптимальное решение и оптимальное значение

результат операции
x2, x3, x4 соответствуют введенным переменным s1, s2, s3

Полный код выглядит следующим образом:

1. Напишите код Python

Описание кода:
c: c относится к массиву коэффициентов функции, для которой требуется максимальное значение.
A_ub: A_ub - матрица коэффициентов неизвестной величины неравенства, которая является левой частью неравенства.
B_ub: B_ub - это правая часть неравенства, которая является правой частью неравенства.

Примечание: если направление неравенства в вопросе не совпадает, вам необходимо добавить знак минуса, чтобы настроить направление, чтобы оно соответствовало; соответственно, коэффициенты матрицы коэффициентов также должны изменить направление и настроить в соответствии с твоя собственная ситуация

2. Результаты бега

Симплексный результат

Использовать результаты библиотеки scipy

Посредством сравнения двух приведенных выше результатов нетрудно обнаружить, что результаты симплексного метода более точны, поскольку конкретные результаты x0 = 50, x1 = 250; более точные чем scipy библиотека. Исходя из результата, он должен быть не десятичным, а общим результатом. Ручной вывод такой же, разница небольшая, основная ошибка составляет около 0,00000001

Читайте также:

  
• Преобразовать область в поверхность в автокаде
  
• Автокад как выбрать линию под линией
  
• Как удалить временные файлы google chrome
  
• 1с переименовать кнопку провести и закрыть
  
• Не работает power query в excel 2016