Методы оптимизации в технико-экономических задачах

«Методы оптимизации в технико-экономических задачах»

по дисциплине:

«Математическая экономика»

Задание на курсовую работу по математической экономике (общая часть)

Задание (вариант 18)

1. Неклассические методы оптимизации

1.1 Теоретическая часть

1.2 Задание

1.3 Построение математической модели задачи

1.4 Решение задачи

1.5 Тестирование задачи на ЭВМ

2. Задача линейного планирования производства.

2.1 Теоретическая часть

2.2 Задание.

2.3 Построение математической модели задачи.

2.4 Решение задачи.

3. Задача оптимального распределения перевозок.

3.1 Теоретическая часть.

3.2 Задание.

3.3 Построение математической модели задачи.

3.4 Решение транспортной задачи.

Заключение

.

Приложение1. Блок-схема к задаче безусловной минимизации функции нескольких переменных

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

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

Задание на курсовую работу по математической экономике (общая часть)

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

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

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

Руководитель работы Королев В.Д.

Доцент каф. ВПМ

Задание (вариант 18)

Задача 1

Зависимость расходов предприятия, прогнозируемых на будущий квартал от факторов x1, x2 задаётся в некоторых денежных единицах функцией

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

Фиксировать x3=0,31

Задача 2

Фирме требуется уголь с содержанием примеси фосфора не больше 0,05% и с примесью пепла не более 4,00%. Доступны 3 сорта угля A, B, C по следующим ценам (за тонну):

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

Задача 3

Имеется четыре завода А1, А2, А3, А4, из которых нужно вывести некоторое количество грузов. И пять пунктов назначения В1, В2, В3, В4, В5, в которые должны быть привезены товары с заводов. Количество товаров в каждом пункте отправления, потребности каждого пункта назначения и тарифы на доставку приведены в таблице.

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

ВВЕДЕНИЕ

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

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

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

методы оптимизации;

макроэкономические модели.

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

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

1. Неклассические методы оптимизации

1.1 Теоретическая часть

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

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

Переходя на математический язык, заключаем, что направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Из курса математики известно, что направление наибольшего возрастания функции двух переменных u=f (x, y) характеризуется ее градиентом

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

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

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

Это позволяет написать общую схему методов спуска.

Решается задача минимизации функции f (x) на всём пространстве Еn.

Методы спуска состоят в следующей процедуре построения последовательности {х (к)}. В качестве начального приближения выбирается любая точка х (0) с Еn. Последовательные приближения х (1), х (2),. строятся по следующей схеме:

в точке х (к) выбирают направление спуска — Sk;

находят (к+1)-е приближение по формуле х (k+1) = хk -?к*Sk.

Направление Sk выбирают таким образом, чтобы обеспечить неравенство f (x (k+1))

Число ?к определяет расстояние от точки х (к) до точки х (к+1). Это число называется длиной шага или просто шагом.

Основная задача при выборе величины? к — это обеспечить выполнение неравенства f (x (k+1))

Выбирают ак=ак-1. Если при этом f (x (k+l))

Если f (x (k+1))>f (x (k)), то выбирают? k=0.5* ?k. Если f (x (k) — 0.5* ?k *S (k))f (x (k)), то выбирают? к =0.25 ?к-1 и т. д.

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

Рассмотрим метод Ньютона.

Сначала необходимо найти стационарную точку как:

(1.1)

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

где ,

— остаточный член.

Затем приравниваем левую часть уравнения к 0 и отбрасываем. В результате получим:

.

Новые приближения и :

(1.2)

Выразим остальные члены:

.

Тогда получим следующую систему уравнений:

где и — неизвестные.

Матрица этой системы является матрицей Гессе:

(1.3)

где .

Из (1.2) находим точку минимума функции.

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

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

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

а затем вернуться на шаг назад и матрицу Гессе в дальнейшем не изменять.

В этом случае сходимость метода уменьшается, но и ошибка округления также снижается.

1.2 Задание

Зависимость расходов предприятия, прогнозируемых на будущий квартал от факторов x1, x2 задаётся в некоторых денежных единицах функцией

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

