Задачи линейного программирования

     Вычисление  вектора X = BY (3) производится с помощью операции умножения матриц, а в данном случае – умножения матрицы В на вектор Y. Для этого необходимо ячейки воспользоваться функцией МУМНОЖ. В открывшимся диалоговом окне появятся два свободных поля: Массив1 и Массив2. В Массив 1 заполняются данные матрицы В, а в Массив 2 вектор Y, после нажатия комбинации клавиш Ctrl+Shift+Enter, в соответствующих ячейках (D6:D7) появляется значение вектора Х.

     Следующим шагом решения задачи будет Вычисление межотраслевых поставок продукции x_ij. Межотраслевые поставки продукции xij вычисляются по формуле

     x_ij = a_ij x_j,          (4)

     где a_ij – элементы матрицы А, расположенной в ячейках A2:B4, x_j – элементы вектора Х, найденного выше и расположенные в ячейках D6:D7. Для проведения вычислений xij необходимо проделать следующее.

     1. Вычислить транспонированный вектор  Х^т относительно вектора Х. При этом вектор-столбец Х станет вектором-строкой Х^т. Это необходимо для согласования размерностей дальнейшего умножения элементов векторов. Для этого воспользуемся функцией ТРАНСП. В появившемся диалоговом окне ТРАНСП введем данные вектор Х (диапазон ячеек D6:D7) в рабочее поле Массив и после нажатия сочетания клавиш Ctrl+Shift+Enter увидим в соответствующих ячейках (D10:E10) транспонированный вектор Х^т.

     2. Вычислим межотраслевые поставки продукции x_ij . Для этого проделать следующие операции:

     - в ячейке A12, в которой будет расположено значение x₁₁, необходимо набрать формулу =А2*D10, которая означает, что x₁₁ = a₁₁ *x₁ .Аналогично заполняются все ячейки массива A18:B19.

     В результате все межотраслевые поставки продукции будут найдены и  расположатся в матрице с ячейками A18:B19. Они показывают самый оптимальный вариант решения задачи. 

     

     Ответ:  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Задача 4.

     Задача линейного программирования симплексным методом

     Условие. Решить задачу линейного программирования симплексным методом. Найти максимум функции:

            F(X) = 3X₁ + 5X₂

  Х₁ + 5Х₂ > 5

  ЗХ₁ - Х₂   < 3,

  2Х₁ - ЗХ₂ > -6,

  Х₁ >0, Х₂  > 0. 

     Решение.

     Решим прямую задачу линейного программирования симплекс-методом.  Поскольку в  правой части присутствуют отрицательные  значения, умножим соответствующие  строки на (-1). Определим максимальное значение целевой функции F(X) = 3x₁+5x₂ при следующих условиях-ограничениях:

x₁+x₂≥5

3x₁-x₂≤3

-2x₁+3x₂≤6

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

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ = 5

3x₁-1x₂ + 0x₃ + 1x₄ + 0x₅ = 3

-2x₁ + 3x₂ + 0x₃ + 0x₄ + 1x₅ = 6

     Введем  искусственные переменные x.

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ + 1x₆ = 5

3x₁-1x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 3

-2x₁ + 3x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 6

     Для постановки задачи на максимум целевую  функцию запишем так:

F(X) =  - Mx₆ => max

     Из  уравнений выражаем искусственные  переменные:

  x₆ = 5-x₁-x₂+x₃ ,

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

 F(X) = (1M)x₁+(1M)x₂+(-1M)x₃+(-5M) => max

     Введем  новую переменную x₀ = x₁+x₂.

     Выразим базисные переменные <6, 4, 5> через  небазисные.

x₀ = -5+x₁+x₂-x₃

x₆ = 5-x₁-x₂+x₃

x₄ = 3-3x₁+x₂

x₅ = 6+2x₁-3x₂

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

x₀ = -5+x₁+x₂-x₃

x₆ = 5-x₁-x₂+x₃

x₄ = 3-3x₁+x₂

x₅ = 6+2x₁-3x₂

     В качестве новой переменной выбираем x₂. Вычислим значения D₂ по всем уравнениям для этой переменной. 

 и из них  выберем наименьшее: 

     Вместо переменной x₅ в план войдет переменная x₂. Выразим переменную x₂ через x₅ и подставим во все выражения. После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x₀ = -3+1.67x₁-x₃-0.3333x₅

