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

                                                    66


                              x11 ≥ 0, x12 ≥ 0,..., x1n ≥ 0;
                             x21 ≥ 0, x22 ≥ 0,..., x 2 n ≥ 0;
                                                                    (11)
                                .................................
                             xm1 ≥ 0, xm 2 ≥ 0,..., x mn ≥ 0.
        Таким образом, (8) – (11) составляют математическую модель расстановочной задачи. Она
совершенно аналогична предыдущим моделям. Несущественное отличие здесь заключается в том,
что часть ограничений (9) выражается неравенствами, а другая часть (10) – равенствами. Если бы
Q1, Q2,…, Qn представляли нижние границы объемов перевозок на линиях (надо выполнить не
меньше чем Q1, Q2,…, Qn тонно-километров на данных линиях), то ограничения (10) также
выразились бы неравенствами:
                              P1jx1j+P2jx2j+…+Pmjxmj ≥ Qj (j=1, 2,…, n).
        Замечание. В литературе по линейному программированию расстановочная задача
встречается под названием «обобщенная транспортная задача». Задачу, приводящую к модели (8)
– (11), называют обобщенной транспортной, т.к. структура ее ограничений (9) – (10) аналогична
структуре ограничений (5) – (6). Обобщение заключается в том, что коэффициенты в группе
ограничений (10) могут принимать любые значения, тогда как в группе ограничений (6) они все
равны единице.
        Расстановочная задача является частным случаем распределительной задачи.
Распределительная задача заключается в рациональном распределении m видов изделий для
изготовления их на n скооперированных предприятиях с целью, например, достижения максимума
выпускаемой продукции.


                4.6.1.3. Классификация задач линейного программирования

        Практические вопросы, приводящие к задаче линейного программирования разнообразны.
Но и приведенных выше примеров достаточно для понимания математической структуры задачи
линейного программирования и ее значения на практике. Проведем классификацию этих задач.
        Во-первых, различают общую задачу математического программирования и специальные
задачи. При этом имеют в виду, что в некоторых задачах структура матрицы технологических
коэффициентов (т.е. коэффициентов в ограничениях) имеет специфические особенности. Так,
например, в транспортной задаче, если выписать столбец коэффициентов, относящихся к
некоторой переменной xij , то он состоит из одних нулей, кроме i-го и (m+j)-го места, где стоят
единицы. Специфично также строение матрицы технологических коэффициентов расстановочной
задачи. Для таких задач можно, используя указанные особенности, создать специальные методы
решения, и поэтому задачи называют специальными. Если не принимается во внимание структура
матрицы технологических коэффициентов, то говорят об общей задаче линейного
программирования. В первую очередь надо, конечно, изучить общую задачу, т.к. методы ее
решения имеют общий характер, и они только специализируются при рассмотрении задач с
особенностями.
        Во-вторых, в настоящее время разработаны методы решения общей задачи линейного
программирования при некоторых отклонениях от рассмотренных нами моделей или при
некоторых дополнительных требованиях.
        Так, разработаны методы решения общей задачи линейного программирования с учетом
следующих обстоятельств:
        а) коэффициенты целевой функции не являются постоянными, а меняются линейно в
зависимости от некоторого дополнительного параметра, так что целевая функция имеет вид
                             Z=(c1+d1t)x1+(c2+d2t)x2+…+(cn+dnt)xn,
        где t – дополнительный параметр (например, время). В этом случае говорят о задаче
параметрического линейного программирования;
      б) ограничения, наложенные ресурсами, выражаются двусторонними неравенствами. Они
имеют вид
                          ai ≤ ai1x1+ai2x2+…+ainxn ≤ bi (i=1, 2,…, m)