Графическое решение злп программа

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

1. Теоретические сведения

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.

Рассмотрим задачу ЛП в стандартной форме записи:

Положим n=2 , т.е. рассмотрим эту задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a i1 x 1 + a i2 x 2 = b i , i=1,2,… m . Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x1=0, x2 =0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Графический метод решения задач линейного программирования | Высшая математика TutorOnline

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

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости. Определим, какую часть плоскости описывает неравенство 2х 1 +3х 2  12. Во-первых, построим прямую 2х 1 +3х 2 =12 . Эта прямая проходит через точки (6, 0) и (0, 4).

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

Удобной для использования при подстановке в неравенство является начало координат. Подставим х 1 =х 2 =0 в неравенство 2х 1 +3х 2  12 . Получим 2  0+3  0  12. Данное утверждение является верным, следовательно, неравенству 2х 1 +3х 2  12 соответствует нижняя полуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на. 1.

Рис. 1. Неравенству 2х 1 +3х 2  12 соответствует нижняя полуплоскость.

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

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (x j  0, j=1,…, n). Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

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

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

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

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

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

Графический метод решения ЗЛП состоит из следующих этапов:

1. Строится многоугольная область допустимых решений ЗЛП – ОДР,
2. Строится вектор-градиент ЦФ в какой-нибудь точке Х 0 принадлежащей ОДР –

Описание интерфейса разработанного программного продукта

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

3. Листинг

Класс «Line»

public class Line <
public float a, b, c;
public Line() < >
public Line (float a, float b, float c) < this.a = a; this.b = b; this.c = c; >
Line (Point p1, Point p2) < this (p1.y – p2.y, p2.x – p1.x, p1.x*p2.y – p2.x*p1.y); >
Line (float A, float B, Point point) < this (new Point (point.x + B, point.y – A), point); >
public boolean isParalellWithLine (Line line) < float k = a * line.b – line.a * b; return MathUtil.isEqualWithEplsilon (k, 0); >
public Point getIntersection (Line line) < if (isParalellWithLine(line)) return null;
float znam = 1 / (a * line.b – line.a * b);
float x = (b * line.c – line.b * c) * znam; float y = (c * line.a – line.c * a) * znam;
return new Point (x, y); >
public double getDistanceToPoint (Point p) < return (a * p.x + b * p.y + c) / Math.sqrt (a*a + b*b); >
public float getA() < return – a; >
public void setA (float a) < this.a = – a; >
public float getB() < return – b; >
public void setB (float b) < this.b = – b; >
public float getC() < return c; >
public void setC (float c) < this.c = c; >
public String getView() < return (a >>

Класс «Polygon»

Заключение

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

Источник: doc4web.ru

Графическое решение ЗЛП для Windows

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

Можно отключать/включать отображение на графике некоторые элементы решения, например координатную сетку или закраску ОДР и т.д. Также можно масштабировать график, что делает изучение решения задачи еще более наглядным и удобным. После решения задачи, можно посмотреть и изучить соответствующую теорию, встроеную в программу.

• Исправлены ошибки в решении задач.
• Оптимизирован код.

ТОП-сегодня раздела «Математика»

MathType — отличное приложение для работы с формулами, математическими выражениями и.

Satellite Antenna Alignment — Программа предназначена для расчета углов, необходимых при установке.

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

Advanced Grapher — Мощная и простая в использовании программа для построения графиков и их анализа.

SMath Studio — бесплатная программа для вычисления математических выражений и построения.

Unit Converter — Конвертер физических величин. Cодержит 1194 единицы измерений в 28 категориях.

Отзывы о программе Графическое решение ЗЛП

Сандугаш про Графическое решение ЗЛП 1.5 [12-05-2023]

Не могу скачать полную версию купить не получается я из Казахстана можно это как то решить
| | Ответить

Источник: www.softportal.com

IX Международная студенческая научная конференция Студенческий научный форум — 2017

КУРСОВАЯ РАБОТА «ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ЕГО РЕАЛИЗАЦИЯ В СРЕДЕ ЭТ MS EXCEL И МАТЕМАТИЧЕСКОГО ПАКЕТА MATHCAD».

Юсупова М.И. 1
1 Донской Государственный Технический Университет
Работа в формате PDF

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

ВВЕДЕНИЕ

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

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

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

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

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

В задачах линейного программирования критерий продуктивности и функции в системе ограничений линейны.

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

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

Целью данной работы является:

1. Углубление знаний по конкретной проблеме изучаемой дисциплины;

2. Получение навыков работы с научной и научно-популярной литературой;

3. Изучить теоретический материал по теме «Графический метод решения задач линейного программирования»;

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

5. Овладеть навыками графического решения ЗЛП в среде ЭТ MS Excel и математического пакета Mathcad.

ГЛАВА 1. ОБЩАЯ ЗАДАЧА ОПТИМИЗАЦИИ

1.1 Классификация задач оптимизации

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

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

а также может выражаться в виде:

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

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

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

К примеру, если известные функции и линейны, то эта задача линейного программирования и для ее решения можно использовать методы линейного программирования (варианты симплекс-метода).

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

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

При поиске решения той или иной задачи есть вероятность столкнуться с

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

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

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

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

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

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

1.2. Постановка общей задачи оптимизации

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

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

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

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

С правильной постановкой задача может иметь вид:

а) необходимо получить при данной себестоимости максимальную производительность.

