Реферат: Математические методы оптимизации
Задание 1. Графическоерешение задачи распределения ресурсов
· Записать стандартнуюи каноническую формы.
· Найти все базисныеи допустимые базисные решения. Определить оптимальное базисное решение.
· Найти графически оптимальноебазисное решение.
Фирма выпускает два вида изделийА и В. Каждое изделие проходит обработку на двух технологических линиях.
Известна таблица технологическихкоэффициентов /> - времени обработки(в минутах) каждого изделия на каждой технологической линии. Кроме этого, известнырыночная цена каждого изделия /> и /> и общее время каждой линии/> и />.
Изделия А Изделия В Общее время работы линии Линия 1 60 32 1920 Линия 2 36 60 2160 Цена одного изделия 30 25РЕШЕНИЕ
Запишем стандартную и каноническуюформы
Обозначим:
/>план выпуска изделия А;
/>план выпуска изделия В.
Тогда затраты линии 1 и линии2, необходимые для производства плана /> будутравны соответственно:
/>
План /> будет допустимым, если затратыдля линии 1 и линии 2 не превосходят общего времени работы каждой из линий, т.е.выполняются неравенства:
/>
Целевой функцией служит выручкаот реализации допустимого плана /> /> при ограничениях
/> (1.1)
Для канонической формы этиограничения нужно преобразовать в равенства. Для этого введём две дополнительныепеременные
/>остаток от производства на линии 1(остаток времени обработки)
/>остаток от производства на линии 2(остаток времени обработки).
Тогда получим каноническуюформу задачи:
-найти переменные />, которые дают максимум целевойфункции
/> при ограничениях
/> (1.2)
· Найдём все базисныерешения.
Полученные ограничения образуютсистему двух уравнений с четырьмя неизвестными. Среди бесконечного множества решенийэтой системы базисные решения получаются следующим образом. Две переменных приравняемк 0. Эти переменные назовём свободными. Значения остальных переменных получаем изрешения системы. Эти переменные назовём базисными. Базисное решение называется допустимым,если оно неотрицательно.
1) Пусть />свободные переменные.Подставляя значения /> (1.2), получаем системууравнений
/>
Следовательно, базисное решениеимеет вид
/>.
Базисное решение означает,что изделия А и изделия В не производятся. Это базисное решение является допустимым.Выручка от реализации этого плана составит
/>.
2) Пусть />свободные переменные. Подставляязначения /> (1.2) получаем систему
/>
Следовательно, базисное решениеимеет вид
/>.
Это базисное решение означает,что изделие А не производится, изделие В производится в количестве 60 ед., времяизготовления продукции на линии 1 используется полностью, для производства на линии2 не хватает 1440 минут работы. Это базисное решение не является допустимым.
3) Пусть />свободные переменные. Подставляязначения /> в (1.2) получаем систему
/>
для базисных переменных /> и />. Следовательно, базисное решениеимеет вид
/>.
Это базисное решение означает,что изделие А не производится, изделие В производится в количестве 36 единиц, времяизготовления продукции линии 1 используется не полностью и его остаток составляет768 минут, а на линии 2 используется полностью. Это базисное решение является допустимым.Выручка от реализации этого плана составит /> ден.ед.
4) Пусть />свободные переменные. Подставляязначения /> в (1.2) получаем систему
/>
для базисных переменных />. Следовательно, базисное решениеимеет вид />. Базисное решение означает,что изделия А производится в количестве 32 ед., изделие В не производится, времяизготовления продукции линии 1 используется полностью, а время изготовления линии2 не полностью используется, его остаток составляет 1008 минут. Это базисное решениеявляется допустимым. Выручка от реализации этого плана составит
/> ден. ед.
5) Пусть />свободные переменные. Подставляязначения /> в (1.2) получаем систему
/>
для базисных переменных />. Следовательно, базисное решениеимеет вид />. Это базисное решение означает,что изделия А производится 60 ед., изделие В не производится, не хватает времениобработки 1680 минут для первой линии, а время обработки второй линии используетсяполностью. Это базисное решение не является допустимым.
6) Пусть />свободные переменные. Тогдабазисные переменные /> и /> найдём из системы уравнений
/>
Отсюда следует, что базисноерешение имеет вид />. Это решение означает,что изделия А производятся в количестве />ед.,изделия В производятся в количестве />, время обработкина каждой из линий используется полностью. Это базисное решение является допустимым.Выручка от реализации составит /> ден.ед.
· Определим оптимальноебазисное решение.
Из теории линейного программированияследует, что оптимальное решение можно найти среди допустимых базисных решений.Отсюда следует, что для определения оптимального решения нужно вычислить значенияцелевой функции на всех допустимых базисных решениях. Оптимальным будет базисноерешение, на котором значение целевой функции наибольшее.
В таблице 1.1 приведены вседопустимые базисные решения и соответствующие им значения выручки />.
двойственныйзадача равновесный спрос полезность товар
Таблица 1.1
№ Базисные переменные Небазисные переменные/>
1/>
/>
/>
/>
/>
2/>
/>
/>
/>
/>
3/>
/>
/>
/>
/>
4/>
/>
/>
/>
/>
Максимальное значение выручкидостигается на четвёртом базисном решении в этой таблице
/>
Следовательно, изделие А производитсяв количестве /> ед., изделие В производитсяв количестве /> ед., время обработкина каждой из линий используется полностью (/>).
Графическое решение задачи
Рассмотрим задачу в стандартнойформе: найти переменные />, которыеобеспечивают максимальное значение функции />
/>
при ограничениях
/>
На горизонтальной оси прямоугольнойсистемы координат будем откладывать план выпуска продукции />, а на вертикальной – план выпускавторой продукции />.
Рассмотрим первое ограничение/>. Множество точек, удовлетворяющихравенству />, образует прямую на плоскости.Построим эту прямую по её точкам пересечения с осями координат. Для определениякоординат точки А пересечения с осью /> в уравнениеподставим />. Из него следует />, т.е />. Для определения координатточки В пересечения с осью /> в уравнениеподставим />. Из него следует />, т.е. />. Неравенству /> удовлетворяют все точки однойиз полуплоскостей, которые образовала построенная прямая. Для её определения достаточнопроверить справедливость неравенства для одной точки. Для начала координат /> неравенство выполняется. Следовательно,все точки полуплоскости, содержащей начало координат, будут графическим изображениемэтого неравенства. Аналогично построим прямую /> поеё точкам пересечения с осями координат: />.Все точки полуплоскости, содержащей начало координат /> будут графическим изображениемнеравенства />. Учитывая ограничения назнак />, множество точек четырёхугольника/> является множеством всех допустимыхрешений. Все угловые точки (крайние точки) четырёхугольника /> соответствуют допустимым базиснымрешениям:
угловая точка /> соответствует базисному решению
/>, />,/>;
угловая точка /> соответствует базисному решению
/>, />,/>, />;
угловая точка /> соответствует базисному решению
/>, />,/>, />;
угловая точка /> соответствует базисному решению/>, />, />, />.
/>
Теперь графически найдём точкучетырёхугольника />, которая определитоптимальное решение.
Из теорем математическогоанализа следует, что оптимальное решение следует искать только среди точек границычетырёхугольника />. Для её определенияв начале координат построим вектор />,координаты которого являются рыночными ценами. Прямая /> проходит через начало координатперпендикулярно вектору />. Она определяетвсе планы, в которых выручка равна 0. Вектор /> указываетнаправление возрастания выручки. Если прямую нулевой выручки (розовая линия) перемещатьпараллельно в направлении вектора />, то значениевыручки будет увеличиваться. Так как среди внутренних точек четырёхугольника /> оптимального решения не можетбыть, то прямую нужно переместить до границы четырёхугольника />, т.е. до точки />.
/>
Таким образом, точка /> определяет оптимальное решение.Соответствующее точке /> базисное решение
/>
является оптимальным решением.Максимальная выручка будет равна />. Уравнение/> определяет уравнение максимальнойвыручки (верхняя розовая линия).
Задание 2.Двойственная задача
· Записать двойственнуюзадачу и дать её экономический смысл.
· Найти оптимальноерешение двойственной задачи.
· Определить целесообразностьпроизводства продукции С, для которой на изготовление единицы продукции требуется60 минут и 50 минут времени изготовления на первой и второй линии соответственно.Рыночная цена составляет 120 ден. ед. за единицу продукции.
РЕШЕНИЕ
Запишем двойственную задачуи дадим её экономический смысл.
Правило построения двойственнойзадачи состоит в следующем. Каждому равенству прямой задачи соответствует двойственнаяпеременная
/>
Стрелки показывают, что первомуравенству соответствует переменная />, а второму– переменная />.
Для определения целевой функции/> двойственной задачи двойственныепеременные /> и /> умножаются на правые частиравенств и складываются:
/>.
Каждой переменной прямой задачи/> соответствует ограничение двойственнойзадачи. Левые части этих ограничений для переменной /> записываютсяследующим образом. Двойственные переменные /> и/> умножаются на коэффициентыперед переменной /> и складываются: />.
Аналогично, записываются левыечасти ограничений для переменной />. Двойственныепеременные /> и /> умножаются на коэффициентыперед переменной /> и складываются: />. Левая часть ограничений дляпеременной /> равна />, а для переменной />. Правые части ограничений равныкоэффициентам 30, 25, 0, 0 целевой функции />
/>
перед переменными />. Левые и правые части ограниченийсоединяются знаком />.
В результате двойственнаязадача имеет вид:
найти двойственные переменные/> и />, при которых целевая функция/> минимальна
/>
при ограничениях
/>
Переменные />, называются допустимым решениемдвойственной задачи, если они удовлетворяют всем ограничениям и оптимальными, еслиони допустимые и на них целевая функция /> достигаетминимума.
Экономический смысл двойственнойзадачи:
двойственная переменная /> определяет теневую цену работы1 минуты оборудования линии 1, а двойственная переменная /> определяет теневую цену работы1 минуты оборудования линии 2.
Тогда целевая функция /> задаёт стоимость времени работыоборудования в теневых ценах соответственно для линии 1 и линии 2.
Выражение /> определяет стоимость 60 минути 36 минут, затраченных на изготовление единицы изделия А в теневых ценах, а выражение/> определяет стоимость 32 минути 60 минут, затраченных на изготовление единицы изделия В в теневых ценах.
Определим величины приведённыхстоимостей.
/>
Если величина /> положительна, то стоимостьресурсов больше рыночной цены этого продукта. В этом случае производство продуктаубыточно. Если величина /> отрицательна,то стоимость ресурсов меньше рыночной цены этого продукта. Если величина /> равна 0, то стоимость ресурсовравна рыночной цене. Ограничения двойственной задачи
/>
Отсюда следует, что при допустимыхтеневых ценах /> производство обоихпродуктов неприбыльно.
Можно дать следующую экономическуюинтерпретацию двойственной задачи. Некоторая фирма предлагает производителю продукциипродать ей все запасы ресурсов по теневым ценам /> и/>. Решение двойственной задачиопределяет минимальный уровень рыночных цен />,при котором производить продукцию неприбыльно.
Найдём оптимальное решениедвойственной задачи
Из первого задания следует,что допустимое базисное решение
/>
является оптимальным решениемпрямой задачи.
По оптимальному базисномурешению /> прямой задачи найдём оптимальноерешение двойственной. Для этого все ограничения двойственной задачи, соответствующиебазисным переменным /> нужно заменить равенствами
/>
Из этих равенств найдём оптимальныезначения двойственных переменных />, минимальноезначение целевой функции равно
/>.
Оптимальная теневая цена работы1 минуты оборудования линии 1 равна />, а оптимальнаятеневая цена 1 минуты оборудования линии 2 равна />.
Стоимость работытехнологического оборудования, затраченных на изготовление единицы изделия А равна
/>,
а стоимость работытехнологического оборудования, затраченных на изготовление единицы изделия В равна
/>.
Приведённые стоимости каждоговида изделия будут раны
/>
Отсюда следует, что производствоизделий А и В рентабельно.
Определим целесообразностьпроизводства продукции С, для которой на изготовление единицы продукции требуется60 минут и 50 минут времени изготовления на первой и второй линии соответственно.Рыночная цена составляет 120 ден. ед. за единицу продукции. Для этого вычислим стоимостьресурсов, затраченных на изготовление единицы продукции С:
/> ден. ед.
Приведённая стоимость этоговида продукции будет равна
/>.
Отсюда следует, что производствоединицы продукции С принесёт прибыль /> ден.ед.
Задание 3. Функцияполезности
Пусть функция полезности наборовиз двух товаров /> имеет вид />, где
/>.
· Найти набор товаров,который имеет такую же полезность, как набор /> иколичество второго товара равно 1.
· Для набора /> найти предельные полезностипервого и второго товаров.
· В наборе /> количество первого товара увеличиваетсяна 0,1, а второго уменьшается на 0,2. Найти приближённое изменение полезности.
РЕШЕНИЕ
1. Функция полезности имеет вид: />.Найдём полезность набор />:
/>
Кривая безразличия /> определяет все наборы товаров,которые имеют такую же полезность как набор />.Из этого уравнения можно найти набор товаров, в котором количества второго товараравно />, подставив это значение в уравнениекривой безразличия />, />. Таким образом, наборы /> и /> безразличны для потребителя.
2. Найдём частные производныефункции полезности />
/>
Предельная полезность первоготовара в наборе /> равна значению частнойпроизводной /> в точке (3,8):
/>.
Предельная полезность второготовара в наборе /> равна значению частнойпроизводной /> в точке (3,8):
/>
Найдём изменение полезности,если количество первого товара увеличивается на 0,1, т.е. />, а количество второго товарауменьшается на 0,2, т.е. />. Приближённоеизменение полезности вычислим по формуле
/>.
Следовательно, полезностьнабора />, равная />, увеличивается на 0,0065. Такимобразом, полезность нового набора />
Задание 4. МодельСтоуна
Функция полезности потребителяимеет вид
/>, где
/>.
1. Найти равновесный спроси его полезность, если рыночная цена первого товара />,рыночная цена второго товара /> ипотребитель выделяет на приобретение товаров сумму /> денежныхединиц.
2. Найти функции спроса наоба вида товаров.
3. Найти спрос на оба товарапри увеличении дохода на 30 денежных единиц и при уменьшении дохода на 60 денежныхединиц.
РЕШЕНИЕ
1. Функция полезности потребителяимеет вид
/>.
Вычислим равновесный спроспри заданных ценах и доходе. Найдём стоимость минимального набора товаров
/>.
Оставшаяся сумма денег /> распределяется пропорциональнокоэффициентам эластичности этих товаров
/> />.
На приобретение первого товаравыделяется сумма
/>.
На приобретение 2-го товара- сумма
/>.
Поделив выделенные средствана рыночные цены товаров, получаем количество товара, приобретаемое сверх установленныхнормативов
/>
Таким образом, оптимальныйспрос составит
/> единиц первого товара и
/> единиц второго товара.
Полезность равновесного наборабудет равна
/>.
2. Найдём функции спроса,заменяя в формулах спроса
/>, /> />.
/>
/>
Эти формулы определяют спросна продукцию при любых ценах и доходах.
3. Оценим влияние на спросизменения дохода обоих товаров. Найдём реакцию спроса на изменение дохода на 1 денежнуюединицу. Частные производные по доходу /> показываютизменение спроса на первый и второй товары соответственно при возрастании доходана 1 денежную единицу.
Дифференцируя полученные вышефункции спроса по М, получаем
/> />.
Вычислим эти частные производныепри заданных /> и />:
/>/>/>.
Так как значения частныхпроизводных положительные, то оба товара являются ценными: с ростом дохода на 1денежную единицу спрос на оба товара растёт: спрос на первый товар увеличиваетсяна />, а второго — на />.
При увеличении дохода потребителяна 30 денежных единиц спрос на первый товар увеличится на /> единицы, а второго на /> и составит
/>, />.
При уменьшении дохода потребителяна 60 денежных единиц спрос на первый товар снизится на /> единиц, а спрос на второй товарснизится на /> единиц и составит соответственно:
/>, />.