Вы на НеОфициальном сайте факультета ЭиП

На нашем портале ежедневно выкладываются материалы способные помочь студентам. Курсовые, шпаргалки, ответы и еще куча всего что может понадобиться в учебе!
Главная Контакты Карта сайта
 
Где мы?
» » » ПРАКТИКУМ ПО ПРИМЕНЕНИЮ ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ И МОДЕЛЕЙ. Часть 2.

Реклама


ПРАКТИКУМ ПО ПРИМЕНЕНИЮ ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ И МОДЕЛЕЙ. Часть 2.

Просмотров: 4852 Автор: admin

ПРАКТИКУМ ПО ПРИМЕНЕНИЮ ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ И МОДЕЛЕЙ. Часть 2.

 

1.3. Целочисленное программирование
Допустим, что к условию задачи (1.1) добавилось требование целочисленности значений всех переменных. В этом случае описанный выше процесс ввода условия задачи необходимо дополнить следующими шагами.
• В экранной форме укажите, на какие переменные накладывается требование целочисленности (этот шаг делается для наглядности восприятия условия задачи).
• В окне "Поиск решения" (меню "Сервис">"Поиск решения"), нажмите кнопку "Добавить" и в появившемся окне "Добавление ограничений" введите ограничения следующим образом:
• в поле "Ссылка на ячейку" введите адреса ячеек переменных задачи, то есть $B$3:$E$3;
• в поле ввода знака ограничения установите "целое";
• подтвердите ввод ограничения нажатием кнопки "OK".

1.4. Анализ оптимального решения на чувствительность в Excel
Проведем анализ чувствительности задачи. Для этого необходимо после запуска в Excel задачи на решение в окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты" и "Устойчивость".
Если ресурс используется полностью (то есть ресурс дефицитный), то в графе "Статус" ("Состояние") соответствующее ограничение указывается как "связанное"; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается "не связан". В графе "Значение" приведены величины использованного ресурса.
Для граничных условий в графе "Разница" показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.
Таблица 3 отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Так, если на ресурс наложено ограничение типа ?, то в графе "Разница" дается количество ресурса, на которое была превышена минимально необходимая норма.
Если на ресурс наложено ограничение типа ?, то в графе "Разница" дается количество ресурса, которое не используется при реализации оптимального решения.
А. Результат решения задачи.
Б. Нормированная стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение. Например, в отчете по устойчивости для рассматриваемой задачи нормированная стоимость Х3 равна –104,4 руб./шт. Это означает, что если мы, несмотря на оптимальное решение, потребуем включить в план выпуска 1 единицу Х3, то новый план выпуска принесет нам прибыль на 104,4 руб. меньше, чем в прежнем оптимальном решении.
В. Коэффициенты ЦФ.
Г. Предельные значения приращения целевых коэффициентов ?сi , при которых сохраняется первоначальное оптимальное решение. Например, допустимое уменьшение цены на Х1 равно 114,6 руб./шт., а допустимое увеличение – практически не ограничено. Это задает соотношение устойчивости для коэффициентов целевой функции.
Примечание. При выходе за указанные в отчете по устойчивости пределы изменения цен оптимальное решение может меняться как по номенклатуре выпускаемой продукции, так и по объемам выпуска (без изменения номенклатуры).
А. Величина использованных ресурсов в колонке "Результ. значение".
Б. Предельные значения приращения ресурсов ?bj. В графе "Допустимое Уменьшение" показывают, на сколько можно уменьшить (устранить излишек) или увеличить ресурс, сохранив при этом оптимальное решение. Для ограничений, не позволяющих выпускать большее, чем в оптимальном решении, количество продукции и получать более высокую прибыль возникает вопрос, на сколько максимально может возрасти это ограничение, чтобы обеспечить увеличение выпуска продукции. Ответ на этот вопрос показан в графе "Допустимое Увеличение". Это приведет к новым оптимальным решениям, увеличивающим прибыль. Дальнейшее увеличение таких ограничений сверх указанных пределов не будет больше улучшать решение, т.к. уже другие ресурсы станут связывающими.
В. Объективно-обусловленная оценка j-го ресурса (теневая цена) рассчитывается только для существенных (дефицитных) ресурсов. Объективно-обусловленная оценка j-го ресурса показывает, насколько увеличится целевая функция при увеличении j-го ресурса на единицу.
Рассмотрим теперь задачу составления смеси.
ПРИМЕР 1.2. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов.

