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

XIV Международная студенческая научная конференция Студенческий научный форум - 2022

Разработка приложения для решения задач линейного программирования графическим методом

 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

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

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

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

Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя.

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

Алгоритм графического метода решении задач линейного программирования.

1. Построить область допустимых решений.

2. Если область допустимых решений является пустым множеством, то задача не имеет решения ввиду несовместности системы ограничений.

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

4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум — в противоположном направлении.

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

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

Для чего необходимо приложение для решения графического методом?

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

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

Элементы расписания.

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

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

Графическое изображение - это символический знак, с помощью которого изображаются статистические данные: линии, точки, плоские геометрические фигуры. Трехмерные фигуры также выступают в качестве графического изображения. Иногда на графиках используются негеометрические фигуры в виде силуэтов или рисунков объектов.

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

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

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

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

Шкала представляет собой линию, отдельные точки которой считываются (в соответствии с принятой шкалой) как определенные числа. В масштабе шкалы присутствуют: линейка-носитель информации, являющийся опорой шкалы, точки, отмеченные на ней тире (расположенные в определенном порядке), числовые обозначения чисел, соответствующие отдельным точкам. Масштаб графика может быть прямым и изогнутым (например, круг, содержащий 360°).

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

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

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

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

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

Название графика кратко и ясно объясняет основное содержание отображаемых данных. В дополнение к заголовку график содержит текст, чтобы сделать график читабельным. Цифровое обозначение шкалы дополнено указанием единиц измерения.

Каждый из перечисленных элементов является очень важной частью всего графического процесса.

Графические методы в управлении производством, совокупность способов условного (графического) изображения какого-либо организационного или управленческого явления на производстве. Впервые применены американскими инженерами Ф.У. Тейлором и Г.Л. Ганттом в начале 20в. в качестве одного из методов организации руководства производством. В СССР Графический метод в управлении производством начали применять в 20-х гг.

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

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

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

2) Графики изменения управляемого процесса во времени и пространстве. Эта группа включает гармонограммы, учётно-контрольные и плановые графики, планы объектов на местности, планировки оборудования и рабочих мест, циклограммы. Основное назначение графиков этой группы - оперативно-календарное планирование, учёт и организация движения производства.

3) Графики функциональных зависимостей между отдельными параметрами (графики сравнения структур и параметров). Такого рода графики используются, в основном, для разработки нормативов, в статистическом учёте и анализе хода производства в планируемом периоде (квартал, полугодие, год).

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

5) Смешанные графики - балансовые и сетевые графики используют для анализа хода производства одновременно по нескольким параметрам, для контроля "узких" мест и оптимизации планирования.

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

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

Описание программы:

Программа позволяет решать задачи линейного программирования путем использования компьютерных систем. В качестве этой системы служит ПК с ОС Windows.

Программа создана, используя встроенные средства Windows Forms IDE Microsoft Visual Studio на языке C#.

Рис1. Пример работы программы с только что введенными данными.

Интерфейс позволяет пользователю вводить данные стандартными средствами (клавиатура и мышь). В качестве ответа пользователь получает изображение графика с ОДР и координаты точки оптимального решения ЗЛП и значение функции в этой точке.

Ход работы приложения:

При запуске программы открывается интерфейс Windows формы, имеющим поля для ввода данных.

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

Рис 2. Примерное решение задачи

Заключение.

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

Список литературы:

[Электронный ресурс]: https://portal.tpu.ru/SHARED/k/KOCHEG/study/Tab1/Lection_MO_201 8.pdf#:~:text=Методы%20оптимизации%20

[Электронный ресурс]: https://ru.wikipedia.org/wiki/Оптимизация_(математика)

[Электронный ресурс]: https://www.statmethods.ru/statistics-metody/graficheskij-metod/

[Электронный ресурс]: https://lfirmal.com/graficheskiy-metod-resheniya-zadach-lineynogo-programmirovaniya/

[Электронный ресурс]: https://function-x.ru/graficheskij_metod.html

[Электронный ресурс]: https://natalibrilenova.ru/graficheskie-metodyi-issledovaniya/

[Электронный ресурс]: https://studbooks.net/1436737/menedzhment/graficheskiy_metod

Просмотров работы: 59