Фиксировать x3=0,31

1.3 Построение математической модели задачи

Задача минимизации функции от двух переменных сводится к нахождению таких значений х1* и х2*, при которых

При kv=0.739,

Найдём производную функции по переменной х1:

Найдём производную функции по переменной х2:

Найдём вторую производную функции по переменной х1:

Найдём вторую производную функции по переменной х2:

Найдём вторую производную функции по переменным х1 и х2:

Таким образом, градиент функции будет равен:

Далее необходимо определить величину шага? k, для которого бы выполнялось неравенство: f (x (k+1))

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

x1(k+1) = х (к) -?к * grad (f (x1(k)))

x2(k+1) = х (к) -?к * grad (f (x2(k)))

до тех пор, пока не выполнятся условия останова:

u1:

где

u2:

u3:

где

u4: Если условия u2 u3 выполняются, а условие u1 нет, на протяжении 10 итераций, вычисления прекратить и вывести результат.

1.4 Решение задачи

Необходимо найти величину шага. За начальную точку берём х1(0)=0 и х2(0)=0. f (х1(0); х2(0))=16,43.

1) ?0(1)=1

х1(1)=-1,3388

х2(1)=0,9076

f (х1(1); х2(1))=33,59

Получили f (x (k+l)) > f (x (k)), таким образом, следует уменьшить шаг.

2) ?0(2)=0,5

х1(2)=8,8788

х2(2)=-4,2155

f (х1(2); х2(2))=765,129

Получили f (x (k+l)) > f (x (k)), таким образом, следует уменьшить шаг.

3) ?0(3)=0,25

х1(3)=-25,6164

х2(3)=11,1324

f (х1(3); х2(3))=5923,182

Получили f (x (k+l)) > f (x (k)), таким образом, следует уменьшить шаг.

4) ?0(4)=0,125

х1(4)=23,2581

х2(4)=-9,4773

f (х1(4); х2(4))=4857,293

Получили f (x (k+l)) < f (x (k)), величина шага выбрана ?0=0,125

Метод градиентного спуска:

1 итерация:

х1(1)=-1,3388

х2(1)=0,9076

u1: =17.1637

Ef=8.399*10−6

Условие останова не выполняется, т.к.

u2: =1.62 621

Ex=0.808

Условие останова не выполняется, т.к.

u3: =10.818

E'=0.211 653

Условие останова не выполняется, т.к.

2 итерация:

х1(2)=8.8788

х2(2)=-4.2156

u1: =731.5315

Ef=0.191

Условие останова не выполняется, т.к.

u2: =11.43 007

Ex=0.4 914

Условие останова не выполняется, т.к.

u3: =76.5888

E'=4.820 012

Условие останова не выполняется, т.к.

Последняя итерация:

х1(k+1)=-0.5 001 334

х2(k+1)=0.1 100 748

u1: =1.2805*10−9

Ef=4.8 599*10−6

Условие останова выполняется, т.к.

u2: =5.8072*10−5

Ex=6.45 204*10−5

Условие останова выполняется, т.к.

u3: =0.2 276

E'=0.10 296

Условие останова выполняется, т.к.

Все три условия останова выполняются, следовательно в точках

x*=(-0.5 001 334;0.1 100 748) функция достигает своего минимума равного

f (-0.5 001 334;0.1 100 748)=8,2 853 964

На этом останавливаемся и проводим последнюю итерацию методом Ньютона:

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

х1(0)=-0.5 001 334

х2(0)=0.1 100 748

Подставив вычисленные вторые производные в этих точках в систему уравнений (1,3), решаем её.

14*? х1(1)-3*? х2(1)=0,27 918

— 3*? х1(1)+8*? х2(1)=-0,58

Получаем

? х1(1)=0,4 764

? х2(1)=-0,0707

Проверяем условия останова:

u1: =0,16 797

Ef=4.14 861*10−6

Условие останова выполняется, т.к.

u2: =0,8 525

Ex=4,2626*10−5

Условие останова выполняется, т.к.

u3: =0,17 054

E'=0,10 453

