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

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

 

ФГБОУ ВПО Уральский  государственный экономический  университет

ЦЕНТР ДИСТАЦИОННОГО ОБРАЗОВАНИЯ

 

 

 

 

 

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

По методу оптимальных решений на тему:

 

 

 

 

 

 

 

 

 

Преподаватель

Студент

Специальность: Экономика

Специализация:

Экономическая безопасность

Группа:

 

 

 

 

 

Екатеринбург

2012

 

Задача 1

решить графически.

 

max(min) F = 2x₁ + x₂

 

 

Задача 2

Для производства 4-х видов продукции  используется 3 вида сырья. Нормы расхода сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

Составим план выпуска продукции, обеспечивающий получение максимальной прибыли, используя симплексный  метод, а также построить двойственную задачу и решить ее симплекс-методом.

 

	Нормы расхода ресурсов на единичное  изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

 

Задача 3

Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из пред- приятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны a1, a2, a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

С =

 

 

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

 

	B1	B2	B3	B4
A1	5	7	3	5	100
A2	1	2	5	6	150
A3	3	4	1	2	50
	75	80	60	85

 

Задача 4

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

 

F=3x₁+2x₂ max,

2x₁+x₂ 5

-2x₁+3x₂ 10

x₁ 0, x₂ 0,

x₁, x₂ – целые

 

Задача 5

 

	Нормы расхода ресурсов на единичное  изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

 

Задача 1

решить графически.

max(min) F = 2x₁ + x₂

 

 

 

 

Принимаем:

       

 

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

 

Минимум будет в точке  А 

Найдем координаты точки А –  пересечения прямых:

= = =

 

= =

 

F_min = 2x₁ + x₂ = + 22/7 = 16/7 = 2,28

Минимум будет в точке C

Найдем координаты точки С –  пересечения прямых:

= = =

 

= = 

 

F_max = 2x₁ + x₂ = + 1 = 13

 

 

 

Задача 2

Для производства 4-х видов продукции  используется 3 вида сырья. Нормы расхода  сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

Составим план выпуска продукции, обеспечивающий получение максимальной прибыли, используя симплексный  метод, а также построить двойственную задачу и решить ее симплекс-методом.

 

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

Решение:

Составим математическую модель. Обозначим:

х₁ – выпуск изделия 1;

х₂ – выпуск изделия 2;

х₃ – выпуск изделия 3.

x₄ – выпуск изделия 4.

 

Запишем систему ограничений:

 

Общая ценность произведенных товаров  составляет:

F =

По экономическому содержанию переменные х₁, х₂, х₃, х₄ могут принимать только неотрицательные значения: х₁, х₂, х₃, х₄ 0

Запишем эту задачу в виде основной ЗЛП, для этого перейдем от системы  неравенств к равенствам, для этого  введем три дополнительные переменные:

 

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

Запишем преобразованную систему  уравнений в векторной форме:

x₁* P₁ + x₂* P₂ + x₃* P₃ + x₄* P₄ + x₅* P₅ + x₆* P₆ + x₇* P₇+ x₈* P₈

 

P₁= ; P₂= ; P₃= ; P₄= ; P₅= ; P₆= ; P₇= ; P₈= ;

P₉= .

Поскольку среди векторов Рj имеется четыре единичных вектора, то для дан- ной задачи можно записать опорный план Х=(0, 0, 0,0,35, 50, 100; 0;0) определяемый системой единичных векторов Р5, Р6, Р7, Р8, которые образуют базис трехмерного пространства.

Составляем симплексную  таблицу I итерации и подсчитываем значения

F₀,  z_j – c_j.

Проверяем исходный план на оптимальность:

F₀ = (C,P₀) = 0; z₁ = (C,P₁) = 0 ; z₂ = (C,P₂) = 0; z₃ = (C,P₃) = 0; z₄ = (C,P₄) = 0

z₁ – c₁ = 0 = ; z₂ – c₂ = 0 = ; z₃ – c₃ = 0 = ;

z₄ – c₄ = 0 =  .

Для векторов базиса z_i – c_i = 0 (j = 5,6,7,8).

                                                                                                                     Таблица I

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	35	6	3	1	8	1	0	0	0
2	P6	0	50	10	5	2	9	0	1	0	0
3	P7	0	100	4	6	15	10	0	0	1	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			0	-3,5	-7	-9	-11	0	0	0	0

 

Максимальное отрицательное  число  _j стоит в 5-ой строке столбца Р4. Следовательно, в базис введем вектор Р4. Определим вектор, подлежащий

исключению из базиса, для этого находим  ₀ min(b_i/a_ij) для a_i3>0

₀ min(35/8; 50/9; 100/10) = 35/8

 

Т.е. ограничивающим фактором для производства изделий 4 является имеющийся ресурс I вида. С учетом его наличия предприятие может изготовить 35/8 (4) изделия 4, при этом ресурс I вида будет полностью израсходован.

 

Следовательно, вектор Р5  подлежит исключению из базиса. Столбец вектора Р4  и 1-я строка являются направляющими.

 

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

Элементы этой строки получаются путем деления соответствующих  элементов таблицы 1 на разрешающий элемент (т.е. 8). При этом в столбец Сб записываем коэффициент С3=11, стоящий в столбце вводимого в базис вектора Р4.

                                                                                                                   Таблица II

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P4	11	35/8	3/4	3/8	1/8	1	1/8	0	0	0
2	P6	0	85/8	13/4	13/8	7/8	0	-9/8	1	0	0
3	P7	0	225/4	-7/2	9/4	55/4	0	-5/4	0	1	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			385/8	4,75	-23/8	-61/8	0	11/8	0	0	0