Контрольная работа по "ТВиМС и линейное программирование"

Задача 1

 

Из перетасованной колоды (36 карт) последовательно извлекаются 3 карты. Какова вероятность события, что эти 3 карты:

1. 6 бубей, 7 червей, дама пик в заданном порядке?

 

Решение:

Используем  классическое определение вероятности  .

где m - число исходов, благоприятствующих рассматриваемому событию;

n - общее число исходов.

 

Число способов извлечь 3 карты из колоды в 36 карт: .

Число способов извлечь 3 карты в заданном порядке: сначала извлекаем 6 бубей – это можно сделать единственным способом (так как такая карта в колоде одна), затем извлекаем 7 червей, также единственным способом и, наконец, извлекаем даму пик единственным способом .

Искомая вероятность:

Ответ: 0,00014.

 

 

 

                                                                    Задача2

Из изучаемой налоговыми органами обширной группы населения  было случайным образом отобрано 10 человек и собраны сведения об их доходах за истекший год в тыс. рублей: х₁, х₂,..., х₁₀. Найти выборочное среднее, выборочную дисперсию, исправленную выборочную дисперсию. Считая распределение доходов в группе нормальным и используя в качестве его параметров выборочное среднее и исправленную выборочную дисперсию, определить, какой процент группы имеет годовой доход, превышающий а тыс. рублей.

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

а

             

100

90

110

130

90

100

110

140

120

110

120

                      

Решение:

Так как в выборке  есть повторяющиеся значения, то её удобно задать таблицей частот значений :

Доход за истекший год, , тыс.руб.	Частота,
90	2	-20	400
100	2	-10	100
110	3	0	0
120	1	10	100
130	1	20	400
140	1	30	900
Итого:	10

 

Выборочное среднее:

.

Выборочная дисперсия:

Исправленная выборочная дисперсия:

Исправленное среднее квадратическое отклонение: .

Так как считаем распределение  доходов в группе нормальным то процент  группы, которая имеет годовой  доход, превышающий 120 тыс. рублей, вычисляется последующей формуле:

Значение функции Лапласа находим по таблице.

Таким образом, 27% группы имеет годовой доход, превышающий 120 тыс. рублей.

 

 

                                                      Задача3

 

Во второй тур президентских  выборов вышли два кандидата: А и В. Накануне второго в результате проведённого опроса лиц, желающих проголосовать за одного из двух кандидатов, было получено, что 51 процент опрошенных проголосует за кандидата А и 49- за кандидата В. Какова вероятность для каждого из кандидатов быть избранным, если для опроса использовалась репрезентативная выборка объёмом 2000 человек?

 

Решение:

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

Найдем вероятность  победы кандидата А, то есть вероятность того, что за него проголосуют Х человек и это составит более 50% (то есть более 1000 человек):

Здесь Ф – функция  Лапласа; n=2000;  p=0,51;  q=1- p = 0,49.

Значение функции Лапласа нашли по таблице.

Вероятность победы кандидата  В можно найти аналогично:

n=2000;  p=0,49;  q=1- p = 0,51.

Ответ: вероятность победы кандидата А составляет 81,33%; вероятность победы кандидата В 18,67%.

 

 

                                      Задача4

Желая установить цену на товар, обеспечивающую максимальную прибыль, магазин в течение 5 рабочих дней недели продавал получаемые от поставщика изделия с наценкой соответственно 1, 2, 3, 4 и 5 у.е. Количество единиц проданного товара в каждый из 5 дней приведено в таблице по вариантам. Методом наименьших квадратов получить уравнение квадратичной регрессии прибыли на наценку У= , где Х- наценка, а У- прибыль, определяемая как произведение наценки на количество единиц проданного товара. С помощью уравнения определить наценку, дающую максимальную прибыль.

 

На-           ценка  № варианта	1	2	3	4	5
11	95	75	55	25	5

                                                    

Решение:

Для нахождения коэффициентов уравнения квадратичной регрессии У= методом наименьших квадратов используем формулы:

Для составления этой системы уравнений  заполняем расчетную таблицу:

i
1	1	95	1	1	1	95	95
2	2	75	4	8	16	150	300
3	3	55	9	27	81	165	495
4	4	25	16	64	256	100	400
5	5	5	25	125	625	25	125
	15	255	55	225	979	535	1415

 

 

Решим данную систему уравнений  по формулам Крамера.

; ;

Получаем уравнение регрессии:

Это уравнение задает параболу, ветви которой направлены вниз.

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

.

Ответ: уравнение регрессии ; наценка, дающая максимальную прибыль .

 

 

 

Задача5

 

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

 

Производящие отрасли	Потребляющие отрасли			Конечная продукция
	I	II	III
I
II
III

 

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

 

№ вар.

а11

а12

а13

а21

а22

а23

а31

а32

а33

y1

y2

y3

           

11

0,2

0,0

0,2

0,3

0,2

0,1

0,2

0,0

0,1

110

90

190

                                    

Решение:

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

Матрица коэффициентов косвенных затрат 1-го порядка:

Матрица коэффициентов  косвенных затрат 2-го порядка:

Матрица коэффициентов полных материальных затрат приближенно равна:

 

Рассчитаем плановые объемы валовой  продукции:

 

Рассчитаем межотраслевые поставки:

, где X_j - валовый продукт j отрасли, а a_ij - прямые затраты.

Ответ: плановые объемы валовой продукции ; межотраслевые поставки .

 

 

                                             Задача6

 

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

 

Фермы	Заводы		Урожай, т
	1	2
1
2
3
Спрос, т

 

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

№ вар.	c11	c12	c21	c22	c31	c32	а1	а2	а3	B1	b2
11	10	15	12	12	18	9	2000	3000	1000	2750	3250

                                

 

Решение:

1. Проверим необходимое  и достаточное условие разрешимости задачи.

 

 

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

 

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

Берем в таблице 1 клетку с наименьшим показателем стоимости  перевозок. В исходной таблице наименьшая стоимость равна 9 и отвечает клетке (3; 2). В эту клетку дадим максимально возможную поставку. Соответствующая ферма 3 располагает 1000 тоннами овощей, а спрос завода 2 составляет 3250 тонн.  Значит, размер максимально возможной поставки равен 1000 тонн. Неудовлетворенный спрос завода 2: 3250 – 1000 = 2250 единиц. Ферма 3 более овощами не располагает (из таблицы вычеркивается соответствующая строка):

 

 

 

 

 

 

	1		2		ai
1	10		15		2000
2	12		12		3000
3	18		9		1000
				1000
bj	2750		3250   2250

 

Из оставшихся для  рассмотрения клеток выбираем клетку с наименьшим показателем стоимости перевозок. Наименьшая стоимость равна 10 и отвечает клетке (1; 1). В эту клетку дадим максимально возможную поставку овощей 2000 тонн. Неудовлетворенный спрос завода 1: 2750 – 2000 = 750 единиц. Ферма 1 более овощами не располагает (из таблицы вычеркивается соответствующая строка):

	1		2		ai
1	10		15		2000
		2000
2	12		12		3000
3	18		9		1000
				1000
bj	2750 750		3250   2250

 

Ферма 2 располагает 3000 тонн овощей, потребность завода 1 составляет 750 тонн. Значит, размер поставки равен 750. Потребность завода 2 составляет 2250 тонн.  Значит, размер поставки равен 2250.

В итоге получаем:

	1		2		ai
1	10		15		2000
		2000
2	12		12		3000
		750		2250
3	18		9		1000
				1000
bj	2750		3250

Число занятых клеток в табл. 6 должно быть равно m + n – 1  = 3+2 – 1 = 4, равенство выполняется, т.е. условие невырожденности выполнено.

Получили исходное опорное  решение.