Условие останова выполняется, т.к.

Решение найдено. Функция

принимает свое минимальное значение 8,2 853 964 в точках x*=(0,4 764; -0,0707)

1.5 Тестирование задачи на ЭВМ

2. Задача линейного планирования производства

2.1 Теоретическая часть

Задачи линейного программирования находят широкое распространение в различных областях:

· Энергетике — рациональная организация электрификации районов с помощью различных видов электростанций;

· Химии — составление сложных смесей с заданным составом компонентов;

· Сельском хозяйстве — рациональное распределение посевных площадей под различные культуры;

· Металлургиирасчёт шихты для получения специальных легированных сталей;

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

Для переменных x1, x2, …, xn найти такие неотрицательные значения

xj?0, j=1.n

которые обращали бы в максимум целевую функцию

F=c0+> max

и удовлетворяли системе равенств

i=1.m

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

Если неизвестных переменных n, а ограничений m, то можно m неизвестных выразить через остальные (n-m) переменных, которые играют роль произвольных постоянных и называются свободными. Те m неизвестных переменных, которые выражаются через свободные, называются базисными.

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

Пронумеруем переменные таким образом, чтобы вначале шли свободные переменные (x1, …, xk), а далее базисные переменные (xk+1, …, xn)

x1, x2, …, xk, xk+1, xk+2, …, xk+i, …, xn

Выразим базисные переменные и целевую функцию через свободные переменные:

xk+i=bi — i=1.m

F=c0+> max

При решении задач линейного программирования принято находить минимум целевой функции, то есть f (x) > min, где f (x)=-F (x)

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

1. графоаналитический метод;

2. симплекс-метод;

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

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

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

Далее следует уловить тот момент, в котором эта линия имеет последнюю общую точку с ОДР.

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

Для решения задачи линейного программирования симплекс-методом все ограничения должны иметь вид равенств.

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

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

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

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

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

Пусть имеется некоторая начальная симплекс-таблица:

xm, xr, xl — базисные неизвестные;

xs, xk — свободные неизвестные;

?ms, ?rs, ?ls, ?fs — коэффициенты, стоящие перед свободной неизвестной хs, в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно;

?mk, ?rk, ?lk, ?fk —коэффициенты, стоящие перед свободной неизвестной xk, в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно;

?m0, ?r0, ?l0, ?f0 —свободные члены в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно.

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

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

Если в строке для целевой функции есть хотя бы один отрицательный коэффициент и в этом же столбце есть ещё хотя бы один отрицательный коэффициент, то целевую функцию можно уменьшить за счёт увеличения соответствующей свободной неизвестной. Это увеличение ограничено вследствие отрицательности коэффициента в выражении для базисной неизвестной. Из выражения базисной неизвестной через свободную находится предел свободной неизвестной. Например, в приведённой выше симплекс-таблице в строке для целевой функцииf (x)коэффициент ?fs > 0, акоэффициент ?fk < 0. Приэтом коэффициенты? rk и? lk, стоящие в столбце свободной неизвестной хk отрицательные. Для отрицательных коэффициентов найдём отношение

(i=r, l)

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

mini ()=

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

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

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

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

Получаем следующую симплекс-таблицу:

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

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

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

2.2 Задание

Фирме требуется уголь с содержанием примеси фосфора не больше 0,05% и с примесью пепла не более 4,00%. Доступны 3 сорта угля A, B, C по следующим ценам (за тонну):

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

2.3 Построение математической модели задачи

экономический математический модель градиент

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

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

Обозначим за x1, x2, x3 количество изделий А, В, С соответственно, с учетом того, что требуется уголь с содержанием примеси фосфора не более 0,05% и примеси пепла не более 4,00%. Связь между сортами угля каждого вида и количеством примесей выразится в системе следующим образом:

(1.1)

По смыслу задачи переменные

x1?0, x2?0, x3?0 (1.2)

Прибыль от реализации трех сортов угля будет выражена функцией:

F=35×1+30×2+48×3 (1.3)

Экономико-математическая модель задачи: найти такое количество каждого сорта угля, x=(x1, x2, x3), удовлетворяющее системе (1.1) и условию (1.2), при котором функция (1.3) принимает максимальное значение:

