Контрольная работа по "Теории вероятности и математической статистике". 9

Задача.

Имеется 150 л жидкости А и 150 л жидкости Б. Для получения одной бутыли смеси 1 нужно взять 2 л жидкости А и 1 л жидкости Б, а для получения одной бутыли смеси 2 нужно взять соответственно 1 л жидкости А и 4 - жидкости Б. Смесь 1 продается по цене 2 ден. единицы, а смесь 2 — 3 ден. единицы за одну бутыль. Сколько нужно приготовить бутылей каждой смеси, чтобы общая их стоимость была наибольшей, при условии, что число бутылей со смесью 2 не менее числа бутылей со смесью 1.

Задания:1)Сформулировать экономико-математическую модель исходной эконом задачи 2) Решить полученную задачу линейного программирования симплексным методом 3) Составить двойственную задачу и найти ее решение.

Решение.

1)

Составим экономико-математическую модель задачи.

Введем обозначения. Пусть x₁ – план приготовления бутылей со смесью 1.

x₂ –– план приготовления бутылей со смесью 2.

Тогда у нас будут ограничения по каждому виду жидкостей

Жидкость A: 2x₁ +x₂   ≤150

Жидкость Б:  x₁+4x₂≤150

Кроме того, по условию задачи x₁≤ x₂

Планируемая прибыль будет:

F(x)= 2x₁ + 3x₂ 

 Переменные x₁ , x₂, по смыслу задачи должны быть неотрицательны.

Итак, получили задачу  линейного программирования

 

max 2x₁ + 3x₂ 

2x₁ +x₂   ≤150

x₁+4x₂≤150

x₁-x₂≤0

x₁≥0,x₂≥0

2)

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

Определим максимальное значение целевой функции F(X) = 2x₁ + 3x₂ при следующих условиях-ограничений.

2x₁ + x₂≤150

x₁ + 4x₂≤150

x₁ - x₂≤0

Для построения первого  опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅. 

2x₁ + 1x₂ + 1x₃ + 0x₄ + 0x₅ = 150

1x₁ + 4x₂ + 0x₃ + 1x₄ + 0x₅ = 150

1x₁-1x₂ + 0x₃ + 0x₄ + 1x₅ = 0

Матрица коэффициентов A = a(ij) этой системы уравнений имеет  вид:

 

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

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

Решим систему уравнений относительно базисных переменных:

x₃, x₄, x₅,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,150,150,0)

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

 

Базис	B	x1	x2	x3	x4	x5
x3	150	2	1	1	0	0
x4	150	1	4	0	1	0
x5	0	1	-1	0	0	1
F(X0)	0	-2	-3	0	0	0

Переходим к основному алгоритму  симплекс-метода.

Итерация №0.

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

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

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

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

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

min (150 : 1 , 150 : 4 , - ) = 37¹/₂

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

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

 

Базис	B	x1	x2	x3	x4	x5	min
x3	150	2	1	1	0	0	150
x4	150	1	4	0	1	0	371/2
x5	0	1	-1	0	0	1	-
F(X1)	0	-2	-3	0	0	0	0

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

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

Вместо переменной x₄ в план 1 войдет переменная x₂.

Строка, соответствующая  переменной x₂ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=4

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

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

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

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

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

 

B	x 1	x 2	x 3	x 4	x 5
150-(150 • 1):4	2-(1 • 1):4	1-(4 • 1):4	1-(0 • 1):4	0-(1 • 1):4	0-(0 • 1):4
150 : 4	1 : 4	4 : 4	0 : 4	1 : 4	0 : 4
0-(150 • -1):4	1-(1 • -1):4	-1-(4 • -1):4	0-(0 • -1):4	0-(1 • -1):4	1-(0 • -1):4
0-(150 • -3):4	-2-(1 • -3):4	-3-(4 • -3):4	0-(0 • -3):4	0-(1 • -3):4	0-(0 • -3):4

 

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4	x5
x3	1121/2	13/4	0	1	-1/4	0
x2	371/2	1/4	1	0	1/4	0
x5	371/2	11/4	0	0	1/4	1
F(X1)	1121/2	-11/4	0	0	3/4	0

Итерация №1.

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

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

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

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

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

min (112¹/₂ : 1³/₄ , 37¹/₂ : ¹/₄ , 37¹/₂ : 1¹/₄ ) = 30

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

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

 

Базис	B	x1	x2	x3	x4	x5	min
x3	1121/2	13/4	0	1	-1/4	0	642/7
x2	371/2	1/4	1	0	1/4	0	150
x5	371/2	11/4	0	0	1/4	1	30
F(X2)	1121/2	-11/4	0	0	3/4	0	0

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

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

Вместо переменной x₅ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=1¹/₄

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

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

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

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

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

 

B	x 1	x 2	x 3	x 4	x 5
1121/2-(371/2 • 13/4):11/4	13/4-(11/4 • 13/4):11/4	0-(0 • 13/4):11/4	1-(0 • 13/4):11/4	-1/4-(1/4 • 13/4):11/4	0-(1 • 13/4):11/4
371/2-(371/2 • 1/4):11/4	1/4-(11/4 • 1/4):11/4	1-(0 • 1/4):11/4	0-(0 • 1/4):11/4	1/4-(1/4 • 1/4):11/4	0-(1 • 1/4):11/4
371/2 : 11/4	11/4 : 11/4	0 : 11/4	0 : 11/4	1/4 : 11/4	1 : 11/4
1121/2-(371/2 • -11/4):11/4	-11/4-(11/4 • -11/4):11/4	0-(0 • -11/4):11/4	0-(0 • -11/4):11/4	3/4-(1/4 • -11/4):11/4	0-(1 • -11/4):11/4

 

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4	x5
x3	60	0	0	1	-3/5	-12/5
x2	30	0	1	0	1/5	-1/5
x1	30	1	0	0	1/5	4/5
F(X2)	150	0	0	0	1	1

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

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

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

 

Базис	B	x1	x2	x3	x4	x5
x3	60	0	0	1	-3/5	-12/5
x2	30	0	1	0	1/5	-1/5
x1	30	1	0	0	1/5	4/5
F(X3)	150	0	0	0	1	1

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

x₂ = 30

x₁ = 30

F(X) = 3•30 + 2•30 = 150

 

3)

 

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

2y₁ + y₂ + y₃≥2

y₁ + 4y₂ - y₃≥3

150y₁ + 150y₂ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

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

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

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

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

 

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

 

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

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

 

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

y₁ = 0

y₂ = 1

y₃ = 1

Z(Y) = 150*0+150*1+0*1 = 150

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

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

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

2*30 + 1*30  = 90 < 150

1*30 + 4*30  = 150 = 150

1*30 + -1*30  = 0 = 0

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

Неиспользованный экономический  резерв жидкости А составляет 60 (150-90).

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

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

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

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

2*0 + 1*1 + 1*1  = 2 = 2

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

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

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