Задание 1.1. Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость? Составить математическую модель ЗЛП и решить ее на ЭВМ, провести анализ решения. Значение параметра a соответствует номеру своего варианта.
1.5. Задачи с булевыми переменными
Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные xj могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми.
Помимо задания требования целочисленности (см. подразд. 1.3) при вводе условия задач с булевыми переменными необходимо:
• для наглядности восприятия ввести в экранную форму слово "булевы" в качестве характеристики переменных;
• в окне "Поиск решения" добавить граничные условия, имеющие смысл ограничения значений переменных по их единичной верхней границе.

Работа № 2
ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП (ТРАНСПОРТНАЯ ЗАДАЧА).

Цель: научиться методам решения двухиндексных задач линейного программирования на ЭВМ, рассмотреть основные типы задач – транспортная задача, задача о назначении.
Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам, рассмотренным работе 1.
Рассмотрим решение двухиндексной задачи, суть которой заключается в оптимальной организации транспортных перевозок штучного товара со складов в магазины.
ПРИМЕР 2.1. Из трех складов, имеющих некоторый продукт в количествах 50т, 60т, 70т, необходимо его доставить в три магазина в количествах 40т, 85т, 55т. Стоимости перевозки 1т продукта из склада i в магазин j заданы в виде матрицы С={cij} размерностью 3x3. Спланировать перевозки так, чтобы их общая стоимость была минимальной.
В рассмотренном примере суммарное наличие товара на всех складах совпадает с общей потребностью, поэтому в "Поиске решения" мы использовали знак равенства B6:D6=B8:D8 (удовлетворить потребности) и E3:E5=G3:G5 (вывести весь товар) – такая транспортная задача называется закрытой. В случае избытка товара второе условие необходимо записывать со знаком ? , тогда в результате решения у каких-то поставщиков останутся излишки товара. В случае дефицита товара первое условие необходимо записывать со знаком ? , тогда в результате решения какие-то потребители окажутся частично неудовлетворенны (открытые задачи).
ПРИМЕР 2.2. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 500 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:

Задание 2.1. Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.
Значение неизвестного параметра а взять равным номеру варианта.
Рассмотрим еще один вид задач, сводящихся к ЗЛП – задачу о назначениях.
ПРИМЕР 2.3. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:
Задание 2.2. Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?
Значение неизвестного параметра а взять равным номеру варианта.