F=35×1+30×2+48×3 > max

f = -35×1−30×2−48×3 > min

2.4 Решение задачи

Решение задачи графоаналитическим методом

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

F=35×1+30×2 > max

f = -35×1−30×2 > min

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

x1?0, x2?0

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

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

Найдем градиент и антиградиент функции:

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

Далее следует уловить тот момент, в котором эта линия имеет последнюю общую точку с ОДР.

Чтобы найти решение необходимо решить систему:

Оптимальное решение:

т. А (0,28;0,78)

F (0,28;0,78)=35*0,28+30*0,78=33,2

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

x4?0, x5?0

После приведения задачи к канонической форме необходимо выбрать первоначальный базис. В качестве базисных переменных возьмем x4, x5, а оставшиеся три переменные x1, x2, x3 будут свободными неизвестными. При этом необходимо, чтобы базисные неизвестные обладали следующим свойством: если все остальные неизвестные (x1, x2, x3) принять равными нулю, то переменные, выбранные в качестве базисных, должны быть неотрицательными.

Базисные переменные нужно выразить через свободные неизвестные:

Запишем опорный план:

Целевую функцию нужно выразить через свободные неизвестные:

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

Отрицательные коэффициенты стоят перед x1, x2 и х3.

Из первого уравнения следует, что х1=0,79.

Из второго уравнения следует, что x2=0,95.

Из второго уравнения следует, что x3=1,08.

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

fx1=-27,65, fx2=-28,57, fx3=-51,84

То есть целесообразно ввести в базис x3, тогда x5 выводим из базиса.

Рассчитаем новый базис:

Получаем базис:

Целевую функцию нужно выразить через свободные неизвестные:

Так как x1, x2 и x5 имеют отрицательные коэффициент, значит базисное решение не является оптимальным.

Выясним, до какого предела можно увеличивать x1, x2 и x5:

из второго уравнения следует ограничение: x1 =0,64;

из первого уравнения следует ограничение: x2 =0,95;

из второго уравнения следует ограничение: x5 =4;

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

fx1=-20,77; fx2=-27,41; fx5=-0,77;

То есть целесообразно ввести в базис x2, тогда x3 выводим из базиса.

Рассчитаем новый базис:

Получаем базис:

Целевую функцию выражаем через свободные переменные:

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

Выясним, до какого предела можно увеличивать x1:

из второго уравнения следует ограничение: x1 =0,38;

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

fx1=-12,53;

То есть целесообразно ввести в базис x1, тогда x4 выводим из базиса.

Рассчитаем новый базис:

Получаем базис:

Видно, что в полученной функции не содержится отрицательных коэффициентов при x, следовательно найденное решение является оптимальным и Fmax=33,605.

Следовательно, наиболее выгодная смесь сортов углей это 0,295 единиц сорта A и 0,776 единиц сорта B, сорт C покупать не выгодно.

Рассмотрим решение данной задачи табличным симплекс-методом.

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

x4?0, x5?0

После приведения задачи к канонической форме необходимо выбрать первоначальный базис. В качестве базисных переменных возьмем x4, x5, а оставшиеся три переменные x1, x2, x3 будут свободными неизвестными. При этом необходимо, чтобы базисные неизвестные обладали следующим свойством: если все остальные неизвестные (x1, x2, x3) принять равными нулю, то переменные, выбранные в качестве базисных, должны быть неотрицательными.

Базисные переменные нужно выразить через свободные неизвестные:

Запишем опорный план:

Целевую функцию нужно выразить через свободные неизвестные:

Составляем начальную симплекс-таблицу:

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

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

Отрицательные коэффициенты стоят перед x1, x2 и х3.

Из первого уравнения следует, что х1=0,79.

Из второго уравнения следует, что x2=0,95.

Из третьего уравнения следует, что x3=1,08.

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

fx1=-27,65, fx2=-28,57, fx3=-51,84

То есть целесообразно ввести в базис x3, тогда x5 выводим из базиса.