Стоимость перевозок  при исходном опорном решении  составляет:

II этап: Улучшение опорного плана.

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

Найдем потенциалы и для каждой занятой клетки из формулы

Будем считать, что  . Тогда

    

    

   

    

 

	1		2
1	10		15
		2000
2	12		12
		750		2250
3	18		9
				1000

 

Для свободных клеток транспортной таблицы вычислим оценки свободных клеток по формуле:  . Критерием оптимальности для метода потенциалов будет выполнение условия .

  

        

Поскольку все оценки положительные, то план оптимален.

Минимальная стоимость  перевозок составит:

 

 

Задача7

 

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

Исходные данные записаны в таблице.

 

№ вар.

а11

а12

а21

а22

а31

а32

b1

b2

b3

c1

c2

f

 

11

7

2

5

6

3

8

14

30

24

-2

5

Min

        

 

Решение:

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

Каждое из неравенств системы ограничений геометрически  определяет полуплоскость с соответствующими граничными прямыми.

Для первого неравенства: строим прямую по двум точкам.

	0	2
	7	0

Взяв произвольную точку  на одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например, точка О (0; 0): , т.е. полуплоскость, содержащая точку О(0; 0) не является множеством решений неравенства .

Для второго неравенства: строим прямую по двум точкам.

	0	6
	5	0

Взяв произвольную точку  на одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например, точка О (0; 0): , т.е. полуплоскость, содержащая точку О(0; 0) является множеством решений неравенства .

Для третьего неравенства: строим прямую по двум точкам.

	0	8
	3	0

Взяв произвольную точку  на одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например, точка О (0; 0): , т.е. полуплоскость, содержащая точку О(0; 0) не является множеством решений неравенства .

Так как  , , то область допустимых решений будет лежать в I координатной четверти.

Получили область допустимых решений – треугольник АВС.

Строим вектор-градиент функции  , указывающий направление возрастания функции F: .

Строим прямую - линию уровня функции , перпендикулярную вектору-градиенту.

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

Крайняя точка С – точка минимума ,  лежит на пересечении прямых и .

Найдем координаты точки С:

      

Координаты точки  .

Подставляя  координаты точки С в функцию , находим

.

Ответ: .

 

 

                    Задача8

 

Найдите решения следующих  матричных игр

Решение:

8	13	8
10	12	10
13	9	9
13	13

Находим минимальный элемент в каждой строке.

   - нижняя цена игры

Находим максимальный элемент в каждом столбце.

     - верхняя цена игры.

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

Задача первого игрока:

Задача второго игрока:

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

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

 

Переменные y₃, y₄, y₅ - базисные.

Первое опорное решение: , . 

Запишем первое опорное решение в симплексную таблицу и проверим его на оптимальность:

	Базисные переменные	1	1	0	0	0
		y1	y2	y3	y4	y5
0	y3	8	13	1	0	0	1
0	y4	10	12	0	1	0	1
0	y5	13	9	0	0	1	1
		-1	-1	0	0	0	0

 

Первое опорное решение не оптимально, так как среди оценок есть отрицательные (-1 и -1). Оценки одинаковые. За разрешающий столбец выберем столбец, соответствующий переменной y₁.

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

 

Вместо переменной y₃ во второе опорное решение войдет переменная y₁.

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

	Базисные переменные	1	1	0	0	0
		y1	y2	y3	y4	y5
0	y3	0		1	0
0	y4	0		0	1
1	y1	1		0	0
		0		0	0		0

Второе опорное решение не оптимально, так как среди оценок есть отрицательная. За разрешающий столбец выберем столбец, соответствующий переменной y₂.

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

 

Вместо переменной y₄ во второе опорное решение войдет переменная y₂.

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

	Базисные переменные	1	1	0	0	0
		y1	y2	y3	y4	y5
0	y3	0		1
1	y2	0	1	0
1	y1	1		0
		0	0	0			0