korobov

31

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

Доля транспорта в общем объеме производственных фондов России в настоящее время составляет около 20°/о. Непосредственно в транспортных отраслях занято более 10% рабочих и служащих. Если же учесть труд, связанный с выполнением транспортных функций в других отраслях народного хозяйства, а также затраты труда в отраслях, непосредственно обслуживающих транспорт эта цифра возрастает вдвое. Можно считать, что на пространственное перемещение грузов как в специально транспортной отрасли, так

ив других отраслях народного хозяйства России затрачивается примерно одна пятая совокупного общественного труда.

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

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

Итак, приступим к постановке транспортной задачи в общем виде.

Условие задачи. Допустим в пунктах А1, А2, .., Аm производится некоторая однородная продукция (сырье, материалы и т. п. В дальнейшем будем именовать — продукция). Таким образом, имеются m поставщиков Аi. Объем производства в пункте Ai,

составляет ai единиц. Следовательно, величину ai можно назвать

m

мощностью поставщика, а ∑ a i — суммарной мощностью всех m поставщиков.

i = 1

Предположим, что указанная продукция потребляется в пунктах В1,В2, . . ., Вn, причем объем потребления в пункте Вj, составляет bj единиц продукции. В дальнейшем

32

В данном случае мы имеем матрицу стоимости перевозок. Сокращенно матрицу можно записать:

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

Матрицу стоимости перевозок, которая дана в условии задачи, и искомую матрицу перевозок также можно представить а одной табл.1.4. В этой таблице стоимости перевозок записываются в верхнем левом углу каждой клетки.

33

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

Суммарные затраты на поставку продукции можно выразить в виде уравнения

Если далее все х сложить по строкам (см.табл.1.4), то сумма их должна быть равна мощности поставщиков - аi:

Сумма переменных х по столбцам равняется емкости потребителей - bj:

Таким образом, в виде систем линейных уравнений (1.28), (1.29) мы получили ограничительные условия транспортной задачи, которым должны удовлетворять искомые переменные хij.

При этом все неизвестные должны быть неотрицательными, т.е.

неотрицательные значения неизвестных хij, при которых целевая функция (1.27)

достигнет минимальной величины.

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

Необходимо найти неотрицательные значения неизвестных хij, минимизирующие целевую функцию

34

Вусловии (1.32) записано, что суммарный объем поставки продукции всем n потребителям от конкретного поставщика i должен быть равен количеству продукции, предназначенной к поставке от этого i-го поставщика, т.е. его мощности.

Всистеме уравнений (1.33) отражено условие полного удовлетворения спроса потребителей: суммарный объем поставки продукции от всех m поставщиков конкретному j-му потребителю должен быть равен емкости (спросу) этого потребителя.

Вограничительных условиях транспортной задачи (1.28), (1.29) содержится m+n

уравнений с m×n неизвестными, причем одно из уравнений является следствием остальных в силу условия

Следовательно, в системе (1.28), (1.29) линейно независимых уравнений будет m+n- 1 (это называют рангом системы - r), и каждый опорный план (программа) должен содержать не более чем m+n-1 положительных перевозок.

Если число положительных перевозок хij равно m+n-1, то такой опорный план (программа) оказывается невырожденным. В случае, когда часть базисных компонент (перевозок) плана нули, то такой план является вырожденным.

Для каждого невырожденного опорного плана в матрице перевозок X=(xij) должно быть m+n-1 заполненных числами xij клеток. Остальные клетки остаются пустыми.

Заполненные в матрице перевозок клетки называются базисными, не заполненные -

свободными.

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

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

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

Динамическое программирование представляет собой вычислительный метод решения некоторых типов задач нелинейного программирования, а также некоторых задач линейного программирования с требованием целочисленности аргументов. Основателем динамического программирования является американский математик Р.Беллман. Введенный им термин "динамическое программирование" возник в результате изучения задач, в которых были существенные изменения во времени. Однако этот метод может быть использован в задачах, где время вообще не фигурирует.

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

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

35

ряд шагов искусственно, решением задачи является оптимальное управление, найденное на последнем шаге.

Рассмотрим пример естественно многошагового процесса. Пусть планируется работа группы разнородных промышленных предприятий, входящих в объединение

П1, П2,…,Пn

на один хозяйственный год. Конечной задачей планирования является получение максимальной прибыли от реализации некоторого вида продукции Р, производимой этими предприятиями. В начале периода имеется определенный запас х0 денежных ресурсов С (или других ресурсов), необходимых для изготовления продукции Р. На каждом предприятии Пj известны производственные возможности использования денежных ресурсов С с учетом использования оборудования и других факторов.

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

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

Под управлением Vi на i-ом шаге операции следует понимать распределение количества денежных средств С

n

xi = ∑xij , j=1

имеющихся к этому времени. Таким образом, управление на i-ом шаге состоит в том, что предприятию П1 выделяется хi1 финансов, предприятию П2 - хi2 финансов С и т.д.

V1 = (x11, x12 ,......, x1n ),

V2 = (x21 , x22 ,......, x2n ),

V3 = (x31, x32 ,......, x3n ),

V4 = (x41 , x42 ,......, x4n ),

от которых зависит суммарный доход

W = W (V1,V2 ,V3 ,V4 ).

Задача состоит в том, чтобы так выбрать все эти четыре управления, т.е. так распределить денежные средства С между предприятиями в начале каждого квартала, чтобы величина W, зависящая от управлений Vi, приняла максимальное значение. Каждое управление Vi (i=1,2,3,4), при котором получается максимум величины W, называется оптимальным управлением (стратегией) на соответствующем шаге операции.

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

36

