Контрольная работа по "Методам оптимальных решений"

 

Федеральное агентство по образованию

Новосибирский государственный университет  экономики и управления – «НИНХ»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Номер группы: ФКП12А

 

Специальность: Экономика.Финансы  и Кредит.

 

Студент (ФИО) Тиунова Виктория Алексеевна

 

Кафедра Высшей математики

 

Учебная дисциплина: Методы оптимальных решений

 

Номер варианта работы:  28 вариант

 

Дата регистрации на кафедре:  «___» ________ 20  г.

 

Проверил: ФИО преподавателя

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(Год) 2013

 

 

 

	Вариант N 028			Задача 1
Информация по  фирме о  нормах затрат ресурсов  на  единицу выпускаемой продукции,
лимитах на эти ресурсы  и ценах  реализации готовой продукции представлена в таблице.
Наименование		Нормa затрат на		Обьем
ресурсов	Продукт A		Продукт B	ресурса
Сырье (кг)	2		1	202
Оборудование (ст.час.)	1		4	506
Трудоресурсы (чел.час.)	6		1	490
Цена реализации (руб.)	214		65
Требуется:
1. Составить модель расчета  оптимальной производственной программы  для  этой фирмы на
основе задачи линейного программирования.
2. Используя графический метод  решения этой модели, найти оптимальную  программу выпуска
продукции, максимизирующую ожидаемый объем продаж.
3. Сформировать задачу, двойственную  к задаче расчета оптимальной  производственной
программы и составить обе группы условий “дополняющей нежесткости”.
4. Подставив в условия “дополняющей  нежесткости” оптимальную программу  выпуска, найти
предельную эффективность имеющихся  у предприятия объемов ресурсов.
5. Выполнить проверку оптимальных  решений прямой и двойственной  задачи подстановкой
их в ограничения и целевые  функции.

 

Решение

1. Пусть  - количество продукта А, - количество продукта В. Тогда математическая модель задачи будет выглядеть следующим образом

F = 214x₁+65x₂ → max, при системе ограничений:

2x₁+x₂≤202 (1)

x₁+4x₂≤506 (2)

6x₁+x₂≤490 (3)

x₁≥0 (4)

x₂≥0 (5)

 

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

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию  задачи F = 214x₁+65x₂ → max.

Построим  прямую, отвечающую значению функции F = 0: F = 214x₁+65x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (214; 65). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений представляет собой многоугольник

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

2x₁+x₂=202

6x₁+x₂=490

Решив систему уравнений, получим: x₁ = 72, x₂ = 58

Откуда найдем максимальное значение целевой функции:

F(X) = 214*72 + 65*58 = 19178

 

3. Составляем двойственную задачу

2y₁+y₂+6y₃≥214

y₁+4y₂+y₃≥65

202y₁+506y₂+490y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

условия дополняющей нежесткости

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

       

        

Условия (1), (2) называются условиями  дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.

 

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

2*72 + 1*58 = 202 = 202

1-ое ограничение прямой задачи  выполняется как равенство. Это  означает, что 1-ый ресурс полностью  используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).

1*72 + 4*58 = 304 < 506

2-ое ограничение выполняется  как строгое неравенство, т.е.  ресурс 2-го вида израсходован  не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0

6*72 + 1*58 = 490 = 490

3-ое ограничение прямой задачи  выполняется как равенство. Это  означает, что 3-ый ресурс полностью  используется в оптимальном плане,  является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃>0).

С учетом найденных оценок, новая  система примет вид:

2y₁+6y₃≥214

y₁+y₃≥65

202y₁+490y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

 

Решая систему уравнений

2y₁+6y₃=214

y₁+y₃=65

получаем

y₁ = 44

y₃ = 21

Z(Y) = 202*44+490*21 = 19178

 

5. Проверка

F(X) = 214*72 + 65*58 = 19178

Z(Y) = 202*44+490*21 = 19178

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

 

 

	Вариант N 028			Задача 2