Следующий шаг — составление новой симплекс-таблицы. В ней x3, x4 будут базисными переменными, а x1, x2, x5 — свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.

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

Выясним, до какого предела можно увеличивать x1, x2 и x5:

из второго уравнения следует ограничение: x1 =0,64;

из первого уравнения следует ограничение: x2 =0,95;

из второго уравнения следует ограничение: x5 =4;

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

fx1=-20,77; fx2=-27,41; fx5=-0,77;

То есть целесообразно ввести в базис x2, тогда x3 выводим из базиса.

Следующий шаг — составление новой симплекс-таблицы. В ней x2, x4 будут базисными переменными, а x1, x3, x5 — свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.

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

Выясним, до какого предела можно увеличивать x1:

из второго уравнения следует ограничение: x1 =0,38;

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

fx1=-12,53;

То есть целесообразно ввести в базис x1, тогда x4 выводим из базиса.

Следующий шаг — составление новой симплекс-таблицы. В ней x1, x2 будут базисными переменными, а x3, x4, x5 — свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.

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

Следовательно, наиболее выгодная смесь сортов углей это 0,295 единиц сорта A и 0,776 единиц сорта B, сорт C покупать не выгодно.

3. Задача оптимального распределения перевозок

3.1 Теоретическая часть

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

В типичной транспортной задаче предполагается наличие некоторого количества пунктов отправления А1, А2, …, Аm (это могут быть склады, базы, хранилища и др.) и некоторого количества пунктов назначения В1, В2, …, Вn (это могут быть фабрики, магазины и др.).

Задаётся количество груза, которое должно быть вывезено из каждого пункта отправления, а также количество груза, которое должно быть доставлено в каждый пункт назначения. Ещё задаётся некоторая величина, определяющая стоимость перевозки (или эквивалентная ей характеристика перевозки) из пункта Оi, в пункт Нj. Если в качестве критерия оптимальности взять минимальную стоимость перевозок всего груза, то

cij — стоимость перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения;

ai — запасы груза в i-ом пункте отправления;

bj — потребности в грузе в j-ом пункте назначения;

xij — количество единиц груза, перевозимого из i-ого пункта отправления в j-ый пункт назначения.

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

В случае, если запасы груза превышают потребность в них, то есть, то вводится фиктивный (n+1)-ый пункт назначения с потребностью bn+1=и стоимостью перевозки единицы груза (или эквивалентной характеристики) принимается равной нулю, то есть сi n+1=0 при i=1.m

В случае, если потребности больше, чем запасы груза, то есть, то вводится фиктивный (m+1)-ый пункт отправления с запасом груза am+1= и стоимость перевозки единицы груза (или эквивалентной характеристики) считаются равными нулю, то есть сm+1 j при j=1.n

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

> min

Ограничения:

1) наличие в каждом пункте отправления определённого количества товаров:

(i=1.m)

2) потребность у каждого пункта назначения в определённом количестве товаров:

(j=1.n)

3) xij?0 (i=1.m, j=1.n)

Количество переменных хij в задаче с m пунктами отправления и n пунктами назначения равно (m * n), а число уравнений равно (m + n). Для того, чтобы соблюдалось равенство, число линейно независимых уравнений должно быть равно (m + n — 1). Таким образом, базис будет содержать (m + n — 1) неизвестных.

Базис является невырожденным, если в нём число отличных от нуля компонент точно совпадает с (m + n — 1). Если же это число меньше нуля, то базис — вырожденный.

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

Метод северо-западного угла является одним из наиболее простых и распространенных методов, но он дает самый далекий от оптимального план. В этом случае начинаем заполнять таблицу с крайней левой верхней клетки (C11) наибольшим возможным объемом груза. Затем вычеркиваем соответствующую строку или столбец и заполняем ставшую крайней левой верхней свободную клетку (т.е. C12 или C21). Продолжаем до тех пор, пока полностью не определим начальный базис.

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

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

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

Потенциалы находятся при рассмотрении занятых клеток. Поскольку количество таких клеток (m+n-1), а общее количество клеток (m*n), то количество потенциалов на единицу больше, чем базисных клеток, поэтому один из потенциалов можно задать произвольно (обычно задают нулевой потенциал).