Глава 2. ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ И ТЕОРИИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Часть 1. ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ

В главе I было показано, что ограничения канонической задачи линейного программирования представляют собой систему линейных уравнений, в которой число уравнений т не совпадает с числом неизвестных п. В практических задачах линейного программирования всегда m<n. Исследование систем линейных уравнений общего вида удобно производить, оперируя понятиями матриц и m-мерных векторов. Элементарному изучению матриц, векторов и систем линейных уравнений при т<п посвящается эта глава.

2.1.1. Матрицы и операции над ними

Матрицей А размеров mxn называется прямоугольная таблица чисел:

матрицы А. Элемент aij , находится на пересечении i-й строки и j-го столбца.

Для обозначения матрицы, как правило, применяются квадратные скобки [ ], круглые скобки ( ) или двойные вертикальные черточки , которыми заключаются прямоугольные таблицы чисел.

соответствующие элементы, т. е. aij =bij, при всех i и j.

Если число строк равно числу столбцов (m=n), то такая таблица называется квадратной матрицей п-го порядка. Она записывается кратко следующим образом:

А= [aij ]n .

Главной диагональю квадратной матрицы, называется диагональ, проходящая через верхний левый и нижний правый углы, т. е. совокупность элементов aij .

Квадратная матрица, у которой все элементы, расположенные вне главной диагонали, равны нулю, называется диагональной.

Диагональная матрица, у которой все диагональные элементы равны единице ( aij =1 при всех i), называется единичной матрицей.

Обозначим ее через Е:

В матричном исчислении рассматривается операция произведения матриц. Однако этого вопроса мы касаться не будем.

2.1.2. Векторы и операции над ними

Матрица размеров т х I, т. е. состоящая из одного столбца с m элементами

называется m-мерным вектором-столбцом. Величины аi называются компонентами вектора A.

В дальнейшем под вектором, или, точнее, m-мерным вектором, будем понимать

упорядоченную совокупность m действительных чисел,

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

В обычном трехмерном пространстве любой радиус-вектор (направленный отрезок, исходящий из начала координат) вполне определяется упорядоченной тройкой чисел x1, x2, x3, которые являются координатами конца этого вектора. Поэтому можно сказать, что трехмерный вектор — это то же, что упорядоченный набор трех действительных чисел. Понятие m-мерного вектора есть обобщение понятия трехмерного вектора, отсюда и сохранение названия вектор.

Компоненты m-мерного вектора можно рассматривать как координаты некоторой точки в воображаемом m-мерном пространстве Rm, т. е, каждому m-мерному вектору соответствует точка в Rm, и, наоборот, каждой точке в Rm соответствует m-мерный вектор. Текущей точке с координатами x1, x2,…, xm соответствует переменный вектор X = [x1, x2,…, xm ] и наоборот.

Началу координат соответствует нулевой вектор: 0=[0, 0, . . . , 0].

Совокупность всех m-мерных векторов называют т-мерным векторным пространством или просто т-мерным пространством.

В m-мерном пространстве содержится равно m единичных векторов:

39

У единичного вектора еi, i-я компонента равна единице, а остальные — нули. Единичный вектор еi одновременно является i-й строкой и i-м столбцом единичной матрицы (2.1.3).

Эти векторы обобщают понятие единичных векторов в трехмерном пространстве, направленных по координатным осям.

Сравниваются векторы так же, как и матрицы, поскольку они являются частным случаем матриц. Два вектора A = [a1, a2, ..., am] и B = [b1, b2, …, bm] считаются равными, если равны их соответствующие координаты, т. е. если А=В, то a1=b1; а2=b2;...; am=bm и наоборот.

Матрицу A размером mxn (2.1.1) можно разложить на п m-мерных векторовстолбцов

В дальнейшем всегда буква А с индексом j будет обозначать j-и столбец матрицы. Говорят, что вектор задан, если известны числовые значения его компонент.

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

При транспонировании вектор-столбец переходит в вектор-строку и наоборот.

Умножение вектора Х на действительное число λ сводится к умножению на это число всех компонент вектора. При λ >1 вектор «удлиняется», а при |λ|<1 — «укорачивается». При положительном числе λ направление вектора не меняется, а при λ<0 вектор меняет свое направление на противоположное.

Пример 1. Если X = [8, -2, 2, 3] и λ=3, то 3Х=Х3 = [24, -6, 6, 9].

Вектор, являющийся произведением некоторого вектора Х на действительное число λ, никогда не выходит из того пространства, которому принадлежит вектор X, т. е. если Х m-мерный вектор, то и λХ тоже m-мерный вектор.

Сумма m-мерных векторов дает снова m-мерный вектор, компоненты которого являются суммами одноименных компонент слагаемых векторов.

Пример 2. Если X1=(2, -4, 0, 8, 4); Х2 = (0, 2, 8, -1, -2); Х3 =(3, 5, 2, 2, -1), то X=X1+X2+X3=(5, 3, 10, 9, 1).

Число, равное сумме произведений одноименных координат двух m-мерных векторов, называется их скалярным произведением, т. е. если X=(x1, х2, ..., xт) и У=[y1,y2,…,yт] m-мерные векторы, то их скалярное произведение есть число

XY=YX=x1y1+x2y2+...+.xmym.

Пример 3. Даны два шестимерных вектора Х=(2, 5, -1, 3, 0, 5); У= [3, -2, 0, 1, 2, 3]. Скалярное произведение этих векторов есть число

ХУ = 2 3+5 (-2) +(-1) 0+3 1+0 2+5 3=14.

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

F = c1x1 + c2x2 + . . . + cnxn

может быть кратко записана в виде