Работа № 3
РЕШЕНИЕ ДВОЙСТВЕННЫХ ЗАДАЧ И ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Цель: научиться составлять и решать двойственные ЗЛП.
Используя теорию двойственности, научиться методам анализа экономических задач. Получить навыки решения задач нелинейного программирования на ЭВМ.
Рассмотрим решение прямой и двойственной задач на примере задачи определения оптимального ассортимента продукции.
ПРИМЕР 3.1. Предприятие выпускает 2 вида продукции А и В, затрачивая на это три вида ресурсов: Труд, Сырье и Оборудование.
Составить прямую и двойственную задачу, провести анализ решения.
Пусть x1 - количество продукции А, x2 - количество продукции В.
После решения задачи (решите ее самостоятельно на ЭВМ) получаем оптимальные значения переменных x1=200, x2=400, целевая функция при этом равна 32000. Таким образом, рационально выпускать 200 единиц продукции А и 400 единиц продукции В, при этом суммарная прибыль составит 32000.
Составляем двойственную задачу. Введем переменные y1, y2, y3, которые назовем двойственными оценками ресурсов Труд, Сырье и Оборудование соответственно. Они имеют смысл предельных стоимостей единицы каждого вида сырья в случае, если предприятие решит реализовать его вместо готовой продукции. Тогда математическая модель двойственной задачи есть:
Решив данную ЗЛП на ЭВМ (проделать это самостоятельно, перейдя на новый лист электронной таблицы Excel), получаем результаты y1 =13.3333, y2 =0, y3=6.6666.
Целевая функция, как и должно быть, совпадает с оптимальным значением прямой ЗЛП и составляет 32000.
Оптимальные значения переменных также позволяют определить оценки ценности ресурсов. Дефицитный ресурс, полностью используемый в оптимальном плане, имеет положительную ценность. Недефицитный ресурс имеет нулевую ценность, в нашем примере это Сырье, т.к. y2 =0.
В результате производства недефицитные ресурсы остаются, а дефицитные вырабатываются полностью. Среди дефицитных ресурсов более ценным является тот, у которого двойственная оценка выше. В нашем примере Труд дефицитнее, чем Оборудование, т.к. y1 =13.3333> y3=6.6666. Двойственные оценки также позволяют определять целесообразность включения в ассортимент новых видов продукции.
Для решения этой задачи нужно рассчитать сумму произведений затрат производственных ресурсов ai на их двойственные оценки S= . Эта сумма имеет смысл общих затрат на производство, ее сравнивают с прибылью С, полученной от реализации единицы этой продукции. Если S > C, то данную продукцию производить не выгодно. Например, предприятие планирует выпускать еще два изделия E и D. Затраты ресурсов и прибыль для них следующие:
следовательно, продукцию D выпускать выгодно.
Задание 3.1. Предприятие выпускает три вида продукции А, В и С. Для выпуска затрачиваются ресурсы: Труд, Сырье и Энергия.
Составить и решить прямую и двойственную задачи, провести анализ решения. Проанализировать ценности ресурсов. Определить, целесообразно ли включать в план продукцию четвертого вида, если цена единицы этой продукции составляет 70 у.е., а на ее производство расходуется по 2 ед. ресурсов каждого вида.
Отчет должен содержать математическую модель прямой задачи, полученные на ЭВМ из ее решения значения переменных и целевой функции, математическую модель двойственной задачи, оптимальные значения ее переменных и значение целевой функции. Сделать выводы:
1) сколько продукции каждого вида следует выпускать и чему при этом будет равна прибыль;
2) какая оценка ценности каждого ресурса, какие ресурсы дефицитные, а какие нет;
3) какие общие затраты на производство продукции четвертого вида и целесообразно планировать ее выпуск.
Рассмотрим теперь методы решения задач нелинейного программирования на ЭВМ. Такие задачи могут содержать как внутри целевой функции, так и внутри ограничений нелинейные выражения относительно неизвестных переменных. Для решения нелинейных задач также используют надстройку «Поиск решения».
Методы численного решения нелинейных задач почти ни чем не отличаются от методов решения ЗЛП, единственное отличие в том, что при вводе целевой функции и ограничений в ячейках электронной таблицы могут использоваться нелинейные функции.
ПРИМЕР 3.2. Найти максимум функции Z = 3 – 4 + 3,при ограничениях:
4x1 + 3x2 + 2x3 ? 8;
x1,2,3 - целые, положительные.
Вводим на отдельном листе в ячейки А1-С1 произвольные значения, например единицы. В ячейку А2 вводим целевую функцию(кавычки не вводить), в ячейку А3 вводим левую часть основного ограничения. Выбираем «Сервис/Поиск решения». Ссылка на целевую ячейку – А2, стремится к максимуму. Изменяемые ячейки – А1-С1.
Нажимаем «Выполнить», получаем оптимальное решение x1=0; x2=0; x3=4. Целевая функция при этом равна Z* = 192.
Задание 3.2. Найти условные экстремумы целевой функции Z
Значение неизвестного параметра а взять равным номеру варианта.
Отчет должен содержать найденные на ЭВМ оптимальные значения переменных и целевой функции.

Работа № 4
РЕШЕНИЕ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ НА ЭВМ