Обозначим потенциалы строк через ui, а потенциалы столбцов через vj. Потенциал столбца находится так, чтобы для базисных клеток сумма потенциалов была равна стоимости перевозок, то есть

ui+vj = cij

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

cij'= ui+vj

Затем, для каждой свободной клетки определяется разность:

fkl'=ckl — ckl' ,

где к и l — индексы свободных клеток.

Оптимальное решение найдено, если все разности fkl'=ckl — ckl' для свободных клеток неотрицательные. Выражение для целевой функции через свободные неизвестные имеет все неотрицательные коэффициенты, значит уменьшить функцию дальше нельзя, найдено оптимальное решение.

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

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

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

1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают знак («+» или «—»), причём свободной клетке — знак плюс, а всем остальным клеткам — поочерёдно знаки минус и плюс;

2) в данную свободную клетку переносят меньшее из чисел xij, стоящих в клетках со знаком «—», одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком «+», и вычитают из чисел, стоящих в клетках со знаком «—».

Клетка, которая ранее была свободной, будет занятой, а клетка с наименьшей загрузкой и со знаком «—"станет свободной.

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

3.2 Задание

Имеется четыре завода А1, А2, А3, А4, из которых нужно вывести некоторое количество грузов. И пять пунктов назначения В1, В2, В3, В4, В5, в которые должны быть привезены товары с заводов. Количество товаров в каждом пункте отправления, потребности каждого пункта назначения и тарифы на доставку приведены в таблице.

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

3.3 Построение математической модели задачи

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

(2.1)

на множестве допустимых планов:

(2.2)

При соблюдении баланса

.(2.3)

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

Обозначим через xij количество продукции, перевозимой из i-го склада в j-ый магазин. Тогда условия перевозки грузов обеспечиваются за счет выполнения следующих равенств:

(2.4)

При данном плане перевозок общая стоимость перевозок составит:

F=5*x11+3*x12+24*x13+10* x14+25* x15+30*x21+2*x22+22*x23+16*x24+7* *x25+30*x31+24*x32+27*x33+29*x34+10*x35+15*x41+17*x42+21*x43+2*x44+3*x45 (2.5)

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

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

3.4 Решение транспортной задачи

1. Метод северо-западного угла.

Заполняется клетка С11 максимальным грузом, затем вычеркивается соответствующая строка или столбец. Затем заполняется клетка С12 или С21 максимальным грузом равным А1-В1, затем вычеркивается соответствующая строка или столбец и процесс повторяется.

Опорный план приведен в таблице.

Так как число отличных от нуля компонент точно не совпадает с (m + n -1), n-число складов, mколичество магазинов, то базис является вырожденным. Следовательно для устранения этого вводим нулевую загрузку в клетку с наибольшим тарифом.

F=5*12+3*12+30*0+2*1+22*14+29*16+2*15+3*9=927

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

1) С завода А1 будет отправлено 12 шт. товара потребителю B1 и 12 шт. товара потребителю B2

2) С завода А2 будет отправлена 1 шт. товара потребителю B2 и 14 шт. товара потребителю B3

3) С завода А3 будет отправлено 15 шт. товара потребителю B4

4) С завода А4 будет отправлено 15 шт. товара потребителю B4 и 9 шт. товара потребителю B5.

2. Метод Фогеля

Для каждой строки и столбца находим штраф — это модуль разности двух наименьших стоимостей перевозок. Заполнение выполняется с наибольшего штрафа. Опорный план приведен в таблице.

Так как число отличных от нуля компонент точно совпадает с (m + n -1), n-число складов, mколичество магазинов, то базис является невырожденным.

Минимальная стоимость перевозок составляет:

fmin = 5*12+24*5+7*10+2*13+22*2+27*7+10*9+2*24= 647

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

1) С завода А1 будут отправлены 12 шт. товара потребителю B1, 5 шт. товара потребителю B3 и 7 шт. товара потребителю B4.

