Задания для самостоятельной работы

1. Для сравнения производительности труда рабочих двух цехов экономист исследовал среднюю выработку рабочих. Обследовано n₁= 40 рабочих в первом цехе иn₂ = 38 во второй. Выборочные средниед.е.,д.е. Генеральные дисперсии Д(х₁ ) = 2,4 Д(х₂ ) = 2,8 При уровне значимости α = 0,1 проверить нулевую гипотезу Н₀ :при конкурирующей гипотезе Н₁:Можно ли считать, что рабочие обоих цехов имеют одинаковую производительность?

2. Стандартный срок службы электроприбора а= 1000 часов. Проверка 50 приборов показала, что средний срок службычасов, при среднем квадратическом отклонениичасов. При уровне значимостипроверить нулевую гипотезу Н₀:если конкурирующая гипотеза Н₁:. Удовлетворяет ли срок службы электроприбора стандартуа?

3. В лаборатории определяют содержание углерода в 30 пробах нелегированной стали. Получены следующие данные: ,По стандарту количество углерода в пробе должно быть равно а = 0,2. При уровне значимостипроверить Н₀ :при Н₁ :Удовлетворяет ли среднее содержание углерода в пробе стандартному?

4. Из двух партий продукции, изготовленных по старой и новой технологиям, взяты выборки объемов n₁ = 45 иn₂ =40. Расход сырья на единицу продукции по старой технологииг., а по новой -г. Генеральные дисперсии равныD(x₁)=6,5D(x₂)=8,0. При уровне значимостипроверить нулевую гипотезу Н₀:при конкурирующей гипотезе Н₁:>Можно ли считать, что расход сырья на изготовление единицы продукции по новой технологии уменьшился?

5. Для исследования колеблемости урожайности свеклы в зависимости от типа внесенных удобрений было засеяно по 10 опытных участков: n₁=10,n₂=10. Выборочные дисперсии соответственно равны,При уровне значимостипроверить Н₀:D(x₁)=D(x₂) при Н₁:D(x₁)>D(x₂). Зависит ли колеблемость урожайности свеклы от типа внесенных удобрений?

6. Стандартный срок работы электролампы а=800 часов. В результате выборочной проверки 50 ламп установлено, что средний срок работы часов. Среднее квадратическое отклонение генеральной совокупности равно 30 часов. При уровне значимостипроверить Н_о:, если Н₁:Удовлетворяет ли срок работы электролампы стандарту а?

Форма контроля: Проверка решений задач и заданий

Гармонический анализ

Функциональный анализ

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

Специальные разделы математики Элементы линейного программирования

Задача 1.Предприятие выпускает два вида продукцииАиВ, для производства которых используется сырьё трех типов. На изготовление единицы изделияАтребуется затратить сырья каждого типа кг соответственно, а для единицы изделияВ–кг. Производство обеспеченно сырьем каждого типа в количествекг соответственно. Стоимость единицы изделияАсоставляетруб., а единицы изделияВ-руб. Требуется составить план производства изделийА иВ, обеспечивающий максимальную стоимость готовой продукции. Числовые данные параметров приведены в следующей таблице.

													
2	3	1	1	4	3	400	900	600	200	100	-150	60	40

1. Решить задачу симплекс – методом.

2. Сформулировать двойственную задачу и привести её решение.

3. Найти многогранник и интервалы устойчивости двойственных оценок.

4. Оценить стоимость готовой продукции, если запасы сырья каждого типа на производстве изменились на величину кг соответственно.

5. Решить исходную задачу графическим методом.

Решение. 1. Составим математическую модель задачи. Пусть, - количество производимых изделий видаиВ соответственно. Тогда на их производство будет израсходовано () сырья 1-го типа. По условию это количество не должно превосходить располагаемого объема этого сырья в количестве 400 единиц, т.е.. Выполняя аналогичные действия с другими типами сырья, окончательно получим систему ограничений:

(1)

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

Количество изделий физически является неотрицательными величинами (нельзя произвести отрицательное количество изделий), что при формализации даеттривиальныеограничения задачи:

. (2)

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

, (3)

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

Для решения задачи симплекс–методом приведем задачу (1)-(3) к каноническому виду, введя дополнительныебалансовые переменные. Неравенства (1) преобразуются в уравнения путем добавления указанных переменных по одной в каждое неравенство (другими словами, левые части неравенств становятсясбалансированными с правыми частями):

(4)

Физически переменные представляют собой остатки сырья соответственно 1-го, 2-го и 3-го типов, остающиеся неиспользованными при произвольном плане выпуска продукциииВ в количествеединиц. Поэтому они также неотрицательны и тривиальная система неравенств в итоге принимает вид:

 0,j=. (5)

Введем балансовые переменные в целевую функцию с коэффициентами, равными 0:

.

Перенесем слагаемые с переменными в левую часть полученного выражения и запишем целевую функцию в виде уравнения:

_.(6)

Задача в форме (4)-(6) называется канонической моделью.

