Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

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

обеспечить min или max так называемой целевой функции. Допустим, что в рассматриваемом примере целевая функция

для 3-го решения L —1 + 2 • 2 + 3-0 = 5, т. е. оптимальным было бы третье решение.

Рассмотрим особенности постановки задач линейного програм­ мирования. Первой из этих особенностей является выражение це­

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

Общая форма записи задач линейного программирования с уче­ том отмеченных их особенностей обычно следующая:

Ь = 'У1сг х г — целевая функция, требующая максимизации пли Ч 11 1 минимизации;

■— ограничения в форме равенств или неравенств.

i x ij < bj

Проиллюстрируем порядок постановки и записи задач линей­ ного программирования на следующем простом методическом при­ мере.

Имеется т гравийных карьеров, в которых может осуществлять­ ся заготовка материалов (1, 2, 3, ... г, ... т). Имеется п объектов дорожных работ, которым нужны гравийные материалы (1 , 2 , ...,

/, .... я).

Введем обозначения: а, — количество гравийного материала, которое может быть получено в г-м карьере, м3; b j — количество гравийного материала, необходимое /-му объекту, м3; Хц — коли­ чество гравийного материала, перевозимое из г-го карьера на /-й объект. Предполагается, что общая потребность в гравийных мате­ риалах удовлетворяется:

тп

Т а б л и ц а 15

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

Допустим, что т = 2 и п = 3. Составим вспомогательную таблицу для переменных (табл. 15). Совокупность перевозок из карьера 1 должна удовлетворять уравнению

Для карьера 2 аналогично получим

Эти условия еще недостаточны для решения задачи. На каждый объект нужно завезти материалы в необходимом количестве, поэто­ му составим следующие соотношения:

Распределить перевозки нужно так, чтобы стоимость всего объе­ ма перевозок была минимальной, т. е.

с п х \ \ Л ~ с п х п ~ \ ~ c i z x \ z ~ \ ~ с п х и ' \ - — L , (V.7)

где L — целевая функция.

Таким образом, целевая функция и все ограничения выразились линейными зависимостями. Дополнительным условием является не­ отрицательность величин хц, т. е. Xij^O.

Из зависимостей (V.2) — (V.6 ) видно, что число неизвестных, которые нужно определить, равно шести (хп, Х\2, х 13, х2ь х22, х2з),

тогда как число уравнений, связывающих эти неизвестные, равно пяти: неравенства (V.2) и (V.3) и равенства (V.4 ) — (V.6 ). Кроме

того, значения неизвестных должны быть найдены так, чтобы ми­ нимизировать линейную форму (V.7).

68

Чтобы получить в дальнейшем (см. § 11) количественное реше­ ние задачи, примем значения постоянных, входящих в целевую функцию, и ограничения в соответствии с данными табл. 16.

Ограничения (V.2) и (V.3), имеющие форму неравенств, можно превратить в равенства, введя фиктивный объект работ 4, на кото­ рый и должна быть спланирована вывозка остатка запаса мате­ риала обоих карьеров. Этот остаток

тп

2 а , - 2 Ь, = ( 4 + 1 0 ) - ( 5 + 3 + 4) = 2.

1 = 1 у = 1

Так как фактически перевозок на фиктивный участок 4 не бу­ дет, их стоимостные характеристики Сн и с24 должны быть приня­

ты равными нулю. При этом значение линейной формы (V.7) не претерпит каких-либо изменений от введения фиктивного участка. С учетом фиктивного участка работ в табл. 17 даны все исход­ ные данные и искомые неизвестные задачи.

69

Как уже отмечалось в гл. I, при решении некоторых задач вмес­ то стоимостных характеристик могут использоваться показатели энергозатрат. Тогда вместо стоимости сц может вводиться показа­ тель энергозатрат Эц. Если, например, речь идет о показателе, ха­ рактеризующем перевозки, и Сц представляет собой стоимость пе­ ревозки единицы измерения материала из г-го карьера на /-й участок работ, то соответствующие энергозатраты выразятся соот­ ношением

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

В задачах линейного программирования могут быть три случая:

1 - й — система имеющихся уравнений не имеет неотрицательны

решений; 2 - й — система имеет неотрицательные решения, но экстремум

линейной формы, выражающей целевую функцию, равен +°о или

— оо; 3- й — значение экстремума линейной формы на множестве неот

рицательных решений системы конечно.

Для большинства задач характерен третий случай.

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

На участок строящейся дороги необходимо вывезти 20 000 м3 ка­

менных материалов. В районе строительства имеются три карьера

70