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

ВВЕДЕНИЕ

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

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

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

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

1.Рассмотреть теоретические основы математического программирования;

2.Изучить и определить общей задачи оптимизации;

3.Овладеть навыками пакетами Mathcad и Microsoft Excel

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

5.Найти наибольшее и наименьшее значение функции двух переменных в замкнутой области.

6.Закрепить полученные знания и навыки на практике и сделать выводы.

Объектом исследования данной курсовой работы является математическое программирование, предмет исследования − задачи линейного программирования.

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

1. Теоретические основы математического программирования

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

Оптимизация − это процесс выбора лучшего варианта из всех вероятных. Методы оптимизации, с точки зрения инженерных расчетов, разрешают избрать лучший вариант системы, лучшее расположение ресурсов и т.д. Для того, чтоб постановить задачу оптимизации, традиционно нужно отыскать оптимальные значения неких параметров, характеризующих эту задачу. В инженерных задачах их принято именовать проектными параметрами, a ʙ экономических − параметрами плана. Значения линейных объемов объекта, массы, температуры и тому подобное имеют все шансы существовать в качестве проектных характеристик, количество n проектных параметров x1, x2… xn охарактеризовывает размерность (и степень трудности) задачи оптимизации. [1]

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

Целевая функция имеет вид:

U=F (x1, x2… xn) [1]

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

В случае, когда параметр равен 1, график − некоторая кривая на плоскости и она является функцией одной переменной.

От вида задания допустимого множества R(X) очень многое зависит. Во многих случаях R(X) выделяется из Rn с помощью системы равенств и неравенств:

[1]

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

Связаны с математическими характеристиками их функций более тривиальные отличия между задачами. К примеру, целевая функция станет гладкой в одном случае, а в ином − разрывной; время от времени свойства функции элементарны и задачи понятны, а время от времени расчет значений просит решения каких-то довольно трудных подзадач, когда очевидные выражения для функций отсутствуют. Линейные функции F(X) и g_j(X)- это наиболее простой и часто встречающийся случай. Тогда говорят о задаче линейного программирования. [1]

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

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

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

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

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

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

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

1.2 Основные теоремы и задачи линейного программирования

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

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

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

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

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

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

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

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

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

2.Рационального использования сырья и материалов;

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

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

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

6.Управления производственными запасами − сводится к оптимизации издержек по хранению и расходов по размещению и исполнению заказов, и многие другие, принадлежащие сфере оптимального планирования. [3]

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

дано неравенством.

В краткой записи ЗЛП имеет вид:

1.Обозначить переменные;

2.Сформировать целевую функцию;

3.Написать систему ограничений в соответствии с целью задачи;

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

Однако следует сказать, что терминология линейного программирования неоднозначна. В значительной степени это связано с экономическими приложениями, термины которых часто сохраняют и для задач линейного программирования. Матрицу A = [а_1, а₂, …аn] называют матрицей условий задачи. Векторами условий задачи называют ее столбцы a_i(i = ). Вектор b называют вектором ограничений задачи.

Допустимую точку [х∈R₁] называют также плaном. Иногда угловую точку множества называют опорным планом, а решение задачи линейного программирования (оптимальную точку) называют оптимальным планом.

Рассмотрим геометрическую интерпретацию. В пространстве Еп множество R₁ можно рассматривать как пересечение полупространств (при п=2 полуплоскостей):

(Ax)_I ≥b_i, i₌,x_i ≥ 0,j=. [2]

Рассмотрим {с; х} = λ − семейство параллельных гиперплоскостей (при п=2 − параллельных прямых). Вектор с направлен в сторону убывания целевой функции. На рисунке 1 изображен случай, когда множество ограничено, т.е. многоугольник. [4]

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

Рассмотрим некоторую точку х_о∈R₁. Ей соответствует значение целевой функции:

λ_о = {с; х₀}, [4]

Теперь будем перемещать прямую {с; х} = λ в направлении − с, то есть в направлении убывания величины λ, до тех пор, пока не придем в такую точку х^≠∈R_1, для которой значение λ минимально. Геометрический смысл задачи здесь очевиден.

Легко изобразить на чертеже, когда:

1.Неограниченно, но решение существует;

2.Когда решение существует, но не единственно;

3.Когда R₁ неограниченно и {с, х} неограничен на R₁.

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

Будем обозначать функцию Лагранжа для задачи так:

L₁(x, y) = (c, х) + (у.b-Ах), [5]

Рассмотрим теорему. Для того чтобы точка x^≠∈R₁ была оптимальной для основной задачи линейного программирования, необходимо и достаточно существования у^* ≥ 0 такого, чтобы пара х^* у^*была седловой точкой функции ЛагранжаL₁(x, y) в области х ≥ 0, у ≥ 0, то есть:

L₁(x^*, y) ≤ L₁ (х^*, у^*)≤ L₁ (х_, у^*), [5]

Необходимым и достаточным условием оптимальности х^* для задачи является следующее представление вектора с:

, у^*≥0, ≥0

Где:

I (х^*) = (i: (Aх^*)_i =b_i),

J (х^*) = (j:хi^*= 0).

Для х^* выполняются следующие равенства:

, i=

, j=

Теорема. Для любых допустимыхх∈R₁ иy∈Q₁ выполняется неравенство:

(с, х) ≥ (b, y), [5]

Доказательство: из неравенств, определяющих R₁и Q₁следует

(с, х) ≥ (А^ту, х) = (уAх) ≥ (уb) = (bу), [5]

Теорема. Если х∈R₁и y∈Q₁, а(с_, х^*) = (b, у^*), то х^* и у^*оптимальны.

Доказательство. Для любого х ∈R₁ в силу условия, теоремы будет:

(c, x) ≥ (b, y^*) = (c, x^*), [5]

То есть, х^* оптимален. Аналогично доказывается оптимальность у^*.

1.3 Классические методы нахождения экстремума

Определение максимума. Если смысл функции f(х) в точке х0 более, нежели ее значения во всех точках некого промежутка, содержащего точку х0, то функция f(х) в точке х0 имеет локальный максимум (maximum). То имеется, при х=х0 функция f(х) имеет максимум, если f(х0+Δх) всех Δх (положительных и отрицательных), довольно небольших по абсолютной величине.

По-иному, это определение определяют следующим образом: функция f(x) владеет максимум в точке х0, если разрешено отыскать эту окрестность δ точки х0, будто для всех точек данной окрестности, отличных от х0 выполняется неравенство f(х)

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