Загрузка
ТестыСправкаQualiMe РегистрацияВход
ТестыСправкаQualiMe
РегистрацияВход
Тесты Студент
Симплексный метод ИТ
45.000

Симплексный метод ИТ

Решите симплексным методом задачу:
  1. $$maxf(X)=5x_1+3x_2+x_3$$; 
  2. $$\left\{\begin{array}{lr} x_1-2x_2-x_3=2, \\ x_2+5x_3=2; \end{array}\right. $$ 
  3. $$x_i \geq0$$, $$i=\overline{1; 3}$$.
Оценка целевой функции: 
$$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$. 
 Оценки переменных: 
$$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$. 
Критерий оптимальности опорного плана задачи: если при максимизации целевой функции все оценки переменных неотрицательные, то план оптимальный. 
Если опорный план задачи не удовлетворяет критерию оптимальности, то выполняем следующие действия. 
Нулевая итерация симплексной таблицы.
  1. Выбираем наихудшую оценку переменной. В случае максимизации целевой функции – наименьшую отрицательную, а в случае минимизации – наибольшую положительную. Столбец, в которой находится эта переменная, называется разрешающим столбцом.
  2. Для каждой базисной переменной составляем симплексные отношения – находим отношения элементов столбца $$A_0$$ и соответствующих элементов разрешающего столбца. Из полученных отношений выбираем наименьшее. Строку, которой соответствует это отношение, называем разрешающей строкой.
  3. Элемент, который находится на пересечении разрешающих столбца и строки, называется разрешающим элементом $$a^0_{рр}$$.
Первая итерация симплексной таблицы.
  1. Вносим изменения в базис: переменную, находящуюся в разрешающей строке нулевой итерации, заменяем переменной из разрешающего столбца.
  2. Все элементы разрешающей строки делим на разрешающий элемент и записываем в строку первой итерации (номер строки совпадает с номером строки нулевой итерации).
  3. Все остальные элементы столбца, номер которого совпадает с номером разрешающего столбца нулевой итерации, считаем равными нулю.
  4. Остальные элементы таблицы находим по правилу прямоугольника (Рис. 1): $$a_{ji}^{1}=\frac{a_{ji}^{0} \cdot a_{pp}^{0}-a_{jP}^{0} \cdot a_{Pi}^{0}}{a_{PP}^{0}}$$.
                                                           
                                                                                    Рис. 1
Предпочтительный вид ЗЛП:
$$maxf(X)=5x_1+3x_2+x_3-M\omega$$;
$$\left\{\begin{array}{lr} \underline{x_1}-2x_2-x_3=2,\\ x_2+5x_3+\underline{\omega}=2; \end{array}\right.$$
$$x_i \geq0$$, $$i=\overline{1;3}$$. 
Базисные переменные: $$x_1=2$$, $$\omega=2$$. 
Свободные переменные: $$x_2=0$$, $$x_3=0$$. 
Составим симплексную таблицу и выполним симплексные преобразования:
                    
Пояснения к нулевой итерации.
  1. Заполняем индексную строку:
    $$\Delta_0=5 \cdot 2- M \cdot 2 =-2M+10$$;
    $$\Delta_1=5 \cdot 1- M \cdot 0 -5 =0$$;
    $$\Delta_2=5 \cdot (-2)- M \cdot 1 -3 =-M-13$$;
    $$\Delta_3=5 \cdot (-1)- M \cdot 5 -1 =-5M-6$$;
    $$\Delta_4=5 \cdot 0- M \cdot 1 +M =0$$.
    Поскольку присутствуют отрицательные оценки переменных, то опорный план задачи не оптимальный.
  2. В качестве разрешающего столбца выбираем столбец $$A_3$$ с наименьшей отрицательной оценкой переменной.
  3. Составляем симплексные отношения:
    $$\theta_1$$ не существует, так как $$a_{13}=-1$$; $$\theta_2=2:5=0,4$$.
  4. Вторая строка будет разрешающей. Разрешающий элемент $$a_{pp}=5$$.
Пояснения к первой итерации.
  1. Вносим изменения в базис: переменную $$\omega$$ заменяем переменной $$x_3$$ из разрешающего столбца.
  2. Все элементы разрешающей строки нулевой итерации делим на $$a_{pp}=5$$ и результаты записываем во вторую строку первой итерации.
  3. Элемент $$a_{13}^{1}$$ считаем равным нулю.
  4. Остальные элементы первой строки находим по правилу прямоугольника:
    $$a_{10}^{1}=\frac{2 \cdot 5-2 \cdot (-1)}{5}=2,4$$;
    $$a_{11}^{1}=\frac{1 \cdot 5-0 \cdot (-1)}{5}=1$$;
    $$a_{12}^{1}=\frac{-2 \cdot 5-1 \cdot (-1)}{5}=-1,8$$.
  5. Заполняем индексную строку. Поскольку среди оценок переменных первой итерации есть отрицательная оценка, то опорный план не оптимальный.
  6.  Переходим ко второй итерации и аналогично заполняем симплексную таблицу. Поскольку все оценки переменных неотрицательные, то опорный план второй итерации оптимальный:
    $$X^*=(6; 2;0)$$; $$f(X^*)=36$$.
Симплексные преобразования можно выполнить иначе:
                           
Выберите несколько вариантов ответов
Решите симплексным методом задачу:
  1. $$minf(X)=5x_1+3x_2$$; 
  2. $$\left\{\begin{matrix} x_1-2x_2=2, \\ x_2+5x_3=2; \end{matrix}\right. $$ 
  3. $$x_i \geq0$$, $$i=\overline{1; 3}$$.
Оценка целевой функции: 
$$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$. 
 Оценки переменных: 
$$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$. 
Критерий оптимальности опорного плана задачи: если при максимизации целевой функции все оценки переменных неотрицательные, то план оптимальный. 
Если опорный план задачи не удовлетворяет критерию оптимальности, то выполняем следующие действия. 
Нулевая итерация симплексной таблицы.
  1. Выбираем наихудшую оценку переменной. В случае максимизации целевой функции – наименьшую отрицательную, а в случае минимизации – наибольшую положительную. Столбец, в которой находится эта переменная, называется разрешающим столбцом.
  2. Для каждой базисной переменной составляем симплексные отношения – находим отношения элементов столбца $$A_0$$ и соответствующих элементов разрешающего столбца. Из полученных отношений выбираем наименьшее. Строку, которой соответствует это отношение, называем разрешающей строкой.
  3. Элемент, который находится на пересечении разрешающих столбца и строки, называется разрешающим элементом $$a^0_{рр}$$.
Первая итерация симплексной таблицы.
  1. Вносим изменения в базис: переменную, находящуюся в разрешающей строке нулевой итерации, заменяем переменной из разрешающего столбца.
  2. Все элементы разрешающей строки делим на разрешающий элемент и записываем в строку первой итерации (номер строки совпадает с номером строки нулевой итерации).
  3. Все остальные элементы столбца, номер которого совпадает с номером разрешающего столбца нулевой итерации, считаем равными нулю.
  4. Остальные элементы таблицы находим по правилу прямоугольника (Рис. 1):
    $$a_{ji}^{1}=\frac{a_{ji}^{0} \cdot a_{pp}^{0}-a_{jP}^{0} \cdot a_{Pi}^{0}}{a_{PP}^{0}}$$. 
                                                                                    
                                                                                                             Рис. 1
Предпочтительный вид ЗЛП: 
 $$minf(X)=5x_1+3x_2+M\omega$$; 
 $$\left\{\begin{array}{lr} \underline{x_1}-2x_2=2,\\ x_2+5x_3+\underline{\omega}=2; \end{array}\right.$$ 
 $$x_i \geq0$$, $$i=\overline{1;3}$$; $$\omega \geq0$$. 
Базисные переменные: $$x_1=2$$, $$\omega=2$$. 
Свободные переменные: $$x_2=0$$, $$x_3=0$$. 
Составим симплексную таблицу и выполним симплексные преобразования: 
                                                       
 Пояснения к нулевой итерации.
  1. Заполняем индексную строку:
    $$\Delta_0=5 \cdot 2+ M \cdot 2 =2M+10$$;
    $$\Delta_1=5 \cdot 1+ M \cdot 0 -5 =0$$;
    $$\Delta_2=5 \cdot (-2)+ M \cdot 1 -3 =M-13$$;
    $$\Delta_3=5 \cdot 0+ M \cdot 5 -0 =5M$$;
    $$\Delta_4=5 \cdot 0+ M \cdot 1 -M =0$$.
    Поскольку присутствуют положительные оценки переменных, то опорный план задачи не оптимальный.
  2. В качестве разрешающего столбца выбираем столбец $$A_3$$ с наибольшей положительной оценкой переменной.
  3. Составляем симплексные отношения:
    $$\theta_1$$ не существует, так как $$a_{13}=0$$; $$\theta_2=2:5=0,4$$.
  4. Вторая строка будет разрешающей. Разрешающий элемент $$a_{pp}=5$$.
Пояснения к первой итерации.
  1. Вносим изменения в базис: переменную $$\omega$$ заменяем переменной $$x_3$$ из разрешающего столбца.
  2. Все элементы разрешающей строки нулевой итерации делим на $$a_{pp}=5$$ и результаты записываем во вторую строку первой итерации.
  3. Элемент $$a_{13}^{1}$$ считаем равным нулю.
  4. Остальные элементы первой строки находим по правилу прямоугольника:
    $$a_{10}^{1}=\frac{2 \cdot 5-2 \cdot 0}{5}=2$$;
    $$a_{11}^{1}=\frac{1 \cdot 5-0 \cdot 0}{5}=1$$;
    $$a_{12}^{1}=\frac{-2 \cdot 5-1 \cdot 0}{5}=-2$$.
  5. Заполняем индексную строку. Поскольку все оценки переменных первой итерации неположительные, то опорный план оптимальный:
    $$X^*=(2; 0;0,4)$$; $$f(X^*)=10$$.
  1. Задача с искусственным базисом называется $$M$$-задачей. 
  2. При решении $$M$$-задачи по мере выведения искусственных переменных из базиса они выводятся и из симплексной таблицы.
Выберите несколько вариантов ответов
Решите симплексным методом задачу:
  1. $$minf(X)=x_1+5x_2+2x_3$$; 
  2. $$\left\{\begin{matrix} x_1-x_2=50, \\ 2x_2+x_3=5; \end{matrix}\right.$$ 
  3. $$x_i \geq0$$, $$i=\overline{1; 3}$$.
Симплексный метод
  1. Математическая модель задачи должна быть приведена к предпочтительному виду. 
  2. Предпочтительные переменные являются базисными, а остальные переменные – свободными. 
  3. Свободные переменные равны нулю. Чтобы найти значения базисных переменных, необходимо в систему ограничений подставить значения свободных переменных. 
  4. Пример составления симплексной таблицы.
                                                          
    Задача:
    $$minf(X)=c_1x_1+c_2x_2+c_3x_3$$;
    $$\left\{\begin{matrix} \underline{x_1}+a_{12}x_2=b_1,\\ a_{21}x_2+\underline{x_3}=b_2. \end{matrix}\right.$$ 
  5. Пример заполнение индексной строки симплексной таблицы.
    Оценка целевой функции (значение целевой функции):
    $$\Delta_0=c_1 \cdot b_1+ c_3 \cdot b_3$$.
    Оценки переменных:
    $$\Delta_1=c_1 \cdot a_{11}+ c_3 \cdot a_{21}-c_1$$;
    $$\Delta_2=c_1 \cdot a_{12}+ c_3 \cdot a_{22}-c_2$$;
    $$\Delta_3=c_1 \cdot a_{13}+ c_3 \cdot a_{23}-c_3$$. 
  6. Критерий оптимальности опорного плана задачи: если при минимизации целевой функции все оценки переменных неположительные, то план оптимальный.
  1. Математическая модель задачи приведена к предпочтительному виду.
    Базисные переменные: $$x_1=50$$; $$x_3=5$$.
    Свободные переменные: $$x_2=0$$. 
  2. Составим симплексную таблицу (Таблица 1): 
        
  3. Заполним индексную строку (Таблица 2).
    Найдем значение целевой функции:
    $$\Delta_0=1\cdot 50+2\cdot 5=60$$.
    Найдем оценки переменных:
    $$\Delta_1=1 \cdot 1+ 2 \cdot 0 -1=0$$;
    $$\Delta_2=1 \cdot (-1)+ 2 \cdot 2 -5=-2$$;
    $$\Delta_3=1 \cdot 0+ 2 \cdot 1 -2=0$$. 
              
  4. Поскольку все оценки переменных неположительные, то опорный план оптимальный.
    Значения базисных переменных находятся в столбце $$A_0$$ (Таблица 3):
    $$x_1=50$$; $$x_3=5$$.
    Значения небазисных переменных равны нулю: $$x_2=0$$. 
            
  5. Решение задачи: $$X^*=(50;0;5)$$; $$f(X^*)=60$$.
  1. Оценки базисных переменных всегда равны нулю. 
  2. Значения базисных переменных находятся в столбце $$A_0$$. 
  3. Значения небазисных переменных всегда равны нулю.
Выберите несколько вариантов ответов
Решите симплексным методом задачу:
  1. $$maxf(X)=x_1+3x_2+2x_3$$; 
  2. $$\left\{\begin{matrix} x_1-x_2\leq4, \\ 2x_1+x_3=5, \\ 5x_1\leq1; \end{matrix}\right.$$ 
  3. $$x_i \geq0$$, $$i=\overline{1; 3}$$.
Симплексный метод
  1. Математическая модель задачи должна быть приведена к предпочтительному виду.
  2. Предпочтительные переменные являются базисными, а остальные переменные – свободными. Свободные переменные равны нулю.
  3. Чтобы найти значения базисных переменных, необходимо в систему ограничений подставить значения свободных переменных.
  4. Оценка целевой функции:
    $$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$.
  5. Оценки переменных:
    $$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$.
  6. Чтобы найти симплексные отношения, необходимо значения столбца $$A_0$$ разделить на соответствующие значения разрешающего столбца:
    $$\theta_j=\frac{b_{j}^{0}}{a_{jP}^{0}}$$.
    1. Приведем математическую модель задачи к каноническому и предпочтительному виду:
      $$maxf(X)=x_1+3x_2+2x_3+0x_4+0x_5$$;
      $$\left\{\begin{matrix} x_1-x_2+\underline{x_4}=4, \\ 2x_1+\underline{x_3}=5, \\ 5x_1+\underline{x_5}=1; \end{matrix}\right.$$
      $$x_i \geq0$$, $$i=\overline{1; 5}$$.
      Базисные переменные: $$x_4=4$$; $$x_3=5$$; $$x_5=1$$.
      Свободные переменные: $$x_1=0$$; $$x_2=0$$.
    2. Составим симплексную таблицу (Таблица 1):
                    
    3. Заполним индексную строку (Таблица 2).
      Значение целевой функции:
      $$\Delta_0=0 \cdot 4+2 \cdot 5+0\cdot 1=10$$.
      Оценки переменных:
      $$\Delta_1=0 \cdot 1+2 \cdot 2 +0\cdot 5-1 =3$$;
      $$\Delta_2=0 \cdot (-1)+2 \cdot 0 +0\cdot 0-3 =-3$$;
      $$\Delta_3=0 \cdot 0+2 \cdot 1 +0\cdot 0-2 =0$$;
      $$\Delta_4=0 \cdot 1+2 \cdot 0 +0\cdot 0-0 =0$$;
      $$\Delta_5=0 \cdot 0+2 \cdot 0 +0\cdot 1-0 =0$$.
                   
    4. Поскольку одна из оценок переменных отрицательная, то опорный план задачи не оптимальный. Следовательно, столбец $$A_2$$ разрешающий. Но так как отрицательные элементы разрешающего столбца и элементы, равные нулю, симплексных отношений не образуют, то оптимизировать целевую функцию нельзя.
      Задача не имеет оптимального решения.
    1. Канонический вид математической модели задачи.
      План: $$X=(x_1; x_2; . . . ; x_n)$$.
      Целевая функция:
      $$max (min) f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
      Система ограничений:
      $$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n=b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n=b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n=b_m. \end{cases}$$
      Условия неотрицательности переменных:
      $$x_i\geq 0$$, $$i=\overline{1, n}$$. 
    2. Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:
      1) к левым частям неравенств типа $$\leq$$ прибавить неотрицательные дополнительные переменные;
      2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
    Выберите несколько вариантов ответов
    Решите симплексным методом задачу:
    1. $$maxf(X)=x_1+5x_2+2x_3$$; 
    2. $$\left\{\begin{matrix} x_1-x_2=50, \\ 2x_2+x_3=5; \end{matrix}\right.$$ 
    3. $$x_i \geq0$$, $$i=\overline{1; 3}$$.
    Оценка целевой функции: 
    $$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$. 
    Оценки переменных: 
    $$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$. 
    Критерий оптимальности опорного плана задачи: если при максимизации целевой функции все оценки переменных неотрицательные, то план оптимальный. 
    Если опорный план задачи не удовлетворяет критерию оптимальности, то выполняем следующие действия. 
    Нулевая итерация симплексной таблицы.
    1. Выбираем наихудшую оценку переменной. В случае максимизации целевой функции – наименьшую отрицательную, а в случае минимизации – наибольшую положительную. Столбец, в которой находится эта переменная, называется разрешающим столбцом.
    2. Для каждой базисной переменной составляем симплексные отношения – находим отношения элементов столбца $$A_0$$ и соответствующих элементов разрешающего столбца. Из полученных отношений выбираем наименьшее. Строку, которой соответствует это отношение, называем разрешающей строкой.
    3. Элемент, который находится на пересечении разрешающих столбца и строки, называется разрешающим элементом $$a^0_{рр}$$.
    Первая итерация симплексной таблицы.
    1. Вносим изменения в базис: переменную, находящуюся в разрешающей строке нулевой итерации, заменяем переменной из разрешающего столбца.
    2. Все элементы разрешающей строки делим на разрешающий элемент и записываем в строку первой итерации (номер строки совпадает с номером строки нулевой итерации).
    3. Все остальные элементы столбца, номер которого совпадает с номером разрешающего столбца нулевой итерации, считаем равными нулю.
    4. Остальные элементы таблицы находим по правилу прямоугольника (Рис. 1): $$a_{ji}^{1}=\frac{a_{ji}^{0} \cdot a_{pp}^{0}-a_{jP}^{0} \cdot a_{Pi}^{0}}{a_{PP}^{0}}$$.
                                                                
                                                                                        Рис. 1
    Базисные переменные: $$x_1=50$$, $$x_3=5$$. 
    Свободные переменные: $$x_2=0$$. 
    Составим симплексную таблицу и выполним симплексные преобразования: 
                                         
     Пояснения к нулевой итерации.
    1. Заполняем индексную строку:
      $$\Delta_0=1 \cdot 50+ 2 \cdot 5 =60$$;
      $$\Delta_1=1 \cdot 1+ 2 \cdot 0 -1 =0$$;
      $$\Delta_2=1 \cdot (-1)+ 2 \cdot 2 -5 =-2$$;
      $$\Delta_3=1 \cdot 0+ 2 \cdot 1 -2 =0$$.
      Поскольку присутствуют отрицательные оценки переменных, то опорный план задачи не оптимальный.
    2. В качестве разрешающего столбца выбираем столбец $$A_2$$.
    3. Составляем симплексные отношения:
      $$\theta_1$$ не существует, так как $$a_{12}=-1<0$$; $$\theta_2=5:2=2,5$$.
    4. Вторая строка будет разрешающей. Разрешающий элемент $$a_{pp}=2$$.
    Пояснения к первой итерации.
    1. Вносим изменения в базис: переменную $$x_3$$ заменяем переменной $$x_2$$.
    2. Все элементы разрешающей строки нулевой итерации делим на $$a_{pp}=2$$ и результаты записываем во вторую строку первой итерации.
    3. Элемент $$a_{12}^{1}$$ считаем равным нулю.
    4. Остальные элементы первой строки находим по правилу прямоугольника: $$a_{10}^{1}=\frac{50 \cdot 2+5 \cdot 1}{2}=52,5$$;
      $$a_{11}^{1}=\frac{1 \cdot 2+0 \cdot 1}{2}=1$$;
      $$a_{13}^{1}=\frac{0 \cdot 2+1 \cdot 1}{2}=0,5$$.
    5. Заполняем индексную строку. Поскольку все оценки переменных первой итерации неотрицательные, то опорный план оптимальный:
       $$X^*=(52,5;2,5;0)$$; $$f(X^*)=65$$.
    1. Чтобы найти симплексные отношения, необходимо значения столбца $$A_0$$ разделить на соответствующие значения разрешающего столбца:
      $$\theta_j=\frac{b_{j}^{0}}{a_{jP}^{0}}$$.
    2. Отрицательные элементы разрешающего столбца и элементы, равные нулю, не образуют симплексных отношений.
    Выберите несколько вариантов ответов
    © Сиротина И.К., 2013—2026