2) С завода А2 будут отправлены 13 шт. товара потребителю B2и 2 шт. товара потребителю B3.

3) С завода А3 будет отправлено 7 шт. товара потребителю B3 B2и 9 шт. товара потребителю B5.

4) С завода А4 будут отправлены 24 шт. товара потребителю B4.

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

Так как число отличных от нуля компонент точно совпадает с (m + n -1), n-число складов, mколичество магазинов, то базис является невырожденным.

F=5*12+24*12+2*13+4*2+27*2+29*7+10*7+2*24=757

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

1) С завода А1 будет отправлено 12 шт. товара потребителю B1 и 12 шт. товара потребителю B3

2) С завода А2 будут отправлены 13 шт. товара потребителю B2 и 2 шт. товара потребителю B5

3) С завода А3 будет отправлено 2 шт. товара потребителю B3, 7 шт. товара потребителю B4 и 7 шт. товара потребителю B5

4) С завода А4 будет отправлено 24 шт. товара потребителю B4.

Найденный опорный план проверяем на оптимальность с помощью метода потенциалов.

4. Метод потенциалов

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

Далее для клеток, не вошедших в базис, вычисляются косвенные стоимости, которые принято указывать в верхнем правом углу. Затем, для каждой свободной (пустой) клетки определяется разность, где k и l — индексы клеток, не вошедших в базис. Эти значения пишутся в нижнем правом углу клеток.

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

Выполнив цикл пересчета получим таблицу.

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

Выполнив цикл пересчета получим таблицу.

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

Выполнив цикл пересчета получим таблицу.

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

Минимальная стоимость перевозок составляет:

fmin = 5*12+3*5+10*7+2*8+22*7+27*7+10*9+2*24= 453

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

1) С завода А1 будут отправлены 12 шт. товара потребителю B1, 5 шт. товара потребителю B2 и 7 шт. товара потребителю B4.

2) С завода А2 будут отправлены 8 шт. товара потребителю B2 и 7 шт. товара потребителю B3.

3) С завода А3 будет отправлено 7 шт. товара потребителю B3 и 9 шт. товара потребителю B5.

4) С завода А4 будут отправлены 24 шт. товара потребителю B4.

Заключение

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

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

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

Приложение1. Блок-схема к задаче безусловной минимизации функции нескольких переменных Вычисление основной функции

Вычисление производной по х1

Вычисление производной по х2

Основная программа:

Приложение2

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

{Программа, реализующая поиск}

{поиск безусловного минимума функции}

{нескольких переменных}

{методом градиентного спуска}

program kurs;

uses crt;

Const

x3=0.0308;{фиксированная переменная}

var

x0,x1:array [1.2] of real;{k-ое и (k+1)-ое приближение}

alfa:real;{шаг}

u1,u2,u3,u4:boolean;{условия останова}

k:integer;{счътчик итераций}

a, b, tau, xgr, fgr, fgrK, Epr, Ef, Ex: real;{погрешности измерений}

{основная функция}

Function f (x1,x2:real):real;

begin

f:=7*sqr (x1)+4*sqr (x2)+6*sqr (x3)-3*x1*x2+x3*x1-x3*x2+x1-x2+x3+82.9;

end;

{производная по х1}

Function DfDx1(x1,x2:real):real;

begin

DfDx1:=14*x1−3*x2+x3+1;

end;

{производная по х2}

Function DfDx2(x1,x2:real):real;

begin

DfDx2:=8*x2−3*x1-x3−1;

end;

begin

clrscr;

alfa:=1; {шаг}

x0[1]: =x3; {начальное приближение}

x0[2]: =x3;

tau:=25*0.1;

fgr:=0.0001;

xgr:=0.0001;

fgrK:=0.001;

u1:=false;

u2:=false;

u3:=false;

u4:=false;

k:=0;{счътчик итераций}

repeat

k:=k+1;

x1[1]: =x0[1]-alfa*DfDx1(x0[1], x0[2]);{вычисление приближений х}

x1[2]: =x0[2]-alfa*DfDx2(x0[1], x0[2]);

if f (x1[1], x1[2])>f (x0[1], x0[2])