Численные методы. Корнюшин П.Н. - 63 стр.

                                                      63


                                   a11 x1 + a12 x 2 + ... + a1n xn ≤ b1 ;
                                   a 21 x1 + a 22 x 2 + ... + a 2 n xn ≤ b2 ;
                                       ......................................
                                  a m1 x1 + a m 2 x2 + ... + amn x m ≤ bm .
       Наконец, числа x1, x2,…, xn, выражающие намеченный план, должны быть
неотрицательными, что достаточно очевидно, но должно быть отмечено отдельно для полноты и
точности математической формулировки поставленной задачи. Итак, мы пришли к следующей
математической задаче: найти такие числа x1, x2,…, xn, при которых достигается максимум
линейной функции
                           Z=c1x1+c2x2+…+cnxn → max,       (1)
удовлетворяются линейные неравенства
                              a11 x1 + a12 x2 + ... + a1n xn ≤ b1 ;
                              a 21 x1 + a 22 x2 + ... + a 2 n xn ≤ b2 ;
                                                                                (2)
                                  ......................................
                             a m1 x1 + am 2 x 2 + ... + a mn xm ≤ bm .
и все переменные неотрицательны:
                                x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0.      (3)
          Эта задача (1) – (3) и составляет математическую модель линейного программирования.
Она возникла на примере из области производственного планирования.
          Замечание 1. Можно было бы поставить целью планирования получение максимального
дохода. При этом получалась бы та же модель (1) – (3), но символы, обозначающие заданные
переменные величины, уже имели бы другой смысл.
          Во-первых, необходимо иметь данные о доходности каждого технологического способа
при выпуске единицы готовой продукции; пусть это будут величины cj для способа Tj (j=1, 2,…, n),
т.е. cj будет теперь обозначать доход на одно готовое изделие, созданное по способу Tj.
          Во-вторых, за параметры управления x1, x2,…, xn, составляющие намечаемый план, следует
теперь взять числа, показывающие, сколько единиц продукции планируется выпустить по
каждому из способов Tj.
          В-третьих, в качестве технологических коэффициентов теперь следует иметь данные о
затратах каждого из производственных факторов Фi при выпуске одной единицы готовой
продукции по способу Tj , так что теперь aij будет обозначать число единиц фактора Фi,
затраченное при выпуске одного изделия по способу Tj. При этом новом значении букв cj, xj, aij
математическая схема, как легко видеть, получится та же самая, но теперь модель (1) – (3) уже
будет выражать стремление к максимальной доходности.
          Замечание 2. Мы рассматривали наиболее простую задачу из области производственного
планирования. Задача сразу усложняется, если готовая продукция составляется из нескольких
компонентов (изделий), которые должны входить в каждую единицу продукции в
соответствующих пропорциях. В этом случае возникают дополнительные требования,
относящиеся к комплектности, ассортиментности и т.д. Задача усложняется и тогда, когда
предприятие выпускает продукцию разного вида. Однако математическая модель в этих более
сложных задачах получается, по существу, такая же.
          Замечание 3. Первой практической задачей, заложившей основы линейного
программирования, была так называемая «задача фанерного треста». Она была решена
академиком Л.В. Канторовичем, который затем в 1939 г. выступил с основополагающей работой
по линейному программированию под названием «Математические методы организации и
планирования производства» (ЛГУ, 1939).

                                      2. Транспортная задача

        Имеется m пунктов отправления A1, A2,…, Am, из которых надо вывезти однородный груз в
количествах a1, a2,…, am тонн (соответственно). Этот груз предназначен для n пунктов назначения
B1, B2,…, Bn, потребности которых составляют соответственно b1, b2,…, bn тонн. Известно, что