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

Условия задачи:

1.2. Симплекс-метод  с искусственным базисом (М-задача).

2.2. Совхоз  для кормления животных использует  два вида корма.

В дневном  рационе животного должно содержаться  не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Исходные данные приведены ниже.

Построить экономико-математическую модель задачи, дать необходимые комментарии к  ее элементам и получить решение  графическим методом. Что произойдет, если решать задачу на максимум и почему?

4.2. Компания по продаже мототехники оценивает ежедневный спрос в 20 единиц. Годовые издержки хранения на один мотоцикл составляют 10 тыс. руб. Магазин работает 300 дней в году. Средние издержки одного заказа составляют 40 тыс. руб. Определите совокупные издержки заказа и оптимальный размер партии. Постройте график общих годовых затрат.

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

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

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

        Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные (x_n+m) и искусственные (R_i)- базисными.

         Исходная таблица для "Метода искусственного базиса" имеет следующий вид:

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

 Алгоритм метода искусственного базиса.

 Подготовительный этап  

Приводим задачу ЛП  к каноническому виду

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

.........................................

a_i,1x₁+a_i,2x₂+...a_i,nx_n+R_i=b_i

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

         В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a_0,n= -a_0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условию-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, x_n+m , к каждому i-му условию-равенству добавляем искусственную переменную R_i.

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

Шаг 1. Проверка на допустимость.   

         Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы, то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

         Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.

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

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

     На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность. Если среди элементов симплексной таблицы, находящихся в строках M и F(не беря в расчет элемент b₀ - текущее значение целевой функции и элемент -∑b_i) нет отрицательных, то найдено оптимальное решение.

2.1 Положительность строки M

          Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑b_i)

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для  которой это отношение минимально - ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

          Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2

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

          Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2.

2.2 Положительность строки F

          Проверяем на положительность элементы строки F. Если имеются отрицательные элементы (не считая b₀), выбираем среди отрицательных элементов строки F максимальный по модулю.

-a_0,l=min{-a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для  которой это отношение минимально - ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

          Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2

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

          Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение. 

Правила преобразований симплексной таблицы

         При составлении новой симплекс-таблицы в ней происходят следующие изменения: 

• Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  
• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l
• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,l×a_k,j/ a_k,l

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

Целевая функция: 
1X₁+5X₂+4X₃-3X₄→max

Условия: 
 
2X₁+7X₂+1X₃+0X₄≤5 
1X₁+4X₂+2X₃+8X₄=6 
-1X₁+0X₂+2X₃+5X₄=9

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

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

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

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

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

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

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

 
          В столбце свободных членов и в строке 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) взятая с противоположным знаком.

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

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

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

 
 
          Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки 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