Контрольная работа по "Экономико-математическому регулированию"

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

 
2X₁+7X₂+1X₃+0X₄+X5=5 
1X₁+4X₂+2X₃+8X₄+R1=6 
-1X₁+0X₂+2X₃+5X₄+R2=9

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

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

 
       Из данных задачи  составляем исходную симплекс  таблицу. 

	X1	X2	X3	X4	Своб. член
F	-1	-5	-4	3	0
X5	2	7	1	0	5
R1	1	4	2	8	6
R2	-1	0	2	5	9
M	0	-4	-4	-13	-15

 
 
         Так как  в столбце свободных членов  нет отрицательных элементов,  то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -13 Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 8. 

	X1	X2	X3	Своб. член
F	-1.375	-6.5	-4.75	-2.25
X5	2	7	1	5
X4	0.125	0.5	0.25	0.75
R2	-1.625	-2.5	0.75	5.25
M	1.625	2.5	-0.75	-5.25

 
          В строке M имеются отрицательные элементы, это означает что полученное  решение не оптимально. Определим  ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -0.75 Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 0.25. 

	X1	X2	X4	Своб. член
F	1	3	19	12
X5	1.5	5	-4	2
X3	0.5	2	4	3
R2	-2	-4	-3	3
M	2	4	3	-3

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

Метод искусственного базиса (Симплекс метод) - Пример 2

Целевая функция: 
 
2x₁-x₂+7x₃+11x₄+5x₅→min 
Условия: 
 
2x₁+5x₃+x₄+8x₅=12 
-3x₁+6x₂+2x₃-2x₄≤5

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

2x₁+5x₃+x₄+8x₅+R1=12 
-3x₁+6x₂+2x₃-2x₄+X6=5

         Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции.

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

         Из данных задачи составляем исходную симплекс таблицу.

 

	X1	X2	X3	X4	X5	Своб. член
F	2	-1	7	11	5	0
R1	2	0	5	0	8	12
X6	-3	6	2	-2	0	5
M	-2	0	-5	0	-8	-12

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

	X1	X2	X3	X4	Своб. член
F	0.75	-1	3.875	11	-7.5
X5	0.25	0	0.625	0	1.5
X6	-3	6	2	-2	5
M	0	0	0	0	0

 
          В строке M отрицательные элементы отсутствуют. Рассмотрим строку F в которой имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1 Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X6, а ведущий элемент: 6. 

	X1	X6	X3	X4	Своб. член
F	0.25	0.167	4.208	10.667	-6.667
X5	0.25	0	0.625	0	1.5
X2	-0.5	0.167	0.333	-0.333	0.833
M	0	0	0	0	0

 
 
          Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение F=6.667 
при значениях переменных равных: X5=1.5, X2=0.833,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решение задачи 2.2.

1)Построение экономико-математической  модели задачи

Переменные:

x ₁- количество кормов первого вида;

 x ₂ - количество кормов второго вида.

 

          ƒ(x)=0,2 x ₁ +0,3 x ₂ →min

 

Ограничения задачи имеют вид:

2 x _{1 +} x ₂ ≥6;

2 x _{1 +} 4 x ₂ ≥12;

x ₁≥0;

x ₂≥0.

2) Построим область  допустимых решений (ОДР) задачи.

       Первое ограничение по питательному веществу имеет вид: 2 x _{1 +} x ₂ ≥6.   Найдем пересечение граничной прямой с осями координат. Прямая 2 x _{1 +} x ₂=6 проходит через точки (0;6) и (3;0). Определим какая полуплоскость удовлетворяет неравенству, подставив в него координаты (0,0). 2∙0+0<6, следовательно утверждение 2 x _{1 +} x ₂ ≥6 является неверным. Областью решения данного неравенства служит верхняя полуплоскость. (на рисунке прямая I)

      Второе ограничение по питательному  веществу имеет вид: 2 x _{1 +} 4 x ₂ ≥12.

Прямая 2 x _{1 +} 4 x ₂ =12 проходит через точки (0;3) и (6;0). Определим какая полуплоскость удовлетворяет неравенству, подставив в него координаты (0,0). 2∙0+4∙0<12, следовательно утверждение 2 x _{1 +} 4 x ₂ ≥12 является неверным. Областью решения данного неравенства служит верхняя полуплоскость (на рисунке прямая II).

      Заштрихуем общую область для  всех неравенств.

 

    3)Построим некоторую линию уровня для целевой функции (ЦФ). Приравняем целевую функцию постоянной величине a: 0,2 x ₁ +0,3 x ₂ =a. Это уравнение является множеством точек, в котором целевая функция принимает значение, равное a. Если a=3, то 0,2 x₁ + 0,3 x₂ = 3

           x₁ = 0     x₂ = 10

           x₁ = 15   x₂ = 0

Через эти две  точки проведем линию уровня (пунктирная прямая на рисунке).

4) Определим направление движения линии уровня.

Построим вектор-градиент, координаты которого являются частными производными функции ƒ(x), т.е. (0,2;0,3). Чтобы построить этот вектор, нужно соединить точку (0,2;0,3) с началом координат. При максимизации ЦФ линию уровня необходимо смещать в направлении вектора-градиента, а при минимизации – в направлении, противоположном вектору-градиенту.

В данном случае движение линии уровня осуществляем до её пересечения с точкой В. Следовательно, именно в этой точке достигается минимум ЦФ.

5) Определим координаты точки В, являющейся точкой пересечения граничных прямых, решив систему уравнений:

    2x₁ +   x₂ = 6;

    2x₁ + 4x₂ = 12.

    

Получаем  точку В (2; 2) – min ЦФ.

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

минимальное значение   min  f(X) = 0,2*2 + 0,3*2 = 1. (тыс. руб.);

максимальное  значение max f(X) = +∞ (функция неограниченна  сверху на ОДР).

Ответ:                 min f(X) = 1 (тысяч денежных единиц);

                              max f(X) = +∞ (ОДР неограничен сверху).

 

      y

      15