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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	(1.1)

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

при

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

.

(1.2)

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

(1.3)

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

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

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

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

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

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

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

Если ограничения в задачи отсутствуют и является нелинейной функцией, то для решения задачи (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. Составление системы ограничений задачи.

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

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

(2.1)

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

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

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

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

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

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

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

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

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

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

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

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

(2.2)

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

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

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

где

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

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

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

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

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

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

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

Теорема 1.

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

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

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

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

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

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

Следствия:

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

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

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

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

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

Постановка задачи. Стандартом предусмотрено, что октановое число автомобильного бензина A-76 должно быть не ниже 76, а содержание серы в нем  0,0061%. Для изготовления такого бензина на заводах используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице 1.

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

Характеристики компонент для производства бензина	Компоненты для производства бензина
	№1	№2	№3	№4
Октановое число	66	75	80	95
Содержание серы, %	0,008	0,006	0,005	0,004
Ресурсы, тонн	800	900	800	500
Себестоимость, тыс. руб./тонн	10,3	12	15,2	20

Необходимо определить, сколько тонн каждого компонента следует использовать для получения 500 тонн автомобильного бензина A-76,его себестоимость была минимальной.

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

Математическая модель задачи о смесях.

Для построения математической задачи:

1. Нужно определить количество неизвестных.

Пусть  количество компонентов в смеси (.

2. Необходимо сформулировать целевую функцию.

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

3. Требуется установить ограничения решаемой задачи.

3.1. Ограничение по количеству бензина:

3.2. Ограничение по октановому числу:

3.3. Ограничение по содержание серы в бензине:

3.4. Условие неотрицательности полученных переменных:

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

Далее рассмотрим решение задачи в среде ЭТ MS Excel. Данную задачу будем решать с помощью надстройки «Поиск решения». Для этого необходимо:

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

Рисунок 3  Таблица исходных данных

2.Далее нужно создать вторую таблицу «Количество компонентов в смеси» и заполнить диапазон ячеек сначала нулевыми начальными значениями.

Рисунок 4  Количество компонентов в смеси

3. В ячейку нужно ввести формулу селевой функции:

После ввода формулу нажмите клавишу «Enter», и тогда в ячейке получится ноль, так как переменные математической модели равны (.

Рисунок 5  Целевая функция задачи

4. Затем нужно набрать таблицу ограничений и остатков ресурсов.

Рисунок 6  Ограничения и остатки ресурса в задаче

5. Открыть вкладку «Данные  Поиск решения». В появившемся окне нужно

выполнить необходимые установки, которые показаны на рисунке 7.

Рисунок 7  Решение с помощью надстройки «Поиск решения»

7. Нажать по кнопке «Выполнить», после этого появится диалоговое окно, если решение будет выполнено.

Рисунок 8  Поиск решения

Щелчок по кнопке «OK» сохраняет найденное оптимальное решение, которое имеет следующий вид на рисунке 9.

Рисунок 9  Оптимальное решение поставленной задачи

Таким образом, можно сделать вывод, что для получения 500 тонн автомобильного бензина, A-76 было смешать компоненты №1, №2, №3 и №4 в количествах 475 и 25 тонн соответственно, а компоненты №1 и №3 не используются. Октановое число полученной смеси составило 76, а содержание серы  0,0059 %. А Остатки ресурсов составили 800, 425, 800 и 475. Себестоимость полученного автомобильного бензина равна 12,4 тыс. ден. ед.

Решение задачи с помощью математического программы MathСad.

Решение, рассматриваемой задачи в этой программе осуществляется аналогично. Для решения потребуется:

1. Задать исходные данные.

2. Присвоить переменным начальные (нулевые) значения.

3.Определить целевую функцию.

4. Использовать математический блок и после этого ввести систему ограничений данной задачи.

5. Отыскать оптимальное решение с помощью функции .

6. Далее вычислить минимальную себестоимость полученной смеси.

7.Найти остаток ресурсов автомобильного бензина после выпуска бензина.

Рисунок 10  Решение задачи в среде MathCad

Рисунок 11  Решение задачи в среде MathCad

ГЛАВА 3. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

3.1 Теоретическое обоснование графического метода решения ЗЛП

Наиболее простым и наглядным методом решения задачи линейного программирования является графическим метод. Это метод применяется для решения задач линейного программирования с двумя переменными. Также графический метод основан на геометрическом представлении допустимых решений и целевой функции задачи [5].

Каждое из неравенств задачи линейного программирования определяет некоторую полуплоскость на координатной плоскости , а система неравенств в целом  пересечение соответствующих плоскостей. Областью допустимых решений называется множество точек пересечения данных полуплоскостей. Область допустимых решений всегда принимает вид выпуклой фигуры, то есть фигуру, которая обладает следующим свойством: если две точки, например, A и B принадлежат такой фигуре, то и весь отрезок AB принадлежит ей. Область допустимых решений графически можно представить выпуклым многоугольником, неограниченной выпуклой многоугольной областью, лучом, отрезком или одной точкой. Если система ограничений задачи линейного программирования несовместна, то область допустимых решений является пустым множеством.

Рассмотрим задачу линейного программирования:

где

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

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

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

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

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

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

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

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

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

Прямая перпендикулярна вектору-градиенту и является линией уровня целевой функции. Линейная функция цели принимает одно и то же значение в любой точке линии уровня.

Данную целевую функцию приравняем постоянной величине «a». При изменении значений «a», можно получить семейство параллельных прямых, каждая из которых является линией уровня.

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

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

Рисунок 12  Графическая интерпретация графического метода

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

Приведем методику решения ЗЛП графическим методом [10]:

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

2. Отыскать и заштриховать полуплоскости, разрешенные каждым из ограничений  неравенств задачи. Чтобы это сделать, нужно подставить в определенное неравенство координаты какой-нибудь точки, а затем проверить правдивость полученного неравенства.

Если неравенство верное, то нужно заштриховать полуплоскость, которая содержит данную точку.

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

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

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

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

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

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

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

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

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

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

Постановка задачи:

Леня Голубков управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (A и B), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.

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

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

На изготовление каждой единицы продукта A отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта B составляют 10, 4 и 6. Леня прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 4 единиц продукта B необходимо изготавливать в каждый конкретный месяц.

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

Составим математическую модель:

1. Пусть – количество продукта A,

– количество продукта B.

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

прибыли

3. Ограничения.

3.1. Ограничения по часам.

Необходимое количество часов машинной обработки на изготовление продуктов A и B:

при этом по условию часов по количеству не должно быть больше 330,следовательно, получается неравенство:

3.2. Ограничение по единицам сырья:

Нужное количество единиц сырья, для изготовления продуктов A и B:

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

.3. Ограничение по единицам труда:

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

при условии, что это число не больше 240, следовательно, получается неравенство, которое имеет вид:

3.4. Ограничение по количеству продукта B.

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

3.5. Условие целочисленности:

3.6. Условие неотрицательности:

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

при ограничениях:

Рисунок 13  Графическое решение ЗЛП

Решение рассмотренной задачи с помощью ЭТ MS Excel.

Для решения данной задачи в среде Excel:

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

Рисунок 14  Таблица данных задачи, с учетом ограничений

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

3.Составим матрицу из координат полученных точек.

Рисунок 15  Составление матриц и вектор-столбцов полученных точек

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

Рисунок 16  Нахождение обратной матрицы с помощью специальной формулы

5. Найдем значения неизвестных переменных с помощью встроенной функции «МУМНОЖ».

Рисунок 17  Поиск неизвестных переменных, с помощью формулы «МУМНОЖ»

6. Найдем значения целевых функций по формуле, так как имеются две предельные точки:

Рисунок 18  Значение целевых функций

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

Рисунок 19  Графический метод решения ЗЛП

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

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

1.Заполним ячейки исходными данными в виде таблицы.

Рисунок 20  Исходные данные

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

Формула целевой функции будет иметь вид:

Рисунок 21  Целевая функция

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

Рисунок 22  Таблица ограничений

4. Открываем вкладку «Данные  Поиск решения». В появившемся окне выполняем необходимые установки, то есть определяем целевую функцию и заносим ограничения

Рисунок 23  Нахождение решения с помощь надстройки «Поиск решения»

5. Щелкаем по кнопке «Выполнить», после этого появится диалоговое окно, если решение будет выполнено.

Рисунок 24  «Поиск решения»

Нажимаем по кнопке OK и получаем оптимальное решение, которое имеет вид:

Рисунок 25  Оптимальное решение ЗЛП

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

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

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

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

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

Также повторяются действия в графическом методе, которые выполнялись в Excel.

1.Определяем функции из системы ограничений. Затем с помощью этих

функций строим график.

2. Определяем координаты точки с помощью математических блоков , ил обратной матрицы.

3. Затем находим значение целевой функции, по заданным точкам.

Рисунок 26  Решение ЗЛП аналитическим методом в среде MathCad

Рисунок 27  Решение ЗЛП графическим методом в среде MathCad

Рисунок 28  Решение ЗЛП графическим методом в среде MathCad

ЗАКЛЮЧЕНИЕ

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

В настоящее время развитие нашего общества характеризуется с возрастанием:

а) технического уровня,

б) осложнением организации производственной структуры,

в) управления войсками,

