Контрольная работа по "Математике"

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной  переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий  переменной x1, так как это наибольший коэффициент по модулю.

3. Определение новой свободной  переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (16.67) и находится на пересечении  ведущего столбца и ведущей строки.

Базис	В	Х1	Х2	х3	х4	Х5	х6	Х7	min
х3	10	0,33	0,67	1	1,33	0,0667	0	0	30
х6	70	16,67	8,33	0	-8,33	-0,67	1	0	4,2
Х7	150	13,67	6,33	0	11,67	-0,27	0	1	10,98
F(X2)	140	-1,83	1,33	0	8,67	0,93	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть  симплексной таблицы.

Вместо переменной x6 в  план 2 войдет переменная x1

Строка, соответствующая  переменной x1 в плане 2, получена в  результате деления всех элементов  строки x6 плана 1 на разрешающий элемент  РЭ=16.67

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x1  плана 2 записываем нули.

Таким образом, в новом  плане 2 заполнены строка x1  и столбец x1 .

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

Представим расчет каждого  элемента в виде таблицы:

Базис	В	Х1	Х2	х3	х4	Х5	х6	Х7
Х-j	8,6	0	0,5	1	1,5	0,08	-0,02	0
Х1	4,2	1	0,5	0	-0,5	-0,04	0,06	0
х7	92,6	0	-0,5	0	18,5	0,28	-0,82	1
F(X2)	147,7	0	2,25	0	7,75	0,86	0,11	0

1. Проверка критерия оптимальности.

Среди значений индексной  строки нет отрицательных. Поэтому  эта таблица определяет оптимальный  план задачи.

Окончательный вариант симплекс-таблицы:

Базис	В	Х1	Х2	х3	х4	Х5	х6	Х7
х3	8,6	0	0,5	1	1,5	0,08	-0,02	0
Х1	4,2	1	0,5	0	-0,5	-0,04	0,06	0
Х7	92,6	0	-0,5	0	18,5	0,28	-0,82	1
F(X3)	147,7	0	2,25	0	7,75	0,86	0,11	0

 

Оптимальный план можно записать так:

x3 = 8.6

x1 = 4.2

F(X) = 6.5*4.2 + 14*8.6 = 147.7

Анализ оптимального плана.

В оптимальный план вошла  дополнительная переменная x7. Следовательно, при реализации такого плана имеются  недоиспользованные ресурсы 3-го вида в количестве 92.6

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

Значение 2.25> 0 в столбце x2 означает, что использование x2 - не выгодно.

Значение 0 в столбце x3 означает, что использование x3 - выгодно.

Значение 7.75> 0 в столбце x4 означает, что использование x4 - не выгодно.

Значение 0.86 в столбце x5 означает, что теневая цена (двойственная оценка) равна 0.86.

Значение 0.11 в столбце x6 означает, что теневая цена (двойственная оценка) равна 0.11.

Ответы на вопросы преподавателя:

1. По какому методу  пересчитываются симплекс-таблицы?

Используется правило  прямоугольника (метод жордановских преобразований).

2. Обязательно ли каждый  раз выбирать максимальное значение  из индексной строки?

Можно не выбирать, но это  может привести к зацикливанию алгоритма.

3. В индексной строке  в n-ом столбце нулевое значение. Что это означает?

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

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

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

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

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

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

Левая часть ограничений  определяет стоимость ресурсов в  теневых (альтернативных) ценах, затраченных  на xj.

5y1+20y2+15y3≥6.5

10y1+15y2+9y3≥8

15y1+10y2+4y3≥14

20y1+5y2+17y3≥10

150y1+170y2+190y3 → min

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

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

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

Из первой теоремы двойственности следует, что Y = C*A-1.

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

	15	5	0
A(a3, a1, a7) =	10	20	0
	4	15	1

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

	0:08	-0,02	0
D = A-1 =	-0:04	0:06	0
	0:28	-0:82	1

 

 

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A-1 =

	0,08	-0,02	0
(14, * 6.5,0) х	-0,04	0,06	0	= (0,86;0,11;0)
	0,28	-0,82	1

Оптимальный план двойственной задачи равен:

y1 = 0.86

y2 = 0.11

y3 = 0

Z(Y) = 150*0.86+170*0.11+190*0 = 147.7

Критерий оптимальности  полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых  выполняется равенство целевых  функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и  двойственной задач соответственно.

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

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

5*4.2 + 10*0 + 15*8.6 + 20*0 = 150 = 150

20*4.2 + 15*0 + 10*8.6 + 5*0 = 170 = 170

15*4.2 + 9*0 + 4*8.6 + 17*0 = 97.4 < 190

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

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

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

Неиспользованный экономический  резерв ресурса 3 составляет 92.6 (190-97.4).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений  в объекте моделирования (например, резерв ресурса можно продать  или сдать в аренду).

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

Обоснование эффективности  оптимального плана.

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

5*0.86 + 20*0.11 + 15*0 = 6.5 = 6.5

10*0.86 + 15*0.11 + 9*0 = 10.25 > 8

15*0.86 + 10*0.11 + 4*0 = 14 = 14

20*0.86 + 5*0.11 + 17*0 = 17.75 > 10

Анализ устойчивости оптимального плана.

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

Чувствительность решения  к изменению коэффициентов целевой  функции.

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

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

Допустимые диапазоны  изменения коэффициентов в целевой  функции определятся из соотношений:

3-ый параметр целевой  функции может изменяться в  пределах:

∆c3- = min [yk/d3k] для d3k>0.

∆c3+ = |max [yk/d3k]| для d3k<0.

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

Таким образом, 3-параметр может  быть уменьшен на 10.75 или увеличен на 5.5

Интервал изменения равен:

(c3 - ∆c3-; c3 + ∆c3+)

[14-10.75; 14+5.5] = [3.25;19.5]

Если значение c3 будет  лежать в данном интервале, то оптимальный  план не изменится.

1-ый параметр целевой  функции может изменяться в  пределах:

∆c1- = min [yk/d1k] для d1k>0.

∆c1+ = |max [yk/d1k]| для d1k<0.

Таким образом, 1-параметр может  быть уменьшен на 1.83 или увеличен на 21.5

Интервал изменения равен:

(c1 - ∆c1-; c1 + ∆c1+)

[6.5-1.83; 6.5+21.5] = [4.67;28]

Если значение c1 будет  лежать в данном интервале, то оптимальный  план не изменится.

Чувствительность решения  к изменению запасов сырья.

Из теоремы об оценках  известно, что колебание величины bi приводит к увеличению или уменьшению f(X).

Оно определяется величиной  yi в случае, когда при изменении величин bi значения переменных уi в оптимальном плане соответствующей двойственной задачи остаются неизменными.

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

Найдем интервалы устойчивости ресурсов.

1-ый запас может изменяться  в пределах:

∆b1- = min [xk/dk1] для dk1>0.

∆b1+ = |max [xk/dk1]| для dk1<0.

Таким образом, 1-ый запас  может быть уменьшен на 107.5 или увеличен на 105

Интервал изменения равен:

(b1 - ∆b1-; b1 + ∆b1+)

[150-107.5; 150+105] = [42.5;255]

2-ый запас может изменяться  в пределах:

∆b2- = min [xk/dk2] для dk2>0.

∆b2+ = |max [xk/dk2]| для dk2<0.