б) нужно найти при известной производительности минимальную себестоимость.

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

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

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

4. Необходимость учитывать ограничения.

1.3 Реализация оптимизационных задач в ЭТ MSExcel и Mathcad

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

которое позволяет производить, анализировать сложные инженерные расчеты.

Рассмотрим решение задачи в пакете Mathcad.

Пример: Найти экстремум функции одной переменной.

1. Определим функцию, чей экстремум будем искать:

2. С помощью математической палитры, найдем первую производную этой функции.

3. С помощью функции simplify упростим выражение для производной:

4. Далее найдем критические значения, при которых производная равна нулю. Для этого воспользуемся функциями Given и Find:

5. Учитывая, что первая производная не существует при , определим две критические точки.

6. Далее исследуем характер полученных критических точек. Если при переходе через критическую точку производная меняет знак с минуса на плюс, следовательно, это точка минимума, а если наоборот, производная меняет знак с плюса на минус, то это точка максимума.

7. Затем найдем значения функции в экстремальных точках

8. Построим график функции и ее производной, как показано на рисунке 1.

Рисунок 1  Нахождение экстремума функции

Рисунок 2  Нахождение экстремума функции

ГЛАВА 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

2.1 Общая постановка задачи линейного программирования

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

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

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

линейных равенств или же неравенств [1].

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

а) рационального расхода материалов и сырья;

б) производственной программы какой-либо компании;

в) наилучшего размещения и концентрации производства;

г) создание наиболее прибыльного плана перевозок, работы транспорта;

д) управление производственными запасами;

е) и множество других зада, которые принадлежат к этой сфере.

Если судить по оценкам американских экспертов, то около 75% от всего числа используемых методов оптимизации приходится на линейное

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

Известный советский математик Л. В. Канторович сформулировал первые постановки задач линейного программирования, за что и был награжден Нобелевской премией по экономике [3].

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

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

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

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

Правила составления математической модели [4].

1. Выбор переменной задачи.

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

2. Составление системы ограничений задачи.

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

В общем виде система выражается следующим образом:

3. Задается целевая функция.

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

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

и условию неотрицательности которая обеспечивает экстремум целевой функции

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

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

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

2.3 Каноническая форма задачи линейного программирования

В каноническую форму можно привести любую задачу линейного программирования [7].

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

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

Задачу линейного программирования вида

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

Например, если система ограничений задается в виде

то при введении дополнительных переменных можно привести ее к виду

Рассмотрим задачу с ограничениями . Тогда систему ограничений можно представить следующим образом [6]:

Далее вводятся следующие обозначения:

Таким образом, задача линейного программирования примет вид:

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

Пусть Dдопустимая область решений, а  допустимые множества

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

2.4 Основные теоремы линейного программирования

1) Линейная форма в угловой точке многогранника решений достигает минимума.

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

Доказательство теоремы основано на лемме. Лемма: Если D ограниченное, замкнутое, выпуклое множество, которое имеет конечное число угловых (крайних) точек, то любую точку можно представить с помощью выпуклой комбинации крайних точек D.

Теорема 2. Если система векторов условий линейно независима и принимает такой вид, что

где все то точка становится угловой точкой многогранника решений.

Теорема 3. Если вектор является крайней точкой многогранника решений, то векторы условий, которые соответствуют положительным компонентам вектора , являются линейно не зависимыми.

1) Угловая точка многогранника решений содержит не более mположительных компонент вектора

2) Каждой крайней точке многогранника решений соответствует линейно m независимых векторов из данной системы:

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

ЭТ MSExcel и математического пакета Mathcad

Рассмотрим решение задач линейного программирования с помощью доступного программного обеспечения: ЭТ MS Excel и пакета Mathcad, на конкретном примере [1].

Таблица 1  Исходные данные задачи

Характеристики компонент для производства бензина

Компоненты для производства бензина

Источник: scienceforum.ru