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

Задание 1.

Система линейных уравнений задана в следующем виде:

9х₁ + 2 х₂ + х₄ = 32;

3х₁ + 2 х₂ +7х₃ = 28;

х₁ + х₃ + х₄ = 4.

Требуется:

а) исследовать систему  на совместность; если система совместна, то является ли она определенной; записать систему в матричном виде;

б) решить систему методом  Гаусса, выписать общее решение системы;

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

 

Решение.

а) Условие совместности системы  линейных уравнений даёт теорема  Кронекера–Капели:

система линейных уравнений  совместна  тогда и только тогда, когда ранг основной матрицы системы  равен рангу её расширенной матрицы:

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

Ранг матрицы А:

9 2 0 1     1 0 1 1     1 0   1  1     1 0    1    1

3 2 7 0     9 2 0 1     0 2 -9 -8     0 2  -9   -8

1 0 1 1     3 2 7 0     0 2  4  -3     0 0 -13 -11

 

Таким образом, rangА = 3.

Найдем ранг расширенной матрицы:

 

9 2 0 1  32     1 0 1 1  4      1 0   1  1   4       1 0    1    1    4

3 2 7 0  28     9 2 0 1 32     0 2 -9 -8  -4       0 2  -9   -8   -4

1 0 1 1   4      3 2 7 0 28     0 2  4  -3  16      0 0 -13 -5  -20

 

Таким образом, rangА_b = 3.

Согласно теореме Кронекера–Капели заданная система совместна.

Для совместной системы линейных уравнений вопрос о её определённости или неопределённости решается с применением следующих теорем:

Теорема. Если ранг основной матрицы  совместной системы равен числу  неизвестных, то система является определённой

Теорема. Если ранг основной матрицы  совместной системы меньше числа неизвестных, то система является неопределённой.

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

Запишем систему в матричном  виде:

А*Х = В:

9 2 0 1     х₁      32

3 2 7 0  *  х₂  = 28  .

1 0 1 1     х₃       4

                 х₄

 

б) Решим систему методом Гаусса:

 

9 2 0 1  32     1 0 1 1  4      1 0   1  1     4       1 0    1    1    4

3 2 7 0  28     9 2 0 1 32     0 2 -9 -8    -4       0 2  -9   -8   -4

1 0 1 1   4      3 2 7 0 28     0 2  4  -3    16      0 0 -13 -5   -20

 

 

Таким образом:

х₃ = 1/13*(20 – х₄); тогда:

х₂ = ½*(–4 + 9*1/13*(20 – 5 х₄) + 8 х₄) = 64/13 + 165/26 х₄;

х₁ = 4 – 20/13 + 5/13 х₄ – х₄ = 32/13 – 8/13 х₄.

Общее решение заданной системы:

(32/13 – 8/13 х₄;  64/13 + 165/26 х₄;  1/13*(20 – х₄)_;   х₄).

 

в) Неизвестная х₄ – называется свободной, при х₄ = 0 имеем базисное решение:

(32/13; 64/13; 20/13; 0)         (*).

 

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

В нашем случае базисное решение (*) является опорным.

 

 

Ответ: (32/13 – 8/13 х₄;  64/13 + 165/26 х₄;  1/13*(20 – х₄)_;   х₄).

 

Задание 2.

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

 х₁ + х₂ ≤ 5;

       -3х₁ + 4х₂ ≤ 12;

 х₁ ≤ 4;                                   (1)

 х₂ ≤ 2;

 х₁ ≥ 0; х₁ ≥ 0;

и графически найти наименьшее и  наибольшее значение линейной функции:

Z =  2х₁ + 4х₂.                                    (2)

 

Решение.

Так как n = 2, решение проведем с использованием градиента и уровней целевой функции. Решение начнем с построения области допустимых решений. В условии (1) имеется пять неравенств. Для построения области допустимых решений надо выделить то геометрическое место точек на рис. 1., которое подчиняется всем ограничениям (1). Для этого в системе координат необходимо построить следующие уравнения: х₁ = 0, x₂ = 0, х₁ + х₂ = 5,

-3x₁ + 4x₂ = 12, x₁ = 4; х₂ =2.

Построим указанные прямые по точкам, являющимися точками пересечения  с осями координат:

х₁ + х₂ = 5: где x₁ = 0, x₂ = 5; x₁ = 5, x₂ = 0;

-3x₁ + 4x₂ = 12: где x₁ = 0, x₂ = 3; x₁ = -4, x₂ = 0;

x₁ = 4; х₂ =2.

В целом все пять неравенств на плоскости выделяют пятиугольник ОАВСD.

Для нахождения оптимальной точки минимума и максимума заданной целевой функции в найденной области допустимых решений, определяем градиент целевой функции (2):

grad Z = (2; 4).

Вектор (2; 4) изобразим в виде направленного отрезка, исходящего из точки О (0, 0). Тогда линии уровня функции Z будут представлены сеткой параллельных прямых, перпендикулярных вектору  grad Z и возрастают в сторону, указанную направлением градиента.

