Контрольная работа по «Экономико-математическому моделированию»

Задача 1.

Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум веществ приведены в таблице.

Питательные вещества (витамины)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
		I	II
	9 8 12	3 1 1	1 2 6

Стоимость 1 кг корма I и II соответственно равна 4 и 6 ед.

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

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

 

Решение:

1. Пусть - количество корма 1-го вида, а - количество корма 2-го вида, которые необходимо включить в рацион, обеспечив при этом минимальную его стоимость.

Поскольку стоимость корма I и II соответственно составляет – 4  и 6  ед., то стоимость всего рациона можно записать следующим образом:

Тогда количество питательного вещества в кормах I и II составят .

Поскольку необходимые минимум вещества это 9, то ограничение по питательным веществам первого вида можно записать следующим образом:

Аналогично рассуждая относительно питательных веществ и , получим еще два ограничения:

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

Найти минимум целевой функции ,

при ограничениях

2. Строим множество допустимых решений. Для этого строим прямые , и :

	0	3
	9	0

 

	0	8
	4	0

 

	0	6
	2	1

 

 

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

Изображаем линию уровня целевой функции:

И вектор градиента, перпендикулярный линии уровня - .

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

Видно, что выход из области (минимум целевой функции) произойдет в точке пересечения прямых и - точка А.

5. Найдем координаты точки А – точка пересечения прямой и . Для этого решим систему уравнений:

 

6. Найдем минимум целевой функции, для этого подставим найденную точку в целевую функцию:

Стоимость рациона будет минимальной и составит 24 ед., если включить в рацион 2 ед. корма I и 3 ед. корма II.

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

Ответ: Стоимость рациона будет минимальной  и составит 24 ед., если включить в рацион 2 ед. корма I и 3 ед. корма II.

.

 

 

Задача 2.

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

Тип сырья	Нормы расхода сырья на одно изделие			Запасы сырья
	А	Б	В
I	1	2	1	430
II	3	0	2	460
III	1	4	0	420
Цена изделия	3	2	5	—

 

Требуется:

1. Сформулировать прямую оптимизационную задачу на максимум выручки от реализации готовой продукции, получить оптимальный  план выпуска продукции.
2. Сформулировать двойственную задачу и найти её оптимальный план с помощью теорем двойственности.
3. Пояснить нулевые значения переменных в оптимальном плане.
4. На основе свойств двойственных оценок и теорем двойственности:

-  проанализировать использование  ресурсов в оптимальном плане  исходной задачи;

- определить, как изменятся выручка от реализации продукции и план ее выпуска, если запас сырья I вида увеличить  на 5 ед., а II - уменьшить на 5 ед.;

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

Решение:

1. Составим ЭММ задачи.

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

Решаем задачу линейного программирования на ЭВМ с помощью табличного процессора MS Excel.

Для этого заполним в Exel следующую таблицу:

Тип сырья	Нормы расхода сырья на одно изделие			Ограничения		Запасы сырья
	А	Б	В
I	1	2	1		<=	430
II	3	0	2		<=	460
III	1	4	0		<=	420
Цена изделия	3	2	5
Количество	0	0	0
Целевая функция

 

Далее введем формулы для нахождения значении целевой функции:

=СУММПРОИЗВ(B7:D7;B6:D6)

И для ограничений:

=СУММПРОИЗВ(B3:D3;$B$7:$D$7)

=СУММПРОИЗВ(B4:D4;$B$7:$D$7)

=СУММПРОИЗВ(B5:D5;$B$7:$D$7)

И воспользовавшись надстройкой «Поиск решения» получим значения переменных оптимального плана выпуска изделий: Х*=(0; 100; 230). Целевая функция имеет максимальное для данных условий задачи значение f(X*)=1350

Следовательно, для получения максимальной выручки от реализации готовой продукции следует производить 100 изделий Б, 230 изделий В и не производить изделия А (x1*=0). Выпуск изделия А  невыгоден при данных условиях задачи.

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

 

Заполним симплекс-таблицу:

ШАГ 1		3	2	5	0	0	0
БАЗИС
	0	1	2	1	1	0	0	430
	0	3	0	2	0	1	0	460
	0	1	4	0	0	0	1	420
	0	-3	-2	-5	0	0	0
ШАГ 2
	0		2	0	1		0	200
	5		0	1	0		0	230
	0	1	4	0	0	0	1	420
	1150		-2	0	0		0
ШАГ 3
	2		1	0			0	100
	5		0	1	0		0	230
	0	2	0	0	-2	1	1	20
	1350	4	0	0	1	2	0

 

На первом шаге имеем следующее опорное решение:

Значение целевой функции: .

Поскольку на данном шаге в строке имеются отрицательные оценки, (решаем задачу на максимум) то решение не является оптимальным,  выбираем минимальное значение, оно соответствует переменной , следовательно ее будем вводить в базис. Определяем переменную вместо которой будем вводить . Для этого в столбце находим отношения (отношение находим только для неотрицательных значений третьего столбца) и выбираем из них минимальное, минимальное значение соответствует переменной . Таким образом выводим из базиса переменную . Переходим к новому опорному плану с помощью элементарных преобразований – ШАГ 2.

На данном шаге имеем следующее опорное решение:

Значение целевой функции: .

Аналогично определяем, что данный опорный план не является оптимальным, поскольку в строке оценок есть отрицательное значение  -2. Определяем какая из переменных вводится в базис, а какая выводится, в данном случае вводим вместо . Переходим к новому опорному плану с помощью элементарных преобразований – ШАГ 3.

На данном шаге имеем следующее опорное решение:

Значение целевой функции: .

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

Таким образом, убирая дополнительные переменные, получаем

 и  - решение соответствует решению полученному c помощью Exel.

2. Составим двойственную задачу. Обозначим двойственные оценки ресурсов I, II, III соответственно как y1, y2, y3. Целевой функцией двойственной задачи является общая стоимость используемых ресурсов в двойственных оценках, которая должна быть наименьшей. Число ограничений двойственной задачи соответствует числу переменных исходной задачи и равно 3. Математическая модель двойственной задачи имеет вид:

 

Z(Y) = 430y1+460y2+420y3→ min;

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

Подставим полученное решение исходной задачи в ограничения исходной задачи:

Т.к. последнее ограничение выполняется как строгое неравенство, то

Согласно второй теореме двойственности

(1у1* +3 у2* + 1у3* -3) ∙ х1* = 0;

(2у1* + 0у2* + 4у3* -2) ∙ х2* = 0;

(1у1* + 2у2* + 0у3* -5) ∙ х3* = 0;

х1* = 0, х2*  = 100, х3*  = 230 (из решения исходной задачи)

Следовательно

2у1* + 0у2* + 4у3* -2=0

1у1* + 2у2* + 0у3* -5=0

Так как y3*  = 0, то

2у1*  -2=0