ЗАДАНИЕ 3 Тема "Игровые модели теории игр 1 страница

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра ИС и ПМ

ПОИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Методические указания к выполнению

расчетно-графического задания

для студентов очной формы обучения

по направлению подготовки 080800.62“Прикладная информатика ”.

Доцент кафедры ИС и ПМ

Яретенко Н.И.

Мурманск

2012 г.

Введение

Расчетно-графическое задание предназначено для студентов очной формы обучения по направлению подготовки 080800.62“Прикладная информатика ”, изучающих курс "Прикладные методы оптимизации" и включает материал по следующим темам:

Линейное программирование. Двойственность в задачах линейного программирования.

Транспортные задачи.

Игровые модели теории игр в задачах принятия решений.

Динамическое программирование.

Теория систем массового обслуживания.

Целочисленное программирование.

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

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

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

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

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

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

Задачи 1.1., 2.1. должны быть решены “ручным” способом. Остальные задачи можно решать, как ручным способом, так и на компьютере с использование пакета Excel.

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

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

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

ЗАДАНИЕ 1 Тема «Линейное программирование»

Задача 1.1

На предприятии имеется возможность выпускать nвидов продукции П_i (i = 1, n).При ее изготовлении используются ресурсы Р₁, Р₂и Р₃.Размеры прямых затрат ресурсов ограничены соответственно величинами b₁, b₂ и b₃. Расход j-го ресурса (i = 1, 3) на единицу продукции i-го вида составляет a_ijед. Цена единицы продукции i-го вида равна с_j ден. ед. Требуется:

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

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

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

4. указать наиболее дефицитный и недефицитный (избыточный) ресурс, если он имеется;

5. составить матрицу взаимозаменяемости ресурсов;

6. с помощью двойственных оценок у _i * обосновать эффективность оптимального плана, сопоставив оценку израсходованных ресурсов j_min и максимальный доход Z_max от реализации готовой продукции по всему оптимальному плану и по каждому виду продукции отдельно;

7. найти устойчивость параметров Pi.

8. установить, целесообразно ли выпускать новую продукцию П_l, на единицу которой ресурсы Р₁, Р₂и Р₃расходуются в количестве а_1l, а_2lи а_3l, а цена единицы готовой продукции составляет р_l.

9. Установить, выгодно ли покупать Dbk единиц k ресурса по цене ck.

Необходимые числовые данные приведены в табл. 1.1.

Задача 1.2

Составить диету, включающую белки, жиры и углеводы в количестве не менее b_i (i = 1, 3). Для составления смеси можно использовать три вида продуктов М_j (j = 1, 3), содержащих белки, жиры и углеводы в количестве a_ij. Цена продуктов c_j. Необходимо определить такой набор продуктов, который обеспечил бы необходимое содержание питательных веществ, и полная стоимость его при этом была бы наименьшей. Требуется:

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

2. симплекс-методом решить двойственную задачу.

Необходимые числовые данные приведены в табл. 1.2.

ЗАДАНИЕ 2 Тема «Транспортная задача»

Задача 2.1

В пунктах D_i (i = 1, 3) производится однородная продукция в количестве а_i ед. Себестоимость единицы продукции в i-м пункте равна s_i. Готовая продукция поставляется в пункты В_j, (j = 1, 4), потребности которых составляют b_jед. Стоимость перевозки единицы продукции из пункта D_i в пункт В_j, задана матрицей c_ij (i = 1, 3; j = 1,4). Требуется:

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

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

3. вычислить суммарные затраты Z_min;

4. указать в какие пункты развозится продукция от поставщиков.

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

Необходимые числовые данные приведены в табл. 2.1.

Задача 2.2

На заводах № 1, 2 и 3 производится однородная продукция в количестве а₁ а₂ и а₃. При этом затраты на производство единицы продукции на заводах составляют s₁ s₂ и s₃ ден. ед. Четырем потребителям требуется соответственно b₁, b₂, b₃ и b₄ единиц продукции. Расходы с_ij по перевозке единицы продукции с i-го завода j-му потребителю известны. Для полного удовлетворения потребностей потребителей необходимо увеличить выпуск продукции. При этом возможны следующие варианты:

1) увеличить производство продукции на заводе № 1 с дополнительными затратами на единицу продукции, равными Dc₁;

2) увеличить производство продукции на заводе № 2 с дополнительными затратами на единицу продукции, равными Dc₂,

3) наладить выпуск продукции на заводе № 4 с затратами на производство единицы продукции, равными c₄, и расходами по перевозке единицы продукции, равными соответственно c₄₁, c₄₂, c₄₃ и c₄₄. Требуется:

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

2. определить минимальные совокупные затраты на производство продукции и доставку ее потребителям по оптимальному плану расширения выпуска продукции.

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

