Модели линейного программирования. Задача планирования производства

                     …………………………………….

                     а_k1  × x₁ + а_k2  × x₂ + … + а_kn  × x_n £ b_k,

                       а_k+1,1  × x₁ + а_k+1,2  × x₂ + … + а_k+1,n  × x_n = b_k+1,

                     ……………………………………..

                     а_m1  × x₁ + а_m2  × x₂ + … + а_mn  × x_mn = b_m, 

   Функция называется  целевой функцией задачи, а условия – ограничениями данной задачи.

   Совокупность значений переменных Х₁, Х₂, …, Х_n, удовлетворяющих условиям задачи, называется допустимым решением, или планом. План X* = ( , , … ), при котором целевая функция задачи принимает экстремальное значение, называется оптимальным.

   1.3 Стандартная (симметричная) задача линейного программирования

   Стандартной задачей линейного программирования называют задачу, в которой требуется найти такие значения Х₁, Х₂, …, Х_n, при которых функция цели принимает максимальное значение

   

   f(x) = ® max            (4)

   и которые удовлетворяют ограничениям 

     £ b_i; (i = ),            (5)

   Х_j ³ 0; (j = ).                (6)

   1.4 Каноническая (основная) задача линейного программирования

   Канонической  задачей называется задача, в которой требуется найти такой набор переменных Х₁, Х₂, …, Х_n, который позволяет максимизировать функцию цели

   f(x) = ® max            (7)

   и удовлетворяет системе ограничений

   

     = b_i; (i = ),            (8)

   Х_j ³ 0; (j = ).                (9)

   1.5 Представление задачи линейного программирования в канонической форме

   Пусть требуется найти неотрицательные значения переменных Х₁, Х₂, …, Х_n, для которых функция цели принимает максимальное значение

   f(x) = C₁ Х₁ + C₂Х₂ + …+ C_nХ_n ® max

   при ограничениях

   

                         
 

   Х_j ³ 0, (j =

). 
 

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

   Найти максимум функции цели

   f(x) = C₁ Х₁ + C₂Х₂ + …+ C_nХ_n + …+ 0×Х_n+1 + …+ 0×Х_n+m ® max

   при ограничениях

     
 

   Х_j ³ 0, (j =

).

   Пример. Записать следующую задачу в канонической форме:

               f(x) = -X₁ + 2X₂ - X₃ + X₄® min,

                             3X₁ - X₂ + 2X₃ + 2X₄ £ 10,

                            X₁ + 2X₂ + X₃ - X₄ ³ 8,

                            2X₁ - X₂ - X₃ + X₄ £ 6,

                            

                            -X₁ + 3X₂ + 5X₃ - 3X₄ = 15,

   X_j ³ 0, (j = 1 ¸ 4).

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

    f(x) = Х₁ - 2Х₂ + Х₃ - Х₄ + 0×Х₅ + 0×Х₆ + 0×Х₇ ® max,

                      3X₁ - X₂ + 2X₃ + 2X₄ + X₅ = 10,

                      X₁ + 2X₂ + X₃ - X₄  - X₆       = 8,

                      2X₁ - X₂ - X₃ + X₄   + X₇  = 6,

                    -X₁ + 3X₂ + 5X₃ - 3X₄    = 15,    X_j ³ 0.

   1.6 Свойства задачи линейного программирования

         1. Множество планов  задачи линейного программирования, если оно не пусто, образует  выпуклый многогранник. Любая точка  внутри области, ограниченной  этим многогранником, является допустимым  решением задачи.

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

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

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

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

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

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

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

   Симплекс-метод  применяется к задаче, записанной в канонической форме (используем одну из двойственных задач линейного программирования):

   f(x) = 10Х₁ + 14Х₂ + 12Х₃ + 0×Х₄ + 0×Х₅ + 0×Х₆ ® max,

    4X₁ + 2X₂ + X₃ + X₄          = 180,

   3X₁ + X₂ + 3X₃  + X₅         = 210,

   X₁ + 2X₂ + 5X₃        + X₆ = 244.

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

   В первом столбце вписаны базисные неизвестные, второй содержит коэффициенты при базисных неизвестных в целевой  функции, в третьем – правые части  уравнений системы ограничений. Далее записана матрица из коэффициентов левой части системы ограничений ( ). В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции. В последней строке записывается значение целевой функции при данном опорном плане, которое вычисляется по формуле f(x) = , и далее – оценки неизвестных, найденные по формуле D_j = - C_j. Если среди оценок D_j есть отрицательные, то опорный план не является оптимальным и значение целевой функции можно улучшить.  

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

оценкой.

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

   Пересчет  таблицы производится по следующему правилу: элементы ключевой строки делятся  на ключевой элемент. Далее, с помощью  метода Жордана Гаусса проводят пересчет таблицы таким образом, чтобы  элементы ключевого столбца имели единицу на месте ключевого элемента и нули на месте всех остальных элементов. Для этого вычтем из элементов третьей строки соответствующие элементы первой строки, а из элементов второй строки – элементы первой строки, поделенные на два (на ключевой элемент).

   

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

   Для каждого шага итерации строится своя симплексная таблица: