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

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

Уральский государственный экономический  университет

 

 

 

 

 

 

 

 

 

 

 

 

 

Контрольная работа № 1

по «Методам оптимальных решений»

 

 

 

 

 

 

 

 

                                                     Исполнитель: 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2012 г

Задача № 1

 

    Вариант 1:

Найти наибольшее и наименьшее значение функции z = x² – y² 

в круге x² + y² ≤ 4.

Решение:

Применяем теорему Ферма.  Если точка  - точка экстремума      дифференцируемой функции  , тогда частные производные

     и     .

1) Найдем частные производные:

                         (0;0) – точка экстремума или критическая точка.

    

2)  Найдем критические точки  функции на границе области:

              

, подставляем в уравнение   ,   ,

,    ,   

3) Найдем значение функции  в критических точках внутри области:

    

4)  Найдем значение функции  на границе:

    ,       ,        ;

     Найдем значение функции  на концах отрезка   :

    .

5)  Выбираем из этих чисел наибольшее и наименьшее:

    ,    

 

 

 

 

 

 

Задача № 5

 

    Фабрика выпускает продукцию  двух видов: П₁ и П₂. Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта – А, В, С. Максимально возможные суточные запасы этих продуктов составляют М, N и К т соответственно. Расходы сырья А, В, С на 1 тыс. изделий П₁ и П₂ приведены в табл. 1.1.

 

Таблица 1.1

Исходный продукт	Расход исходных продуктов на 1 тыс. изделий (т)		Максимально возможный запас (т)
	П1	П2
А	1	2	М
В	2	1	N
С	1	0,8	К

 

    Изучение рынка сбыта  показало, что суточный спрос  на изделия П₂ никогда не превышает спроса изделия П₁ более чем на 1 тыс. шт. Кроме того, установлено, что спрос на изделия П₂ никогда не превышает 2 тыс. шт. в сутки.

    Оптовые цены 1 тыс. шт. изделий П₁ равны 3 тыс. руб., 1 тыс. шт. П₂ – 2 тыс. руб.

    Какое количество изделий  (в тыс. шт.) каждого вида должна  производить фабрика, чтобы доход  от реализации продукции был  максимальным?

    Построить математическую  модель данной операции и решить оптимизационную задачу графическим и симплекс-методом.

Вариант 1: М=6, N=8, К=5.

Решение:

Исходный продукт	Расход исходных продуктов на 1 тыс. изделий (т)		Максимально возможный запас (т)
	П1	П2
А	1	2	6
В	2	1	8
С	1	0,8	5
Прибыль руб/ед.	3	2	-

 

Обозначим объем производства П₁  через х_1,   продукцию     П₂    через х_{2 .}   С учетом этих обозначений математическая модель     задачи имеет вид:

1) чтобы доход от реализации  был максимальным:

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

,    ,    ,   ,    

2) приводим задачу к  каноническому виду, введя дополнительные  переменные:   ,    ,     .

max ,

,         ,        .

 

Задач обладает опорным  планом:    (0;0;0;6;8;5)

,

 

Задачу можно решить симплекс-методом (данные переводим в таблицу)

 

 

№ симп.	i	ба зис			3	2	0	0		0
											Q
	1		0	6	1	2	1	0	0		6
I	2		0	8	2	1	0	1	0		4min
	3		0	5	1	0,8	0	0	1		5
	4			0	-3	-2	0	0	0

 

 

 

 

Продолжение

 

№ симп.	i	ба зис			3	2	0	0	0
										Q
	1		0	2	0		1	-	0	min
II	2		3	4	1		0		0	8
	3		0	1	0		0	-	1
	4			12	0	-	0		0

 

Продолжение

 

№ симп.	i	ба зис			3	2	0	0	0
										Q
	1		2		0	1			0
III	2		3		1	0			1
	3		0		0	-1			0
	4			12	0	0			3

 

          max

3) Графический способ решения задачи   max при ограничениях

,    ,    .

I      ,      (0;3) (6;0);

II     ,       (0;8) (4;0);

III    ,    (1;5) (5;0);

В    - точка max,   .

                             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача № 6

 

    Графическим способом  решить ЗЛП

Вариант 1:

max (2х₁ + х₂),  при  х₁ – х₂ ≤ 2,   х₁ + 3х₂ ≥ 3,   7х₁ – х₂ ≥ 2,    х₁,₂ ≥ 0.

Решение:

I    ,  ,  (0;-2)  (2;0);

II   ,  ,  (0;1)  (3;0);

III  ,  ,  (0;-2)  ( ;0).

 

                 

                               

          

B , ,    .                               

 

 

 

 

 

Задача № 7

 

    Решить следующую ЗЛП:

 

Вариант 1:  max (4х₁ + х₂ +2х₃ + 3х₄);         х₁ + 2х₂ + 3х₃ – х₅ + х₇ = 50;                                        -зх₂ + х₃ + х₄ + 2х₅ + 4х₇ = 10;       4х₂ + х₅ +х₆ – 1/2 х₇ = 24,

х₁, y₂ не ограничены в знаке.

   Найти решение задачи, двойственной к ЗЛП.

Решение:

        ,  

        (1  2  3  0  -1  0  1)

              ( 0-3  1  1   2  0  4)               

               (0  4  0 0  1  1  -1/2),

 

        (1  0  0)

               (2 -3  4)

               (3  1  0)

               (0  1  0)

               (-1  2 1)  

               (0  0  1)

               (1  4 -1/2).

Двойственная задача:     ,       ,    ,     ,    

,     ,       .

Решение исходной задачи ищем симплексным  методом:

            I

i	ба зис			4	1	2	3	0	0	0
											Q
1		4	50	1	2	3	0	-1	0	1	50
2		3	10	0	-3	1	1	2	0	4	2,5 min
3		0	24	0	4	0	0	1	1
4			230	0	-2	13	0	2	0	16

           II

i	ба зис			4	1	2	3	0	0	0
											Q
1		4		1					0	0
2		0	2,5	0					0	1
3		0		0					1	0
4			190	0	10	9	-4	-6	0	0

 

          III

i	ба зис			4	1	2	3	0	0	0
											Q
1		4		1	0					0
2		0		0	0					1
3		1		0	1					0
4				0	0					0

 

        IV

i	ба зис			4	1	2	3	0	0	0
											Q
1		2			0	1				0
2		0			0	0				1
3		1			1	0				0
4					0	0		-	-	0

 

При этом плане   max .

 

Задача № 9

 

    Решить транспортную  задачу. С – матрица стоимостей. Прочерк означает невозможность перевозки по данному маршруту.

a_i – запасы поставщиков, b_j – заявка потребителей.

 

Вариант 1:

          6    5    4   -

        

С =    8    8    2   6      a₁ = 500; a₂ = 300; a₃ = 100

 

          9  -     7    6

 

b₁ = 400;  b₂ = 200; b₃ = 150; b₄ = 250.

 

Решение:

 

постав- щики	Потребители
					запасы
	6	5	4	-	500
	8	8	2	6	300
	9	-	7	6	100
	400	200	150	250

 

 

 

Если суммарные запасы и потребности  совпадают  , то

называется закрытой моделью.

,      .

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

 

постав- щики	Потребители
					запасы
	(-) (400)	5 (+) (100)	4	М	500
	8	8 (-) (100)	2 (150)	6 (+) (50)	300
	9	М	7	6 (100)	100
	0 (+) (100)	0	0	0 (-) (100)	100
	400	200	150	250	1000

 

 

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

Проверим оптимальность полученного  плана перевозок через потенциалы (m + n - 1), 4 + 4 - 7 = 7 – число занятых клеток. Для каждой занятой клетки сумма потенциалов должна быть равной стоимости единицы перевозки.

                            Пусть   ,  ,  ,   ,

                                  то  ,   ,  ,   .

 

,   ,    ,

,     ,     ,

,     ,   .

 

 

 

Наличие отрицательных оценок показывает неоптимальность плана.

 

   0    0      5  М-3

         -1   0       0   0

          7   М-8   5  0

        -3     -2     4  0

 

Чтобы улучшить неоптимальный план перевозок, выбираем клетку (4;1) с отрицательной  оценкой, с наибольшей по абсолютной цене.  Для клетки  (4;1) строим замкнутую линию, начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках.

постав- щики	Потребители
					запасы
	6 (300)	5 (200)	4	М	500
	8	8 (0)	2 (150)	6 (150)	300
	9	М	7	6 (100)	100
	0 (100)	0	0	0 (0)	100
	400	200	150	250	1000

 

Проверим оптимальность плана:

                            Пусть   ,  ,  ,   ,

                                  то  ,   ,  ,   .

 

,     ,     ,       ,

,   ,  ,

,    ,    ,

.

        План улучшен на 300 ед.    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача № 10

 

    По плану производства  продукции предприятию необходимо  изготовить k изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Стало известно, что при производстве х₁ изделий первым способом затраты равны:    mх₁ + х₁² руб.

    При изготовлении х2  изделий вторым способом они  составляют:

nх₂ + х₂² руб.

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

Вариант 1: m = 4,  n = 8, k = 180.

Решение:

Математическая постановка задачи состоит в определении минимального значения функции  ,    при условиях  , .

Сначала найдем решение задачи, используя  геометрическую интерпретацию. Областью допустимых  значений исходной задачи является отрезок прямой АВ, а линии уровня окружности с центром в точке Е (-2;-4).

Минимальное значение целевой функции  в точке Д, чтобы найти координаты точки Д воспользуемся тем, что угловой  коэффициент в окружности  . Точка Д совпадает с угловым коэффициентом прямой линии ,   К= - 1.

                                 

 

Найдем производные от , , ,  .

,  ,           отсюда

,    ,  ,  ,  то   .

,        .

Если предприятие изготовит 1 способом 91 изд. , 2 способом 89 изд., то общие затраты будут минимальны и составят  17286 руб.

Решаем задачу методом Лагранжа:

Составим функцию Лагранжа ,

Найдем частные производные  от , , :

,   ;

  ,   ;

,   ;

,     = 91,   = 89.

Д (91;89) – точка экстремума является подозрительной.

,       ,

4 = 364,       = 91,    = 89.

 

В данной точке  (91;89) – функция  имеет минимальное значение.