По рисунку видно, что максимум целевой функции достигается  в точке В (3; 2), а минимум в точке О (0; 0).

Таким образом, максимум заданной целевой функции будет:

Z _max = Z (В(3; 2)) = 3*2 + 2*4 = 14;

Z _min = Z (О(0; 0)) = 0*2 + 0*4 = 0.

 

 

Построим в единой системе координат  область, ограниченную неравенствами  системы.

 

 

х₁ = 2

 

 

 

 

 

 

 

Рис. 1. – Область допустимых решений  системы.

 

 

Ответ: Z _max = 14; Z _min = 0.

 

Задание 3.

 

Найти экстремальное значение целевой  функции Z:

х₁ – 2х₂ + 3 х₃ ≥ -4;           (1)

         3х₁ – х₂ + 2 х₃ ≤ 3.

Z = 5х₁ + 2х₂ – 3х₃ → max.      (2)

 

Решение.

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

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

 х₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0, x₅ ≥ 0; x₆ ≥ 0.

 – х₁ + 2х₂ – 3х₃ + x₄       = 4;           (3)

          3х₁ – х₂ + 2 х₃            + x₅ = 3.         

Z = –5х₁ – 2х₂ + 3х₃ + 0*x₄ + 0*x₅ → min.      (4)

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

Х_Б1 = (0;  0; 0; 0; -4; 3).

Определим теперь значение целевой  функции при этом опорном плане:

Z(Х_Б1) = –5*0 – 2*0 + 3*0х₃ + 0*x₄ + 0*x₅ = 0.

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

Таблица 1.

Б1	СБ1	В1	А1	А2	А3	А4	А5
			-5	-2	3	0	0
А4	0	4	1	-2	3	1	0
А5	0	3	3	-1	2	0	1
zj - cj		0	5	2	-3	0	0

 

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

Для этого определим, какой вектор выводим из базиса, а какой вводим из условия:

Ө₀₁ = min{4/1; 3/3} = min {4; 1} = 1.

Таким образом, в базис вводим вектор А₁, выводим вектор А₅.

Таблица 2.

Б2	СБ2	В2	А1	А2	А3	А4	А5
			-5	-2	3	0	0
А4	0	3	0	-5/3	7/3	1	-1/3
А1	-5	1	1	-1/3	2/3	0	1/3
zj - cj		-5	0	11/3	-19/3	0	-5/3

 

В таблице 2 не выполнено условие оптимальности: в строке z_j - c_j есть положительные элементы, организуем пересчет таблицы. Выводим из базиса вектор А₄, вводим в базис вектор А₂.

Таблица 3.

Б3	СБ3	В3	А1	А2	А3	А4	А5
			-5	-2	3	0	0
А2	-2	-9/5	0	1	-7/5	-3/5	1/5
А1	-5	8/5	1	0	17/15	1/5	4/15
zj - cj		-22/5	0	0	-88/15	1/5	-26/15

 

В таблице 3 не выполнено условие оптимальности: в строке z_j - c_j есть положительные элементы, организуем пересчет таблицы. Выводим из базиса вектор А₁, вводим в базис вектор А₄.

Таблица 4.

Б4	СБ4	В4	А1	А2	А3	А4	А5
			-5	-2	3	0	0
А2	-2	16/5	3	1	2	0	1
А4	0	8	5	0	17/3	1	4/3
zj - cj		-32/5	-1	0	-7	0	-2

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

Х_Б4 = (0; 16/5; 0; 8; 0), Z(Х_Б4) = -32/5.

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

Имеем ответ: Х_опт. = (0; 16/5; 0; 8; 0), Z = 32/5.

Ответ: Z = 32/5.

 

Литература

 

 

 

1. Жильцов О.Б. Математичне програмування (з елементами інформаційних технологій): Навч. посіб. для студ. вищ. навч. закл. / О.Б. Жильцов, В.Р. Кулян, О.О. Юнькова; За ред. О.О. Юнькової. – К.: МАУП, 2006. – 184 с.
2. Кундышева Е.С. Экономико-математическое моделирование: Учебник для вузов / под ред. Б.А. Суслакова. – М.: Изд.-торг. корпорация «Дашков и К», 2010. – 424с.
3. Лугінін О.Є. Економетрія: Навч. посіб. – К.: Центр учбової літератури, 2008. – 278 с.
4. Невежин В.П., Кружилов С.И. Сборник задач по курсу «Экономико-математическое моделирование». – М.: ОАО «Издательский дом «Городец», 2005. – 320 с.
5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2005. – 144 с.
6. Шелобаев С.И. Экономико-математические методы и модели: Учеб. пособ. для вузов. – М.: ЮНИТИ-ДАНА, 2005. – 287 с.
7. Экономико-математические методы и прикладные модели: Учеб. пособ. для вузов / Под ред. В.В. Федосеева. – М.: ЮНИТИ-ДАНА, 2002. – 391 с.