Для решения задачи (4)-(6) симплекс-методом необходимо иметь исходный опорный план, т.е. базисное решение системы уравнений (4), которое удовлетворяет условиям (5). Для этого все переменные системы надо разделить на две группы –базисныеисвободные. Сначала выбирают базисные. Поскольку уравнений всего три, то и базисных переменных будет также три. Переменные могут быть базисными, если матрица коэффициентов при них является невырожденной, т.е. её определитель не равен нулю. В качестве базисных переменных целесообразно выбрать балансовые переменные, каждое из которых входит только в одно уравнение системы (4) и поэтому матрица коэффициентов при них будет единичной, и, стало быть, невырожденной. Остальные переменные (и) будут свободными. Если систему (4) разрешить относительно выбранных базисных переменных, то тем самым найдется общее решение системы. Базисное решение получается как частный случай общего решения, когда все свободные переменные в общем решении системы (4) приравниваются нулю. Подставив в (4), легко получаем значения базисных переменных:

= 400; = 900; = 600,

которые удовлетворяют ограничениям (5). Тем самым найден исходный опорный план, который в векторном виде запишется:

= ( 0 ; 0 ; 400 ; 900 ; 600 ).

Подставив компоненты в целевую функцию (3), получим её значение для этого плана:

=0.

Теперь составим первоначальную симплексную таблицу:

	1	1	0	0	400	=200
3	4	0	1	0	900	=300
1	3	0	0	1	600	=600
	- 40	0	0	0	0	-

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

Правила заполнения последнего столбца рассмотрим позже.

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

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

Определим эту пару переменных. Сначала определим переменную, которая войдет в число базисных. Это должна быть одна из свободных переменных: или. Выбираем ту переменную, которой в индексной строке соответствует наименьшее отрицательное число (-60, обведено прямоугольником). Значит, переменнаястановится базисной, а этот столбец таблицы называютразрешающим столбцом.

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

(7)

Вычисленные по формуле (7) значения , () записываются в последнем столбце () симплекс–таблицы. Строка, в которой находится минимальное симплексное отношение, называетсяразрешающей строкой. В нашем случае это первая строка с симплексным отношением200. Выбор разрешающей строки по приведенному правилу гарантирует неотрицательность свободных членов при дальнейшем пересчете таблицы и, стало быть, гарантию того, что получаемые базисные решения системы будут опорными планами задачи линейного программирования.

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

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

Теперь приступают к пересчету таблицы. Заполнение новой таблицы начинается с разрешающей строки. Элементы разрешающей строки прежней таблицы делятся на разрешающий элемент (он равен 2) и в результате в разрешающем столбце этой строки будет коэффициент 1 (отсюда её называют нормированной строкой):

1	12	12	0	0	200

Далее заполняются остальные строки новой таблицы, включая индексную строку (кроме элементов столбца ) так, чтобы получить нули в столбцеэтих строк. Для этого используют нормированную разрешающую строку. Из элементов строк прежней таблицы вычитают соответствующие элементы нормированной разрешающей строки, умноженные на коэффициент разрешающего столбца преобразуемой строки. Покажем это на примере заполнения второй строки. В разрешающем столбце этой строки стоит коэффициент 3. Поэтому вычтем из элементов второй строки соответствующие утроенные элементы нормированной разрешающей строки:

1	12	12	0	0	200
3-31=0	4-312=52	0-312= -32	1-30=1	0-30=0	900-3200=300

Все остальные строки пересчитываются аналогично. В итоге получаем таблицу первой итерации симплекс-метода:

1	12	12	0	0	200	400
0		-32	1	0	300	120
0	52	-12	0	1	400	600
0		30	0	0	12000	-

Произошел переход к новым базисным переменным: . При этом переменные

являются свободными, и в новом опорном плане их значения равны нулю. Значения остальных переменных получаем из нового столбцасвободных членов (находятся напротив единиц базисных переменных):

х₁ = 200; х₄ = 300; х₅ = 400.

Запишем опорный план в векторной форме:

= ( 200 ; 0 ; 0 ; 300 ; 400 ).

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

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

Далее по такой же схеме пересчитываем таблицу первой итерации и получаем таблицу второй итерации:

1	0	45	-15	0	140
0	1	-35	25	0	120
0	0	1	-1	1	100
0	0	24	4	0	13200	-

Аналогично определяем новый опорный план:

= ( 140 ; 120 ; 0 ; 0 ; 100 ).

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

;=13200.

Итак, задача линейного программирования решена. Возвращаясь к содержательной постановке задачи, можно сказать, что план выпуска, включающий 140 единиц продукции вида и 120 единиц продукции вида, является оптимальным. При этом будет достигнута максимальная стоимость готовой продукции.

2. Рассмотрим исходную задачу (1)-(3). При переходе к двойственной задаче нужно выполнить ряд правил. Во-первых, каждому ограничению (1) исходной задачи соответствует переменная двойственной задачи. Таким образом, здесь будут три двойственные переменные . Во-вторых, нетривиальные ограничения двойственной задачи задаются матрицей, являющейся транспонированной по отношению к матрице ограничений (1), неравенства ограничений типа “” превращаются в неравенства типа “”, а свободными членами нетривиальных ограничений становятся коэффициенты при соответствующих переменных целевой функции (3). В-третьих, находится минимум, а не максимум целевой функции двойственной задачи и ее коэффициентами становятся свободные члены системы (1). Наконец, двойственные переменные, как и переменные задачи (1)-(3), подчиняются тривиальным условиям неотрицательности. С учетом этих замечаний задача, двойственная задаче (1)-(3), имеет вид:

