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

Задача.

Имеется 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