Содержание

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

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

       1) показатель эффективности (целевая функция F) линейно зависит от элементов решения x₁,x₂,…,x_n и

       2) ограничения, налагаемые  на элементы решения, имеют  вид линейных равенств или  неравенств относительно x₁,x₂,…,x_n .

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

       Математически задача может быть сформулирована следующим  образом: определить оптимальное значение целевой функции:

       

 
                          (1.1)

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

       

       (1.2)

       

       (1.3)

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

       Если  в задаче (1.1)-(1.3) ограничения (1.2) представлены в виде равенств, то задача носит название «Основная задача  линейного программирования» (ОЗЛП).

       Кроме записи ОЗЛП с помощью знаков суммирования используют и другие способы представления  задачи.

       1.2 Геометрическая  интерпретация задачи

 

       Составим  математическую модель следующей задачи. Пусть в цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19/3 м² площади. На приобретение оборудования предприятие может израсходовать 10 тысяч рублей, при этом оно может купить оборудование двух видов. Комплект оборудования первого вида стоит 1000 рублей, а второго вида – 3000 рублей. Приобретение одного комплекта оборудования первого вида позволяет увеличить выпуск продукции в смену на две единицы, а одного комплекта оборудования второго вида – на четыре единицы. Зная, что для установки одного комплекта оборудования первого вида требуется 2 м² площади, а оборудования второго вида – 1 м² площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

       Предположим, что предприятие приобретет x₁ комплектов оборудования первого вида и x₂ комплектов оборудования второго вида. Тогда переменные x₁ и x₂ должны удовлетворять следующим неравенствам: 

                                                                               (1.4) 

       Если  предприятие приобретет указанное  количество оборудования, то общее  увеличение выпуска продукции составит 

        .                                                                         (1.5) 

       По  своему экономическому содержанию переменные x₁ и x₂ могут принимать лишь целые неотрицательные значения, то есть 

       x₁, x₂ ³ 0,                                                                              (1.6) 

        x₁, x₂ – целые.                                                                                (1.7)

       Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (1.5) при выполнении условий (1.4, (1.6) и (13). Так как неизвестные могут принимать только целые значения, то задача (1.4) – (1.7) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум, решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого строится многоугольник решений задачи, состоящий в определении максимального значения линейной функции (1.5) при выполнении условий (1.4) и (1.6) (рисунок 1.1). 

       

       Рисунок 1.1 – Геометрическая интерпретация задачи 

       Координаты всех точек построенного многоугольника решений OABC удовлетворяют системе линейных неравенств (1.4) и условию неотрицательности переменных (1.6). Вместе с тем условию (1.7), то есть условию целочисленности переменных, удовлетворяют координаты лишь 12 точек, отмеченных на рисунке 1.1. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник OABC многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами. Значит, если найти точку максимума функции (1.5) на многоугольнике OKEMNF, то координаты этой точки и определят оптимальный план задачи.

       Для этого построим вектор и прямую 2x₁+4x₂=0. построенную прямую передвигаем в направлении вектора до тех пор, пока она не пройдет через последнюю общую точку ее с данным многоугольником. Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является максимальным.

       В данном случае искомой является точка  E(1,3), в которой целевая функция принимает максимальное значение . Следовательно, координаты точки E определяют оптимальный план задачи (1.4) – (1.7). В соответствии с этим планом предприятию следует приобрести один комплект оборудования первого вида и три комплекта оборудования второго вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 единиц в смену.

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

 
 

         Пусть дана система n линейных уравнений с m переменными (n<m). 

         (1.8) 

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

         

       Тогда систему (1.8) можно разрешить относительно переменных x₁, x₂, …,x_n которые, как и раньше, будем называть базисными переменными. В результате решения системы (1.8) базисные переменные будут выражены через остальные переменные x_n+1, x_n+2, …, x_m, называемые свободными. Число свободных переменных k=m-n. Мы имеем решение системы (1.8) в виде: 
 
 

          (1.9) 

       Свободные переменные остаются произвольными. Давая  им различные значения, получим все  решения системы (1.8). Одно из решений найдем, если все свободные переменные приравняем к нулю. Тогда получим: 

       x₁=b₁, x₂=b₂, …, x_n=b_n; x_n+1=x_n+2=…=x_m=0 

       Если  все числа b₁, b₁, …,b_n неотрицательны, то мы будем иметь неотрицательное решение системы (1.8), соответствующее угловой точке (вершине) многогранника неотрицательных решений, это так называемое опорное решение.

       Решить  систему относительно базисных переменных x₁, x₂, …,x_n, используя свойства определителей n-го порядка, очень удобно. Мы будем решать эту систему путем последовательного исключения неизвестных.

       Запишем в виде таблицы коэффициенты уравнений (1.10) и элемент a₁₁ заключим в рамку 

                (1.11) 

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

       Выпишем соответствующую таблицу для  коэффициентов уравнений  

                   (1.12) 

       Коэффициент a’₂₁ равен нулю

       Из  уравнения (3.25) следует, что 

                        (1.13) 

       На  таблице (1.11) соединим элемент a_2j c разрешающим элементом прямой линией. Рассмотрим прямоугольник, диагональю которого является проведенная линия. Эту диагональ будем называть первой диагональю. Второй диагональю является прямая, соединяющая элементы a₂₁ и a_1j, обведенные кружком. Как следует из формулы (1.13), чтобы получить элемент a_2j, нужно из произведения элементов первой диагонали вычесть произведение второй диагонали. Остальные элементы второй строки вычисляются по этому же правилу. Это правило напоминает правило вычисления детерминантов второго порядка, поэтому будем коротко называть его D-правилом.

       Переход от таблицы коэффициентов (1.11) к таблице (1.12), совершаемый с помощью D-правила, будем называть симплекс преобразованием или S-преобразованием одной таблицы в другую.

       Очевидно, для выполнения S-преобразования с помощью первого уравнения необходимо, чтобы коэффициент a₁₁¹0 в противном случае переменная x₁ в первом уравнении будет отсутствовать.

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

               (1.14) 

       Если  a₁₁¹0, и мы хотим исключить x₁ с помощью первого уравнения, то принимаем элемент a₁₁ за разрешающий и в таблице (1.14) обводим его рамкой. Строка и столбец, в которых находится разрешающий элемент, называются соответственно разрешающей строкой и разрешающим столбцом. В таблице (1.14) это первая строка и первый столбец.

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

       Остальные элементы новой таблицы вычисляются  по D-правилу. Например, для вычисления элемента a’_ij соединяем элемент a_ij на таблице (1.14) с элементом a₁₁ прямой. В результате имеем первую диагональ. Вторая диагональ получается от соединения элементов a_i1 и a_1j, обведенных на таблице кружками. По D-правилу имеем 

          

       При выполнении симплекс преобразования диагонали, изображенные на таблице (1.14), на самом деле проводить не нужно: они легко выделяются в уме.

       Выполнив  S-преобразование над таблицей (1.14), мы получим новую таблицу 

                 (1.15) 

       Этой  таблице соответствует система  уравнений: 
 
 

               (1.16) 

       Система (1.16) эквивалентна первоначальной системе (1.8), но в системе (1.16) переменная x₁ исключена из всех уравнений, кроме первого. Если в таблице (1.15) элемент a’₂₂¹0, то, приняв его за разрешающий элемент и проделав над таблицей (1.15) S-преобразование, получим новую таблицу. И в системе уравнений, соответствующей этой таблице, переменная x₂ будет исключена из всех уравнений, кроме второго.

       Если  в таблице (1.15) a’₂₂=0, то во втором столбце найдем элемент, не равный нулю, и примем его за разрешающий. Пусть это будет a’₁₂. Тогда выполняя симплекс преобразование над таблицей (1.15), мы исключим x₂ из всех уравнений, кроме i-того. Продолжая так дальше, мы после n преобразований придем к таблице, имеющей, например, следующий вид. 

            (1.17) 

       Таблице (1.17) соответствует система уравнений, эквивалентная первоначальной системе. Эта система уравнений имеет вид: 

            (1.18) 

       Можно считать, что система (1.18) решена относительно базисных переменных x₁, x₂, …, x_n. Переносить члены, соответствующие свободным переменным, в правую часть для фактического решения системы (1.18) относительно базисных переменных не будем, так как в дальнейшем нас будет интересовать решение, где все свободные переменные равны 0.