Цель: научиться методам решения многокритериальных ЗЛП с помощью ЭВМ, используя метод последовательных уступок.
Во многих реальных экономических задачах критериев, которые оптимизируются, может быть несколько. Например, при производстве продукции максимизируется качество и минимизируется себестоимость, при взятии ссуды в банке максимизируется кредитный срок и минимизируется процентная ставка, при выборе места для строительства дома отдыха максимизируются экологические условия и минимизируется расстояние от населенного пункта и пр.
Существует несколько методов решения многокритериальных задач. Одним из наиболее эффективных является метод последовательных уступок, использование которого рассмотрим на примере.
Решить задачу методом последовательных уступок, выбрав уступку по первому критерию d1=4, а по второму d2=5.
Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные x1, x2, x3. Для этого в ячейку А1 вводим подпись «Переменные», а соседние три ячейки В1, С1 и D1 вводим значения переменных. Это могут быть произвольные числа, например единицы, далее они будут оптимизироваться. Во второй строке задаем целевые функции. В А2 вводим подпись «Целевые», задаем первую целевую функцию 2x1 + x2 –3x3 . Аналогично в С2 и D2 вводим вторую и третью целевую функцию. В третью строку вводим левые части ограничений. Для этого вводим в А3 подпись «Ограничения».
Предварительные действия завершены. Вызываем надстройку «Поиск решения» в меню «Сервис». На первом этапе оптимизируем первую целевую функцию.
После открытия окна «Поиск решения» в поле «Установить целевую» ставим курсор и делаем ссылку на ячейку В2, щелкая по ней мышью. В окне появится $B$2. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Равной максимальному значению». После ставим курсор в поле «Изменяя ячейки» и обводим ячейки с переменными В1, С1 и D1, выделяя ячейки с переменными. В поле появится $B$1:$D$1. В нижней части окна находится поле «Ограничения». Для того чтобы ввести ограничения, нажимают кнопку «Добавить», откроется окно «Добавление ограничения». В левом поле «Ссылка на ячейку» вводят ссылку на левую часть первого ограничения – ячейку В3, в центральном окне определяем знак ? и в правом «Ограничения» набираем правую часть ограничения – число 1. Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить», вводим «С3» «?» и «16». Вновь нажимаем «Добавить», вводим «D3» «?» и «24». Для ввода дополнительных ограничений x1, x2, x3?0 вновь нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В1, С1 и D1 (результат $B$1:$D$1) в среднем окне ставим «?» и в правом число 0.
Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат: в ячейках В1, С1 и D1 значения переменных x1, x2, x3, соответствующие оптимальному решению: 11,2; 6,4 и 0. В ячейки В2 – значение целевой функции 28,8.
На втором этапе оптимизируется вторая целевая функция. При этом первую, в соответствие с методом последовательных уступок, можно ухудшить на величину не более чем d1=4. По этой причине, на втором шаге, значения в ячейке В2 (где хранится первая целевая функция, которая максимизируется) может быть не меньшее, чем 28,8–4=24,8. Вызываем надстройку «Сервис/Поиск решения», видим, что все прежние данные остались введенными. Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую» и щелкаем по ячейке С2, в которой находится ссылка на вторую целевую функцию. Так как вторая целевая функция минимизируется, то ставим флажок в поле напротив надписи «Равной минимальному значению». Вводим дополнительное ограничение, связанное с уступкой по первому критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения» в трех окнах (слева направо) вводим данные «В2», «?», «24,8». Результат на рис.4.3.
Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат: переменные x1, x2, x3 равны 10,2; 4,4; 0. Вторая целевая функция равна 23,4 (ячейка В2). Первая равна своему минимальному значению 24,8 (ячейка С2).
На третьем этапе делаем уступку по второму критерию. Величина уступки равна d2=5. Так, как вторая функция минимизируется, то ее значение не должно превышать 23,4+5=28,4. Вызываем надстройку «Сервис/Поиск решения». Меняем ссылку на целевую функцию. Ставим курсор в поле «Установить целевую» и щелкаем по ячейке D2, в которой находится ссылка на третью целевую функцию. Так как третья целевая максимизируется, то ставим флажок в поле напротив надписи «Равной максимальному значению». Вводим дополнительное ограничение, связанное с уступкой по второму критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения» вводим данные «С2», «?», «28,4». Результат на рис.4.5.
Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат: переменные x1, x2, x3 равны 10,76; 6,62; 1,11. Целевые функции равны, соответственно, 24,8; 28,4 и 6,93. Это окончательный ответ. Все дополнительные условия соблюдены.
Задание 4.1. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:
Уступка по первому критерию оптимизации d1=2.
Значение неизвестного параметра а взять равным номеру варианта.
Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.
Задание 4.2. Молочный комбинат, исследовав конъюнктуру местного рынка, решил выпускать новый вид йогурта, который был бы конкурентно способен. При этом необходимо разработать план организации производства для выпуска данного продукта. Основными затратами на разработку являются затраты на модернизацию оборудование х и затраты на научные исследования у. При исследовании установлено, что себестоимость единицы продукции при этом будет зависеть от затрат как F1(x, y) = 12 + ax + (31-а)y, а качество продукции как F2 = 6 + (31-а)x + аy. Ставится задача минимизировать себестоимость (цену) данного продукта и максимизировать качество выпускаемой продукции. Из двух целевых функций основной считается цена (себестоимость продукции). По фактору «цена» можно сделать уступку 3 денежные единицы. Решить задачу методом последовательных уступок и найти оптимальные значения факторов х и у, а также значения целевых функций, если на факторы наложены ограничения:
Значение неизвестного параметра а взять равным номеру варианта.
Отчет должен содержать математическую модель задачи, оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ, выводы, какие должны быть затраты на модернизацию оборудования и на научные исследования, какими при этом будет себестоимость и качество продукции.
Задание 4.3. Решить методом последовательных уступок двухкритериальную задачу, представленную математической моделью:
Уступка по первому критерию оптимизации d1 равна номеру варианта а.
Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.
Задание 4.4. Решить методом последовательных уступок трехкритериальную задачу, представленную математической моделью:
Значение неизвестного параметра а взять равным номеру варианта.
Уступки по первому и второму критерию оптимизации равны d1=6, d2=4.
Отчет должен содержать оптимальные значения переменных и всех целевых функций, полученных в результате расчета на ЭВМ.




Информация

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

Популярные новости

Статистика сайта



Rambler's Top100



 
Copyright © НеОфициальный сайт факультета ЭиП