Учитывая данные  задания 1, исследовать динамику предельной эффективности сырья при
изменении его объема от  нуля до бесконечности при  сохранении других ресурсов в  прежних
объемах.
Требуется:
1. Рассмотреть модель расчета  оптимальной производственной программы  как задачу линейного
программирования с параметром, выражающим объем сырья.
2. Используя графический метод  решения прямой задачи при  увеличении параметра от нуля  до
бесконечности и условия  "дополняющей нежесткости", вычислить  убывающие значения
предельной эффективности и определить диапазоны их устойчивости.
3. Записать выявленную функцию  предельной эффективности сырья  в табличной форме и
построить ее график.

 

Решение

1. Модель расчета оптимальной производственной программы с параметром, выражающим объем сырья (С)

F = 214x₁+65x₂ → max, при системе ограничений:

2x₁+x₂≤С (1)

x₁+4x₂≤506 (2)

6x₁+x₂≤490 (3)

x₁≥0 (4)

x₂≥0 (5)

 

2. Используя графическое решение  задачи 1, рассмотрим поведение целевой  функции при изменении параметра  С от нуля до бесконечности.

Найдем параметр С, при котором  линия уровня будет проходить  через точку Е.

Координаты точки В

x₂=0

6x₁+x₂=490

x₁= 81,67

Е (0; 81,67)

Тогда

2x₁+x₂=С

С=2 x₁=163,33

Таким образом, в диапазоне значений параметра запаса сырья(0; 163,33) объем производства продукта А будет изменяться от 0 до 81,67. Продукт В производиться не будет. Так как цена реализации продукта А составляет 214 руб., то предельная эффективность 1 кг сырья на данном интервале составит 214/2=107 руб.

 

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

x₁+4x₂=506

6x₁+x₂=490

x₁=63,21

x₂= 110,7

К (63,21; 110,7)

Тогда

2x₁+x₂=С

С=2*63,21+1*110,7=237,13

Таким образом, в диапазоне значений параметра запаса сырья(163,33; 237,13) значение целевой функции будет изменяться от 81,67*214= 17476,67 до

214*63,21+65*110,7=20723,7

Предельная полезность 1 кг сырья  составит

(20723,7- 17476,67)/(237,13-163,33)=44 руб.

 

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

 

3. Запишем функцию предельной  эффективности

Запас сырья	Предельная полезность
0;163,33	107
163,33;237,13	44
237,13;	0

Строим график

График предельной эффективности  запасов сырья

 

 

	Вариант N 028				Задача 3
Необходимо доставить однородный груз от трех филиалов фирмы пяти потребителям:
		Филиал 1		Филиал 2	Филиал 3
Предложение филиалов (ед.):			126	10	98
			потр.1	потр.2	потр.3		потр.4	потр.5
Спрос потребителей (ед.):			68	68	82		16	110
Известна матрица затрат на доставку единицы груза от каждого поставщика потребителю (руб.).
			потр.1	потр.2	потр.3		потр.4	потр.5
Поставщик 1			10	11	9		6	8
Поставщик 2			15	16	13		11	14
Поставщик 3			14	12	11		11	12
1. Составить ЭММ расчета оптимального  плана перевозок.
2. Определить исходный опорный  план методом северо-западного  угла.
3. Найти оптимальный план перевозок  методом потенциалов и указать  соответствующие ему
минимальные транспортные затраты.

 

Решение

1. Пусть  - объем перевозок из i – го пункта в j-й. Тогда математическая модель задачи будет выглядеть следующим образом

 

2. Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 126 + 10 + 98 = 234

∑b = 68 + 68 + 82 + 16 + 110 = 344

Потребности больше запасов, поэтому  вводим фиктивного поставщика с объемом запасов 344-234=110 ед. и стоимостью доставки 0.

 

 

 

Построим первый опорный план транспортной задачи.

Потребности первого потребителя  равны 68 и меньше запасов первого  поставщика, удовлетворяем запрос первого  потребителя полностью. У первого  поставщика остается в запасе 126-68=58 ед. Их направляем второму потребителю. Запрос второго потребителя не удовлетворен на 10 ед., их направляет от второго поставщика и т.д.

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	68     10	58     11	-     9	-     6	-     8	126
A 2	-     15	10     16	-     13	-     11	-     14	10
A 3	-     14	-     12	82     11	16     11	-     12	98
A 4	-     0	-     0	-     0	-     0	110     0	110
Потребность	68	68	82	16	110