Необходимые числовые данные приведены в табл. 2.2.

Задача 2.3

В пунктах D_i (i = 1, 3) производится однородная продукция в количестве а_i ед. Готовая продукция поставляется в пункты В_j, (j = 1, 4), потребности которых составляют b_jед. Стоимость перевозки единицы продукции из пункта D_i в пункт В_j, задана матрицей c_ij (i = 1, 5; j = 1,4). Ограничения на пропускную способность заданы матрицей d_ij. Требуется:

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

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

3. вычислить суммарные затраты Z_min;

4. указать в какие пункты развозится продукция от поставщиков.

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

Необходимые числовые данные приведены в табл. 2.3.

Задача 2.4

Студенческие отряды СО-1, СО-2 и СО-3 численностью а₁, а₂, и а₃ человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П₁, П₂, П₃ и П₄необходимо выделить соответственно b₁, b₂, b₃ и b₄ человек. Производительность труда студентов зависит от урожайности картофеля, а также от численности отряда и характеризуется для указанных отрядов и полей элементами матрицы p_ij (в центнерах на человека за рабочий день). Требуется:

1) распределить студентов по полям так, чтобы за рабочий день было убрано максимально возможное количество картофеля;

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

Необходимые числовые данные приведены в табл. 2.4.

ЗАДАНИЕ 3 Тема "Игровые модели теории игр

в задачах принятия решений»

Задача 3.1

Предприятие имеет возможность самостоятельно планировать объемы выпуска сезонной продукции А₁, А₂, А₃. Не проданная в течение сезона продукция позже реализуется по сниженной цене. Данные о себестоимости продукции, отпускных ценах и объемах реализации в зависимости от уровня спроса приведены в таблице:

Вид продукции	Себестоимость	Цена единицы продукции	Объем реализации при уровне спроса
		в течение сезона	после уценки
А1	d1	p1	q1	a1	b1	c1
А2	d2	p2	q2	a2	b2	c2
А3	d3	p3	q3	a3	b3	c3

Требуется:

1) придать описанной ситуации игровую схему, указать допустимые стратегии сторон, составить платежную матрицу.

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

(a) При условии, что вероятности известны.

(b) При условии, что вероятности того или иного спроса одинаковы.

(c) При условии, что про вероятности неопределенны.

Указание1. Для уменьшения размерности платежной матрицы считать, что одновременно на все три вида продукции уровень спроса одинаков: повышенный, средний или пониженный.

Указание2. Использовать критерии Байеса(вероятности равны 0,25, 0,4, 0,35 соответственно), Лапласа, Вальда, Сэвиджа, Гурвица (значение параметра g в критерии Гурвица равно 0,6).

Числовые данные приведены в табл. 3.1.

ЗАДАНИЕ 4 Тема "Динамическое программирование"

Задача 4.1

Выделены денежные средства S₀=100 для вложения в инвестиционные проекты. По каждому проекту известен возможный прирост f_i(x) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы. Требуется:

1) распределить средства S₀ между проектами так, чтобы суммарный прирост прибыли на всех четырех проектах достиг максимальной величины;

Необходимые числовые данные приведены в табл. 4.1.

Задача 4.2

В начале планового периода продолжительностью 6 лет имеется оборудование, возраст которого t. Оборудование не должно быть старше 6 лет. Известны: стоимость r(t) продукции, произведенной в течение года с помощью этого оборудования; ежегодные расходы u(t), связанные с эксплуатацией оборудования; его остаточная стоимость s; стоимость p нового оборудования, включающая расходы, связанные с установкой, наладкой и запуском оборудования. Требуется:

1) составить матрицу максимальных прибылей за 6 лет;

2) сформировать по матрице максимальных прибылей оптимальные стратегии замены оборудования возрастов t и t₁ лет в плановом периоде продолжительностью 6 и N лет.

Необходимые данные приведены в табл. 4.2

ЗАДАНИЕ 5Тема «Системы массового обслуживания"

Задача 5.1

Требуется привести характеристики системы массового обслуживания с отказами (k>N) или неограниченной длиной очереди (k<N). В таблице 6.1 приведены необходимы данные:

· l – параметр потока;

· m – интенсивность обслуживания;

· к – число требований;

· N – число узлов;

ЗАДАНИЕ 6Тема «целочисленное программирование»

Задача 6.1

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

Сформулированная задача - задача ЦП. Пусть х_ij = 1, если путешественник переезжает из i -ого города в j-ый и х_ij = 0, если это не так.

Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.

Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u₁ = 0, u_n+1 = n. Для того, чтобы избежать замкнутых путель, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x_ij и переменные u_i. (u_i целые неотрицательные числа).

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

Необходимые данные приведены ниже.

Задача 6.2

Решить задачу методом ветвей и границ.

Данные, необходимы для решения, приведены ниже.
Приложение