г) углублением социального разделения труда,

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

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

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

Таким образом, в ходе работы над курсовым проектом посвященный теме «Графический метод решения задач линейного программирования и его реализация в среде ЭТ MS Excel и математического пакета Mathcad» была проведена следующая работа:

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

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

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

4. Улучшены навыки работы в среде ЭТ MS Excel и математического пакета Mathcad.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Аверьянова С.Ю., Растеряев Н.В. Содержательные задачи линейного программирования и их решение с помощью ЭТ MS EXCEL и пакета MATHCAD: учебное пособие/ Южный федеральный университет. – Ростов-на-Дону: Издательство ЮФУ, 2014. – 132 с.

2. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М.: Наука, 1965. – 424 с.

3. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования

транспортного типа. - М.: Наука, 1969. – 382 с.

4. Васильев О.В. Методы оптимизации в задачах и упражнениях. М.:

Физматлит, 1999. 207 с.

5. Карманов В.Г. Математическое программирование: Учеб. Пособие. М.:

Физматлит, 2001. 263 с.

6. Растеряев, Н.В., Герасименко Ю.Я. Решение оптимизационных задач в среде MATHCAD и EXCEL: Учеб. пособие – Новочеркасск: Южно-российский гос. тех. ун-т (НПИ), 2004.- 100 с.

7. Пантелеев, А.В. Методы оптимизации в примерах и задачах: Учеб. пособие/ А.В. Пантелеев, Т.А. Летова. – 2-е изд., исправл. – М.: Высш. шк., 2005. – 544 с.

8. [Электронный ресурс] – Режим доступа: – 2011. – Режим доступа: http://www.optimiz.ru/catalog/poisk, свободный.

9. Шадрина, Н.И. Решение задач оптимизации в Microsoft Excel 2010 : учеб. пособие / Н.И. Шадрина, Н.Д. Берман. – Хабаровск : Издательство Тихоокеан. гос. университета, 2016. – 101 с.

10. Габасов Р., Кириллова Ф. Качественная теория оптимальных процессов. М.: Наука, 1971. - 508 с.

Код для цитирования: Скопировать