x₆ = 3-1.67x₁+x₃+0.3333x₅

x₄ = 5-2.33x₁-0.3333x₅

x₂ = 2+0.6667x₁-0.3333x₅

     Полагая небазисные переменные x = (6, 4, 2) равными  нулю, получим новый допустимый вектор и значение целевой функции:

x = (-1.67, 0, 1, 0, 0.3333, 0), x₀ = -3

x₀ = -3+1.67x₁-x₃-0.3333x₅

x₆ = 3-1.67x₁+x₃+0.3333x₅

x₄ = 5-2.33x₁-0.3333x₅

x₂ = 2+0.6667x₁-0.3333x₅

     В качестве новой переменной выбираем x₁. Вычислим значения D₁ по всем уравнениям для этой переменной. 

и из них выберем  наименьшее: 

     Вместо  переменной x₆ в план войдет переменная x₁. Выразим переменную x₁ через x₆ и подставим во все выражения. После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x₀ = -0-0x₃-0x₅-1x₆

x₁ = 1.8+0.6x₃+0.2x₅-0.6x₆

x₄ = 0.8-1.4x₃-0.8x₅+1.4x₆

x₂ = 3.2+0.4x₃-0.2x₅-0.4x₆

     Полагая небазисные переменные x = (1, 4, 2) равными  нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 0, 0, 0, 1), x₀ = -0

     Выражение для x₀ не содержит положительных элементов. Найден оптимальный план.

x₀ = -0-0x₃-0x₅-1x₆

x₁ = 1.8+0.6x₃+0.2x₅-0.6x₆

x₄ = 0.8-1.4x₃-0.8x₅+1.4x₆

x₂ = 3.2+0.4x₃-0.2x₅-0.4x₆

     На  этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.

x₁ = 1.8+0.6x₃+0.2x₅

x₄ = 0.8-1.4x₃-0.8x₅

x₂ = 3.2+0.4x₃-0.2x₅

     Выразим базисные переменные:

x₁ = 1.8+0.6x₃+0.2x₅

x₂ = 3.2+0.4x₃-0.2x₅ ,

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

F(X) = 3(1.8+0.6x₃+0.2x₅) + 5(3.2+0.4x₃-0.2x₅)

 или

F(X) = 21.4+3.8x₃-0.4x₅

     Получаем  новую систему переменных.

x₀ = 21.4+3.8x₃-0.4x₅

x₁ = 1.8+0.6x₃+0.2x₅

x₄ = 0.8-1.4x₃-0.8x₅

x₂ = 3.2+0.4x₃-0.2x₅

 

x₀ = 21.4+3.8x₃-0.4x₅

x₁ = 1.8+0.6x₃+0.2x₅

x₄ = 0.8-1.4x₃-0.8x₅

x₂ = 3.2+0.4x₃-0.2x₅

     В качестве новой переменной выбираем x₃. Вычислим значения D₃ по всем уравнениям для этой переменной. 

 и из них  выберем наименьшее: 

     Вместо  переменной x₄ в план войдет переменная x₃. Выразим переменную x₃ через x₄ и подставим во все выражения. После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x₀ = 23.57-2.71x₄-2.57x₅

x₁ = 2.14-0.4286x₄-0.1429x₅

x₃ = 0.5714-0.7143x₄-0.5714x₅

x₂ = 3.43-0.2857x₄-0.4286x₅

     Полагая небазисные переменные x = (1, 3, 2) равными  нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, -0, 2.71, 2.57), x₀ = 23.5714

     Выражение для x₀ не содержит положительных элементов. Найден оптимальный план. Окончательный вариант системы уравнений:

x₀ = 23.57-2.71x₄-2.57x₅

x₁ = 2.14-0.4286x₄-0.1429x₅

x₃ = 0.5714-0.7143x₄-0.5714x₅

x₂ = 3.43-0.2857x₄-0.4286x₅

     Оптимальный план можно записать так:

x₁ = 2.14

x₃ = 0.5714

x₂ = 3.43

F(X) = 3*2.14 + 5*3.43 = 23.57. 
 
 
 
 
 
 
 
 

Список  использованной литературы

1. http://simplex-metod.narod.ru/real/prumery/page_4.html;
2. http://www.reshmat.ru/example_simplex_1.html;
3. Мадера А.Г. курс Математические модели в управлении – М:2005;
4. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004.