(8)

,i=1,2,3, (9)

F= 400y₁+ 900y₂ + 600y₃. (10)

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

Оптимальное решение задачи (8)-(10) находится в индексной строке последней симплекс-таблицы в столбцах, соответствующих первоначальнымбазисным переменным. Отсюда находим:

= ( 24 ; 4 ; 0 ).

Таким образом, = 24 > 0, = 4 >0,=0.

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

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

0. (11)

Здесь D^-1- матрица, состоящая из столбцов первоначальных базисных переменных (т.е.) последней симплекс-таблицы:

.

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

;.

Сначала определим многогранник устойчивости двойственных оценок.

Запишем неравенство (11):

=0.

Векторное неравенство преобразуем в систему скалярных неравенств, выписывая их для каждой компоненты вектора:

4/5 (400 + b₁) – 1/5 (900 + b₂)0,

-3/5 (400 + b₁) + 2/5 (900 + b₂)0, (12)

(400 + b₁) – (900 + b₂) + (600 + b₃)0.

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

Теперь построим интервалы устойчивостипо каждому типу ресурса в отдельности. Вначале построим интервал устойчивости для первого типа сырья. Положим=0,= 0. Подставляя это в систему неравенств (12), находим:

4/5 b₁ - = - 140, илиb₁-175,

- 3/5 b₁ - = - 120, илиb₁ 200,

b₁ 900 – 400 - 600 = - 100, илиb₁-100.

Объединяя эти неравенства, получаем:

- 100 b₁ 200,

что соответствует следующему интервалу устойчивости по первому ресурсу:

.

Изменение запасов сырья только второго типа (b₁=b₃= 0) дает из системы (12) нам следующее:

- 1/5 b₂ - + = - 140, илиb₂ 700,

2/5 b₂ - = - 120, илиb₂ - 300,

- b₂ 900 – 400 - 600 = - 100, илиb₂ 100.

Отсюда получаем неравенство

- 300 b₂ 100

и интервал устойчивости по второму ресурсу:

.

Аналогично исследуем устойчивость по третьему типу сырья (b₁=0,b₂=0):

b₃ 900 – 400 – 600 = - 100

или

- 100 Δb₃< ∞.

Отсюда интервал устойчивости: .

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

4. Проверим выполнение неравенства (11) для условий нашей задачи ():

= = > 0.

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

Получили систему двух уравнений с двумя неизвестными. Решая её, получаем новый оптимальный план:

= 280, = 40.

При этом новая стоимость продукции получается подстановкой этих значений в целевую функцию (3):

Z_нов.max= 60 ∙ 280 + 40 ∙ 40 = 18400.

5. Рассмотрим исходную задачу (1)-(3). Поскольку в ней только две переменные_,, то её можно решить графически на координатной плоскости_. Тривиальные неравенства (2) означают, что решение следует искать в первом квадранте системы координат. Нетривиальные неравенства (1) представляют собой полуплоскости, пересечение которых в пределах первого квадранта образует так называемуюобласть допустимых решений(ОДР) задачи линейного программирования. Оптимальный план представляет собой одну из угловых точек ОДР.

Построим, например, полуплоскость, отвечающую первому неравенству системы (1):

≤ 400.

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

= 400.

Линию, если она не проходит через начало координат, проще всего построить по двум точкам на осях координат. При = 0 получаем= 400, а при= 0 находим= 200. Соединяем эти две точки прямой линией, получаем две полуплоскости, выше и ниже этой прямой. Отметим эту линию цифрой (1). Исходному неравенству отвечает только одна из указанных полуплоскостей. Она определяется подстановкой в неравенство пробной точки, нележащей на граничной прямой. Например, такой точкой может быть начало координатх₁ =х₂ = 0. Подставляя в неравенство нулевые значения переменных, получим:

0 400.

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

400 (1)

200

Аналогично построим и две другие полуплоскости, получим в итоге ОДР (ее границы обведены жирными линиями):

400 (1)

200

(3)

40 (2)

60 200 400 600

Теперь надо найти угловую точку ОДР, в которой целевая функция достигает максимума. Для этого построим градиент (вектор роста)целевой функции= (60 ; 40 ), координаты которого состоят из коэффициентов целевой функции при соответствующих переменных. Градиент указывает направление наискорейшего возрастания целевой функции. Надо найти в ОДР точку, наиболее удаленную от начала координат в этом направлении. Для этого на направлениевектораиз всех угловых точек ОДР опускаем перпендикуляры. Оптимальному плану соответствует угловая точка, порождающая самый дальний от начала координат перпендикуляр. В нашем случае такая угловая точка образована пересечением границ 1-го и 2-го неравенств:

Решение этой системы даёт оптимальный план задачи:

= 140;= 120.

Заметим, что полученные числа совпадают с решением симплексного метода.