Барсов А. С. Что такое линейное программирование. — М. : Физматгиз, 1959. — 104 с. — (Популярные лекции по математике ; вып. 33). — Библиогр.: с. 104 (13 назв.).

Популярные лекции

ПО МАТЕМАТИКЕ

А. С. БАРСОВ

ЧТО ТАКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ФИЗМАТГИЗ-1959

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 33

А. С. БАРСОВ

ЧТО ТАКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

МОСКВА 1959

АННОТАЦИЯ

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

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

Книга рассчитана на математиков, инженеров и экономистов, занимающихся вопросами математического планирования, в частности применением автоматических цифровых вычислительных машин к этим вопросам.

Алексей Сергеевич Барсов.

Что такое линейное программирование.

Редактор В. Д. Розенкноп.

Техн. редактор К. Ф. Брудно. Корректор З. В. Моисеева

Сдано в набор 30/VIII 1959 г. Подписано к печати 10/XI 1959 г. Бумага 84X108V3a-Физ. печ. л. 3,25. Условн. печ. л. 5,33. Уч.-изд. л. 5,40. Тираж 15.000 экз. T-Ï1040. Цена книги 1 р. 60 к. Заказ № 3554.

Государственное издательство физико-математической литературы. Москва, В-71, Ленинский проспект, 15.

Первая Образцовая типография имени А. А. Жданова Московского городского Совнархоза. Москва, Ж-54, Валовая, 28.

ОГЛАВЛЕНИЕ

Предисловие......................... 4

Введение .......................... 5

Глава I. Некоторые понятия и определения линейной алгебры..................... 9

§ 1. Понятие об т-мерном пространстве ......... 9

§ 2. Гиперплоскость и полупространство ......... 19

§ 3. Выпуклые многогранники.............. 21

§ 4. Система линейных неравенств............ 24

§ 5. Наименьшее и наибольшее значения линейной формы на многограннике.................. 28

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

Глава II. Решение общей задачи линейного программирования ...................... 36

§ 7. Тождественные преобразования системы линейных алгебраических уравнений............... 37

§ 8. Метод определения неотрицательного решения системы линейных алгебраических уравнений......... 50

§ 9. Решение задачи линейного программирования..... 57

§ 10. Об одной задаче на минимакс............ 63

Глава III. Решение транспортной задачи по критерию стоимости..................... 65

§ 11. Постановка задачи.................. 66

§ 12. Основные решения транспортной задачи по критерию стоимости..................... 67

§ 13. Оптимальный выбор................. 71

§ 14. Инвариантность последовательности выборов эквивалентным преобразованиям матрицы стоимости ...... 76

§ 15. Алгоритм нахождения оптимального решения..... 77

Глава IV. Решение транспортной задачи по критерию времени .................... 90

§ 16. Постановка и решение задачи ............ 90

§ 17. Решение задач транспортировки с учетом времени и стоимости .................... 101

Литература....................... 104

ПРЕДИСЛОВИЕ

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

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

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

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

Член-корреспондент АН СССР Л. А. Люстерник внимательно ознакомился в марте 1959 года с материалами лекций, дал ряд ценных советов и содействовал выходу в свет этой работы.

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

Автор особенно признателен редактору В. Д. Розенкнопу, тщательная работа которого значительно способствовала улучшению книги.

А. С. Барсов

ВВЕДЕНИЕ

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

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

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

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

Первыми работами в этом направлении были работы члена-корреспондента АН СССР Л. В. Канторовича. В этих работах приведены математические методы решения таких задач, как задача повышения эффективности работы транспорта, определения оптимальных производственных режимов, рационального раскроя промышленных материалов и т. п.

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

Линейное программирование охватывает методы решения ряда оптимальных задач, имеющих дело со многими взаимосвязанными переменными, подчиняющимися определенным

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

Имеется некоторая величина (например, стоимость, время), являющаяся линейной функцией ряда переменных. Переменные в свою очередь должны удовлетворять ограничениям, выраженным в виде системы линейных неравенств или равенств.

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

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

Из данных m пунктов отправления, в каждом из которых имеется но а- единиц груза, необходимо перевезти в каждый из п пунктов назначения по bj единиц того же груза

(/=1, 2, т\ У= 1,2, —, п).

Требуется спланировать перевозки таким образом, чтобы затраты на последние были минимальны. Пусть x.j обозначает количество груза, перевозимого из /-го пункта отправления в у'-й пункт назначения. В таком случае задача математически сводится к нахождению таких неотрицательных значений x(j, удовлетворяющих уравнениям

при которых общая стоимость перевозок

становится наименьшей, при этом c{j есть стоимость перевозки единицы груза из /-го пункта отправления в у-й пункт назначения.

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

Другим примером применения линейного программирования может служить следующая задача.

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

Пусть, например, цех располагает m машинами (станками) для производства различных п изделий. Каждая машина /-я (/=1,2, . . ., т) характеризуется определенным bi возможным месячным рабочим временем, нормой времени t.j на изготовление одной единицы у-го изделия (/=1,2, . ..,/z), а также стоимостью Сц, затрачиваемой на изготовление одной единицы того же у-го изделия на /-й машине. Если цеху дано задание выпустить в наступающем месяце определенное ßy количество каждого из различных изделий, то возникает задача такой организации работ, при которой задание будет выполнено при минимальном расходе средств. Если через Ху обозначить количество у-х изделий, производимое на i-м станке, то поставленная задача сводится к такому распределению загрузки машин, чтобы удовлетворить условиям

и сделать значение общей стоимости

как можно меньше.

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

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

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

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

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

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

Примером может служить задача определения оптимального плана перевозок строительного песка к строительным площадкам г. Москвы. В этой задаче было задано 10 пунктов отправления и 230 пунктов назначения. Полученный на машине «Стрела» оптимальный план перевозок дал только за одну декаду июня 1958 года экономию около 11°/0.

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

ГЛАВА I

НЕКОТОРЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ЛИНЕЙНОЙ АЛГЕБРЫ

В этой главе излагаются основные понятия и определения линейной алгебры /«-мерного пространства, необходимые для решения задачи линейного программирования.

§ 1. Понятие об n-мерном пространстве

Всякая упорядоченная тройка (av а2У а3) действительных чисел может быть геометрически истолкована как точка пространства. В соответствии с этим геометрическим представлением в математике принято следующее определение: трехмерное пространство есть множество всевозможных упорядоченных троек (av а2, аг) действительных чисел*). При этом говорят, что система чисел (av а2, а9) определяет точку M в трехмерном пространстве с координатами ах, а2, а3 или вектор Р с компонентами av а2, аг в том же пространстве. Для задания некоторых объектов, процессов или состояний недостаточно трех действительных чисел. Так, определение положения твердого тела в пространстве требует шести координат. В случае если район производит определенные промышленные и сельскохозяйственные товары, например железнодорожные вагоны, автомашины, хлеб, молоко, спички и т. д., то для характеристики промышленного и сельскохозяйственного производства данного района требуется упорядоченная последовательность действительных чисел. Так, имея таблицу 1,

*) Аналогично множество всевозможных действительных чисел (ах) есть одномерное пространство, геометрическим образом которого может служить прямая; множество всевозможных пар действительных чисел (av а2) есть двухмерное пространство, геометрическим образом которого может служить плоскость.

можно сказать, что район № 2 ежегодно производит а2Х тонн угля, а22 тонн железной руды, а23 тонн стали, а2п тонн пшеницы.

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

Таблица 1

Эти примеры указывают на целесообразность рассмотрения совокупности всевозможных упорядоченных последовательностей из m действительных чисел, где m — любое натуральное число. Известно, что упорядоченная система m действительных чисел (а1, а2, ..., ah ат) называется т-мерным вектором.

Числа аь /=1,2, . называются компонентами вектора P(alf а2, ат).

Векторы P(av а2, ..., ат) и Q^, b2, ..., bm) считаются равными в том и только в том случае, если совпадают их компоненты, стоящие на одинаковых местах, т. е. при ai = bi для всех /=1,2, ..., т.

Если нас интересует суммарная производительность двух районов по различным видам продукции, то, очевидно, она может быть получена сложением соответствующих производительностей этих районов*). Так, если производительность района № 1 по каждому виду продукции определяется вектором Pl{aiv а12, а района № 2 — вектором Р2(я21, а22, ,..,ûj, то суммарная производительность этих районов характеризуется вектором

*) Производительность в данном случае означает количество продукции, выпускаемое за определенный отрезок времени.

Если производительность района определяется вектором Р = Р(ар аг, . .., ат), то увеличение производительности района по каждому из товаров в k раз можно выразить вектором Q, где Q, = Q{kax, ka2, . .., kam).

Введенные определения являются обобщением известных правил действий над векторами трехмерного пространства. Распространяя понятие трехмерного пространства на последовательности действительных m чисел, получаем следующее важное определение: совокупность всевозможных /я-мерных векторов Р (av аг, ..., ат) с действительными компонентами называется m-мерным пространством и обозначается Р(т). По определению, сложить два т-мерных вектора Р и Q — значит получить третий вектор R = P-[-Q с компонентами, равными суммам соответствующих компонент слагаемых векторов. Умножить вектор Р на число k— значит умножить каждую компоненту на это число.

Вектор Р (av а2, ..., ап) называется пропорциональным вектору Q(^1, b2, . .., bn), если существует такое число ky что bl = kal, b2 = ka2, ..., bn = kan. В этом случае P = £Q.

Обобщением понятия пропорциональности векторов служит понятие линейной комбинации векторов.

Вектор Р называется линейной комбинацией векторов Pj, Р2, . .^Р^, если существуют такие действительные числа lv /2, /„ что Р = /1Р1 + '«Р.+ ---+/Л- В этом случае /-я компонента вектора Р (/=1, 2, т) равна сумме произведений i-x компонент векторов Pv Р2, Р^ соответственно на lv /2, ..., ls.

Система векторов Pv Р2, ..., Рг-1, Рг называется линейно зависимой, если хотя бы один из этих векторов является линейной комбинацией остальных векторов.

Это определение эквивалентно другому:

система векторов называется линейно зависимой, если существуют такие действительные числа kv k2, ..., kr по крайней мере одно из которых отлично от нуля, что имеет место равенство

В противном случае система векторов называется линейно независимой.

Если вектор Р0 является линейной комбинацией векторов Pj, Р2, Р„, то говорят, что Р0 линейно выражается через систему векторов {Ру}, где /=1, 2, ..., п. Понятно, что если вектор линейно выражается через некоторую

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

Обобщая эту терминологию, говорят, что система векторов Qj, Q2, линейно выражается через систему векторов Pj, Р2, ..., Ри, если всякий вектор Q,-, /= 1, 2, . •s, является линейной комбинацией векторов системы {Р/}, у=1, 2, п.

Рассмотрим в пространстве Р(т) векторы:

(1)

Эти векторы называются ортами. Система векторов (1) является линейно независимой, так как —j— кг\г-\- ... ...-[- km\m = О, только если ki = О для всех /=1,2, ..., т. Всякий вектор P(av д2, ат) пространства Р(т) линейно выражается через векторы системы (1), а именно

Можно показать, что всякая система векторов пространства Р(т\ состоящая более чем из m векторов, линейно зависима.

Так, если в плоскости из начала координат выходят два вектора Р1 и Р2, не направленные по одной прямой, т. е. линейно независимые векторы, то любой третий вектор Р0 можно представить как линейную комбинацию этих векторов.

Аналогично, если в трехмерном пространстве заданы три вектора, не лежащие в одной плоскости и выходящие из начала координат, то любой вектор этого пространства выражается как линейная комбинация этих векторов. Так, на рис. 1 изображен случай, когда вектор Р0 представляется комбинацией линейно независимых векторов Pv Р2, Р8, которая имеет вид

Рис. 1.

В двухмерном пространстве двум линейно независимым векторам Р1 (ап, а21) и Pt (а12, а22) соответствует определитель

отличный от нуля.

Абсолютное значение этого определителя равно площади параллелограмма, построенного на векторах Р1 и Р2 (рис. 2).

Рис 2. Рис. 3.

В трехмерном пространстве три линейно независимых вектора

образуют параллелепипед (рис. 3). В этом случае абсолютное значение определителя

отлично от нуля и равно объему параллелепипеда.

По аналогии, если в т-мерном пространстве заданы m линейно независимых векторов

то, как показано в курсах высшей алгебры, определитель

отличен от нуля.

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

Образуем из компонент этих векторов матрицу*) порядка

(2)

Столбцы этой матрицы, рассматриваемые как /w-мерные векторы, могут, вообще говоря, быть линейно зависимыми. Максимальное число линейно независимых столбцов матрицы (2) называется рангом этой матрицы**). Иначе говоря, ранг матрицы (2) равен максимальному числу линейно независимых векторов Ру, компоненты которых составляют ее столбцы. Всякая максимальная линейно независимая система векторов пространства Р(т> называется базисом этого пространства.

Пусть векторы Рр Р2, Ру-1, Рр Ру+1, Рт

образуют базис пространства Р(т\ который назовем Л-базисом. Тогда любой вектор Р этого пространства может быть представлен, и притом однозначно, в данном базисе в виде линейной комбинации векторов Ру., /=1, 2, т. Все базисы векторного пространства состоят из одного и того же числа векторов.

Возьмем произвольный вектор Q, не принадлежащий базису Pj, Р2, Рт. Тогда, если вектор Q не равен нулю, то в линейной комбинации

имеется по крайней мере один коэффициент, отличный от нуля.

*) Здесь и в дальнейшем компоненты векторов Ру будем располагать в виде колонок матриц.

**) Всегда максимальное число линейно независимых строк матрицы равно максимальному числу линейно независимых столбцов.

Пусть, например, ау^0, тогда вектор Ру Л-базиса можно представить в виде:

Исключим из Л-базиса вектор Ру и присоединим к оставшимся векторам вектор Q. Система векторов Р,, Р2, Ру_,, Q,

Ру+1, Рт снова является базисом. В самом деле, в силу однозначного разложения любого вектора по векторам базиса, после исключения вектора Ру из Л-базиса, вектор Q уже не может быть представлен в виде линейной комбинации оставшихся векторов. Это означает, что система векторов Pj, Р2, Ру_, Q, Ру+1, Рт является линейно независимой системой, т. е. образует базис.

ß-базис, полученный из Л-базиса заменой некоторого вектора на вектор, не принадлежащий Л-базису, назовем базисом однократного замещения по отношению к А-базису.

Пусть в /я-мерном пространстве задано п -\-1 векторов Р0, Р1? Р2, ..., Ру, ..., Р„, которые в базисе Q1} Q2, ..., Qm имеют разложения:

(3)

Образуем матрицу из компонент разложений (3)

(4)

Допустим теперь, что векторы qv q2, ..., qm образуют новый базис в Р(т). Пусть эти векторы имеют следующие разложения в базисе Q,, Q2, Qm:

Так как qv q2, qm образуют базис, то определитель

(5)

отличен от нуля.

Перейдем от базиса Qp Q2, ..., Qm к базису qv q2, ..., qm. Тогда векторы P0, Р„ Р2, Рп будут иметь в базисе Чр Ч2» Чт коэффициенты разложения, вообще говоря, отличные от коэффициентов разложения в базисе Qv Q2,.. .,Qm:

Матрица разложений в этом случае имеет вид

(6)

Как известно, элементы матрицы (6) определяются через элементы матрицы (4) и определитель (5) по следующим формулам:

где

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

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

Пусть в базисе Р,, Р2, Р, векторы Р0, Рр Р2, Р,, Р4, Р5, Рв имеют разложения, определяемые матрицей

Так как определитель, составленный из компонент векторов Р Р Р

отличен от нуля, то векторы Р4, Р4, Р6 образуют базис.

Найдем разложения векторов Р0, Р1, Р2, Р8, Р4, Р5, Рв в базисе Р4, Р5, Рв. Пользуясь формулами (7), получим

Производя соответствующие выкладки, будем иметь матрицу, представляющую разложение данных векторов в базисе Р4, Р5, Рв:

Как известно скалярным произведением двух векторов Р и Q называется выражение, определяемое формулой

(Р. Q) = ахЪх + я А + ... + a fi, + ... + aj>m

где a fr bt — компоненты векторов Р и Q. Векторы Р и Q называются ортогональными, если их скалярное произведение равно нулю. Так как матрицу порядка m X # можно рассматривать как (т X #)-мерный вектор, то скалярным произведением матриц

будем называть алгебраическую сумму всех элементов матрицы

и обозначать (Л-В).

§ 2. Гиперплоскость и полупространство

Из аналитической геометрии известно, что линейному уравнению

Аххх + Агхг + Агхг = С (8)

в трехмерном пространстве соответствует плоскость, нормальная к вектору А Л2, Аг).

Приведем уравнение (8) к виду

Плоскость, соответствующая этому уравнению, отсекает на осях координат отрезки av а2, аь (рис. 4).

Кроме того, уравнение плоскости в трехмерном пространстве может быть представлено в векторной форме (А°-Х) = /г, где А° — вектор единичной длины, нормальный к плоскости; X — текущий вектор, соединяющий начало координат с точкой, принадлежащей плоскости; здесь (А°»Х)—скалярное произведение векторов А° и X, равное по величине проекции h вектора X на направление, определяемое вектором А°. Величина h равна расстоянию от начала координат до плоскости. При h = О плоскость проходит через начало координат.

Любой вектор X, соединяющий начало координат с точкой плоскости, имеет одну и ту же проекцию h на направление А0 (рис. 5).

Рис 4.

Рис. 5.

По аналогии будем называть гиперплоскостью или просто плоскостью в т-мерном пространстве множество всех точек (xlt хг, ..., хт), удовлетворяющих уравнению

Условимся говорить, что эта гиперплоскость нормальна к вектору А(Лг, Л2, ...,Ат). Будем говорить также, что уравнению

соответствует гиперплоскость, отсекающая на осях координат отрезки длины а1% а2, ..., ат.

Наконец, векторное уравнение (А°-Х) = Л в пространстве Р{т) определяет гиперплоскость, нормальную к единичному вектору А° и отстоящую от начала координат на расстоянии h. Прямая на плоскости делит последнюю на две части, каждая из которых называется полуплоскостью. Из рис. 6 видно, что прямая делит плоскость на две полуплоскости. Кроме того, проекции Ос1 векторов Х1? концы которых лежат в одной полуплоскости, меньше h=Ocy а для векторов Х2, концы которых принадлежат другой полуплоскости, больше h.

Плоскость в трехмерном про* странстве также делит все пространство на две части, каждая из которых называется полупространством.

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

Пусть гиперплоскость в пространстве Р(т) выражается уравнением (A°-X) = Ä. Тогда для точек M одного из полупространств проекции изображающих их векторов X на направление А0 меньше Л, а для точек другого полупространства— больше h. Таким образом, одно из полупространств

Рис, 6.

есть множество векторов X, для которых выполняется неравенство (А0-XX Л, а для векторов другого полупространства — (А° • X) > к. Сама гиперплоскость (А° • X) = h может быть присоединена к одному из полупространств. Тогда все множество точек т-мерного пространства будет разделено на два вида: точки, для которых (А°-Х)^А, и точки, для которых (А0 - X) > h (или в другом случае ( А° • Х)< h и ( А° • X) > Л).

Пример 1. Дано полупространство — 5х1 -(- 4х2—За:,^ 5. Определить, принадлежит ли ему точка (0, 0, 0).

Для ответа достаточно подставить значения xt = 0; л:2 = 0; хг = 0 в неравенство. Будем иметь —5-0-}-4-0— 3-0 < 5, откуда следует, что точка (0, 0, 0) действительно принадлежит полупространству — 5х, -|- 4л;2 — Зх9 ^ 5.

Плоскость — Ъхх -\--\-$х2— За:, = 5 перпендикулярна вектору А ( — 55 4,-3) (рис. 7).

Рис. 7.

Пример 2. Определить, принадлежит ли точка девятимерного пространства х1 = 0; х2 = 4; лг8 = 3; хл = — 7; л:8=0; х6 = 0, х7 = 9; л:8—1; xQ = 0 полупространству 4х1 Ъх2 — 7л:, -\- хъ — 2х6 -f- 12х7 — 3*9 <; 11. Подставив координаты этой точки в неравенство, получим 4-0-(-4-5 — — 3-7 — 7-0-J-0-1 — 2-0 — 9-12 — 1-0 — 3-0 = 109 > И. Следовательно, эта точка не принадлежит заданному полупространству.

§ 3. Выпуклые многогранники

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

Примерами выпуклых тел могут служить круг, шар, куб, угол, образованный двумя лучами, выходящими из одной точки (рис. 8).

Пусть точки X и у являются общими для выпуклых тел А и В (рис. 9). Тогда х и у принадлежат телу Л, а поэтому отрезок, соединяющий точки х и у, также принадлежит А. Аналогично этот же отрезок принадлежит и телу В. Следовательно, он принадлежит и общей части тел А и В. Это

означает, что общая часть или пересечение выпуклых тел есть выпуклое тело.

Возьмем на плоскости многоугольник, лежащий по одну сторону от каждой прямой, участвующей в образовании этого многоугольника. Как видно из рис. 10,а, этот многоугольник является выпуклым. Действительно, любые две точки х и у такого многоугольника принадлежат ему вместе с соединяющим их отрезком. Напротив, многоугольник, представленный на рис. 10,6, не лежит по одну сторону от каждой прямой, участвующей в образовании этого многоугольника. Такой многоугольник не является выпуклым.

Возьмем произвольную точку М, не принадлежащую выпуклому многоугольнику (рис. 11,а). Всегда можно указать такую прямую PQ, что точка M и многоугольник лежат по разные стороны от PQ. Для выпуклого многоугольника можно построить множество таких прямых, что каждая из них имеет по крайней мере одну общую точку с многоугольником, и таких, что весь многоугольник находится по одну сторону от каждой из них. Такие прямые называются опорными.

Так, на рис. 11,6 прямые AD, СВ, DB и FN являются опорными. Опорная прямая может иметь с выпуклым многоугольником общую часть, состоящую или из одной точки, или отрезка.

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

Рис. 8.

Рис. 9.

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

Ранее мы убедились, что общая часть нескольких выпуклых тел является выпуклым телом. Поэтому общая часть нескольких многогранников есть выпуклое тело. Поскольку плоскость есть выпуклое тело, то пересечение многогранника с плоскостью есть выпуклое тело и представляет либо точку, либо отрезок, либо выпуклый многоугольник. Аналогично свойствам выпуклых тел трехмерного пространства можно рассматривать свойства выпуклых «тел» многомерных пространств. Некоторые из этих свойств будут рассмотрены в § 4 и 5.

Рис 10.

Рис. 11.

§ 4. Система линейных неравенств

Пусть в двухмерном пространстве заданы п неравенств вида

*/Л+ */Л<** (''=1. 2,...,/г)*). (10)

Каждое такое неравенство определяет одну из двух полуплоскостей с граничной прямой ^ilxl-\-ailxt = bi. Граничная прямая ttilxl-\-aitxt = bi нормальна к вектору k((aiv ai2).

Рис. 12 (а, б).

Всякая пара чисел (xv х2), удовлетворяющая всем неравенствам системы (10), называется решением данной системы неравенств. Иными словами, всякая точка плоскости (ххх2)у координаты которой удовлетворяют системе (10), является решением.

Рассмотрим несколько примеров:

1. Неравенство

Х + Т^1 или 2*1 + 3**<6

определяет полуплоскость (рис. 12,а). Этому неравенству удовлетворяет любая точка, лежащая в заштрихованной части плоскости. Граничная прямая выражается уравнением 2х1-\-Зх2 = 6 и нормальна к вектору А (2, 3).

2. Два неравенства

2*,+ Зл:а<6,

определяют часть плоскости, как изображено на рис. 12,6.

*) Всякое неравенство вида а^х, -f- ai2x2 ^ после умножения обеих частей его на —1 приводится к виду (10).

3. Трем неравенствам

удовлетворяет множество точек плоскости, образующих треугольник решений AFB (рис. 12,в).

Рис. 12 (в, г).

4. Четырем неравенствам

(1)

(2) (3)

(4)

соответствует множество точек плоскости, образующее многоугольник решений ABCD (рис. 12,г). 5. Семи неравенствам

(1)

(2) (3) (4) (5) (6) (7)

соответствует то же множество точек, что и в примере 4. Неравенства (5), (6) и (7) могут быть исключены без изменения множества решений. При этом неравенства (5) и (6) определяют граничные прямые, не имеющие с многоугольником ABCD общих точек. Прямая (7) имеет одну общую точку с многоугольником и является опорной (рис. 12,д). 6. Система неравенств

(1)

(2) (3) (4) (5')

не имеет ни одного решения. Геометрически это означает, что не существует ни одной точки, координаты которой удовлетворяют всем неравенствам (рис. 12,е).

Рассмотрение этих примеров приводит к следующим выводам:

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

Рис. 12 (д, е).

2. Система неравенств может оказаться несовместной. В этом случае не существует ни одной точки плоскости, удовлетворяющей одновременно всем неравенствам системы.

Без ограничения общности систему п неравенств в трехмерном пространстве можно записать в виде

aiixi + аИхг + апх* < */ (/ = 1, 2, . . ., Л). (11)

Как мы уже знаем, каждое из неравенств (11) определяет полупространство с граничной плоскостью

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

В случае совместности среди неравенств системы могут быть и «лишние» неравенства, удаление которых не изменяет множества решений данной системы неравенств. Эти «лишние» неравенства могут быть двух видов: 1 вид — неравенства, граничные плоскости которых не имеют пересечения с множеством всех решений системы; 2 вид — неравенства, граничные плоскости которых являются опорными для множества решений.

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

Пусть в т-мерном пространстве задана система неравенств

в/А + Л/Л + • • ■ + «лЛ.<*1 ('=1. 2,..., «)• О2)

По аналогии с трехмерным пространством будем говорить, что каждое из неравенств (12)' определяет в m-мерном пространстве полупространство с граничной плоскостью

*/Л + в/Л + • • • + aimXm = bi-

Если в m-мерном пространстве существует по крайней мере одна точка М(х1У х2, хт)у удовлетворяющая одновременно всем неравенствам, то система (12) называется совместной. Множество всех таких точек будем называть «многогранником решений».

Пусть в т-мерном пространстве заданы две точки М'(х'и х'г, х'т) и М"(х"и xnt, х"т). Множество точек

M(xv xv ...yxm), координаты которых удовлетворяют условиям:

при изменении параметра / от 0 до 1, называют отрезком, соединяющим точки М' и М". Являясь пересечением полупространств, «многогранник решений» есть выпуклое множество. Это означает, что вместе с точками М' и М" ему принадлежат и все точки соединяющего их отрезка.

Неравенства, которые можно удалить из системы (12), не изменяя множества ее решений, называются зависимыми или «лишними». Удаляя из заданной системы последовательно одно за другим неравенства такого вида, получим подсистему неравенств, множество решений которой совпадает с множеством решений первоначальной системы.

Удаление «лишних» неравенств является очень сложным и трудоемким процессом. Одна из особенностей методов линейного программирования состоит в том, что для определения наименьшего (наибольшего) значения линейной функции на многограннике не требуется специального процесса выделения «лишних» неравенств. Если системе неравенств (12) не удовлетворяет ни одна точка /и-мерного пространства, то такая система называется несовместной.

§ 5. Наименьшее и наибольшее значения линейной формы на многограннике

Рассмотрим совместную систему линейных неравенств с двумя переменными. Предположим, что мы исключили все «лишние» неравенства 1-го и 2-го видов и тем самым выделили многоугольник решений в «чистом виде» (рис. 13). Пусть, кроме того, задана линейная функция двух переменных

Найдем среди множества точек (xv х2) многоугольника решений такие, которые придают линейной функции /= с1х1-\-сгх1 наименьшее и наибольшее значения. Рассмотрим множество всех точек (л^, х2) плоскости, в каждой из которых функция f=clxl -J- ctx2 принимает фиксированное значение f=fy. Множество таких точек есть прямая cxxx-\-ctxt=fv Эта

прямая, как отмечалось в предыдущем параграфе, нормальна к вектору С (сх\ с2), выходящему из начала координат. Проведем прямую F (рис. 13), нормальную к вектору С, и будем ее передвигать параллельно самой себе в положительном направлении вектора С. Пусть при движении прямой F она впервые встретится с многоугольником в вершине Л. В этом положении F' прямая F становится опорной. При дальнейшем движении в том же направлении прямая F пройдет через вершину В и станет также опорной прямой. Так как направление вектора С (сх\ с2) есть направление наибольшего возрастания линейной функции /=с1х1-\-с2х2, то на опорной прямой F' функция / принимает наименьшее значение, а на опорной прямой F" — наибольшее значение среди значений /, принимаемых на многоугольнике решений.

Таким образом, наименьшее и наибольшее значения линейной функции f=clxl -\-с2х2 на многоугольнике решений достигаются в точках пересечения этого многоугольника с опорными прямыми, нормальными к вектору С (сх; с2). Пересечение опорной прямой с многоугольником решений может состоять либо из одной точки*) (вершины многоугольника), либо из бесчисленного множества точек (в этом случае это множество есть сторона многоугольника).

На рис. 14 изображен случай, когда линейная функция / достигает наименьшего значения в каждой точке отрезка А Ал9

Рис. 13.

Рис. 14.

*) Эта точка может оказаться в бесконечности.

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

Аналогично линейная функция трех переменных f=clxl-\-Л~сгх1~\~сьхг принимает постоянное значение на плоскости, нормальной к вектору С (сх\ с2\ сг). Направление С есть направление максимального возрастания функции / (рис. 15). Наибольшее и наименьшее значения этой функции на многограннике решений также достигаются в точках пересечения этого многогранника с опорными плоскостями, нормальными к вектору С (cv с2, сг)\ при этом на одной из опорных плоскостей / достигает наименьшего, а на другой — наибольшего значения. Пересечение многогранника с опорной плоскостью может представляться либо одной точкой (вершина многогранника), либо бесчисленным множеством точек (в этом случае это множество есть либо ребро, либо грань многогранника). Например, на рис. 16 изображен случай, когда /достигает наименьшего значения в каждой точке грани ABQP, а наибольшего — в точке D.

Рис. 15

Рис. 16.

Обобщением понятия линейных функций от двух и трех переменных является функция вида /= сххх-f-с2х2-\~. . .-\-спхп от п вещественных переменных л^, х2У..., хп, называемая линейной формой; здесь сх, с2} ..., сп — вещественные числа. Фиксируя значения линейной формы f—fx\ f=ft\ . • • . ..; f=fg, мы тем самым определяем в я-мерном пространстве гиперплоскости

нормальные к я-мерному вектору C(cv с2, с9). Обозначим через /min наименьшее значение формы

/= * А + С2Х2 + • • • + V«

на многограннике решений, а через /тах — наибольшее значение. Так как вектор С определяет направление наибольшего возрастания линейной формы /, то при /' </min и при /'>/тах соответствующие гиперплоскости /' = сххх -\- сгх2 -|- спхп не имеют пересечений с многогранником решений. С другой стороны, каждая гиперплоскость/" = £А~Ь*?А~Ь ... -\-спхп, для которой /min ^/П1ах, имеет общие точки с многогранником решений. Множество точек M (xv х2У ... , лгп), в которых линейная форма / достигает наименьшего значения, есть пересечение многогранника решений с опорной гиперплоскостью сххх -|- с2х2 -f- ... -f- спхп =/min, нормальной к вектору С(сх, с2, ... , £и). Аналогично, наибольшего значения / достигает в точках пересечения многогранника с опорной гиперплоскостью сххх -f- с2х2 -[-...-{- £Ллг„ = /тах, также нормальной к вектору С.

Пересечение многогранника решений с опорной гиперплоскостью есть вершина, ребро или «грань» многогранника.

Таким образом, оптимальное значение линейной формы на многограннике решений достигается в точках, среди которых всегда имеется по крайней мере одна из вершин. Поэтому для определения оптимального решения достаточно выбрать ту вершину многогранника, в которой линейная форма достигает наименьшего (наибольшего) значения.

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

Пусть задана система m линейных неравенств с п переменными:

(12)

определяющая в /г-мерном пространстве многогранник решений. Рассмотрим наряду с этой системой неравенств систему m линейных алгебраических уравнений с п-\-т переменными:

(12')

Покажем, что всякому решению jtj, х\, ... , х°п системы неравенств (12) соответствует определенное решение x°v х\,..., х°п; К» V&> • • • э V-m системы линейных алгебраических уравнений (12'), причем дополнительные переменные удовлетворяют условию jjiJ ^ 0, ]к\ ^ 0, ... , \i?m ^5 0. В самом деле, если х\, х\у ... , х°п есть решение системы (12), то имеют место неравенства:

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

Тогда, во-первых, jjlJ ^ 0, ц°2 ^ О, ... , \х°т ^ 0; во-вторых, система чисел x°v х\, ... , л:°; jx°, jx°, ... , ja^, как следует из (12"), есть решение системы линейных алгебраических уравнений (12').

Докажем, наоборот, что всякому решению х\, х°2, ... , х°п; ja?, |xj, ... >ц°т системы уравнений (12'), удовлетворяющему условию jij ^ 0, |xj ^ 0, ... , р.°т ^ 0, соответствует определенное решение системы неравенств (12). В самом деле. Поскольку система чисел x°v лг°, ... , х*п\ \x°v ... \к°т есть решение системы (12'), то можно записать:

Так как по предположению числа jjiJ, ... , ]х°т неотрицательны, то имеют место неравенства:

т. е. система чисел jcj, x°2i ... , лг° есть решение системы неравенств (12).

Таким образом, установлено взаимнооднозначное соответствие между множеством всех решений х\, лг°, ... , лг° системы (12) и множеством решений х\у х°„ ... , х°п; jaJ, ... , )iQm системы (12'), причем дополнительные переменные jjiJ, jij, ... , ]i°m неотрицательны. Таким образом, задача решения системы линейных неравенств вида (12) сводится к решению соответствующей системы линейных уравнений вида (12').

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

Xj^O, x2 ^ 0, ... , xn ^ 0. Такие решения называются неотрицательными. Поэтому, так как решение системы неравенств сводится к решению соответствующей системы линейных алгебраических уравнений, то одним из важных вопросов линейного программирования является определение неотрицательных решений системы линейных уравнений.

Пример. Требуется определить неотрицательное решение системы неравенств:

Вводя дополнительные переменные jj^ ^ 0, jjl2 ^ 0, ja, ^ 0, получим систему уравнений:

Всякому неотрицательному решению этой системы уравнений соответствует определенное неотрицательное решение исходной системы неравенств, и наоборот. Так, например, неотрицательному решению xt = 1 ; х2 = 1 ; ja, = 1 ; ja2 = 2; ja, = 7 системы уравнений соответствует неотрицательное решение хг=\; х2=\ исходной системы неравенств.

Заметим, что если система неравенств несовместна в области неотрицательных решений, то соответствующая система линейных уравнений не имеет ни одного неотрицательного решения.

Известно, что наименьшее (наибольшее) значение линейной формы на многограннике, определяемом системой неравенств, достигается в определенной вершине многогранника решений. Можно показать, что каждой вершине многогранника решений отвечает неотрицательное решение соответствующей системы линейных алгебраических уравнений, причем по крайней мере одна дополнительная переменная равна нулю. Дополнительные переменные ja, ^ 0, ja2 ^ 0, ... , jaot ^ 0, вводимые в систему неравенств, можно иллюстрировать геометрически.

Рассмотрим многогранник решений системы неравенств:

Пусть имеется одно из неотрицательных решений х*у х\у ..., х„ системы неравенств. Ему соответствует точка М(х\у х\,.. . , д:°), принадлежащая многограннику решений.

Пусть h- обозначает расстояние от точки M до /-й гиперплоскости. Значения дополнительных переменных:

пропорциональны расстояниям от точки M (х\, л^, ... , х°п) до граничных гиперплоскостей:

Действительно, по определению расстояние от точки M до /-й гиперплоскости равно

откуда и следует, что:

ГЛАВА II

РЕШЕНИЕ ОБЩЕЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейное программирование — это раздел математики, в котором рассматриваются методы решения следующей задачи: задана система m линейных алгебраических уравнений с п переменными:

(13)

и линейная форма / тех же переменных

/= 'А + 'А + • • • + с/х/ + • • • + 'Л- (14)

Требуется среди решений системы (13) найти такое неотрицательное решение, при котором линейная форма / принимает минимальное значение*). Такое решение будем называть оптимальным решением данной задачи.

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

*) Аналогично формулируется задача для нахождения неотрицательного решения, при котором / принимает максимальное значение.

§ 7. Тождественные преобразования системы линейных алгебраических уравнений

Пусть задана система (13), содержащая г линейно независимых уравнений и разрешенная относительно г переменных. Без ограничения общности можно считать, что система разрешена относительно первых г переменных из первых г уравнений:

(15)

Система уравнений (15) в сокращенной записи имеет вид

Предположим, что свободные члены bi в уравнениях (15) неотрицательны.

Каждое из уравнений системы (15) можно рассматривать как проекцию векторного уравнения

(16)

на векторы Pv Р2, Рг, где P4 = Pt (1, 0, ... 0); Р2 = Р2(0, 1, ... 0); Рг = Рг(0, 0, ... 1).

Векторы Pv Р2, Рг образуют базис в г-мерном пространстве. При этом матрица разложений векторов Р0, Pv Р2, . .., Рг, ..., Рп в базисе Pv Р2, Рг представляется в виде

(17)

Допустим, что совокупность векторовPv Р2, Рг, Рг+1,Рп, входящих в уравнение (16), образует несколько базисов г-го порядка, отличающихся один от другого хотя бы одним вектором. Будем называть каждый из этих базисов собственным базисом.

Пусть Ах, Л2, ..., Ak, ... — собственные базисы системы векторов Рр Р2, Р„ Рг; Рг+1, Ру, Рп. При переходе от базиза к базису все коэффициенты уравнений (15) будут преобразовываться по формулам (7) предыдущей главы. Система (15) при этом будет переходить в эквивалентные ей системы, т. е. в системы с теми же решениями.

Базис А будем называть положительным по отношению к ненулевому вектору Р0, если Р0 представляется в этом базисе в виде Р0 = 2(М>/» ß/^O. Как видно из уравнений (15), базис Ау содержащий векторы Pv Р2, Рг, соответствующие разрешенным переменным, является положительным, так как по предположению bt ^ 0. Переменные (ххх2.. ,хг), относительно которых система (15) разрешена, называются основными, а остальные — неосновными. Решение системы, получаемое приравниванием неосновных переменных нулю, называется основным.

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

В дальнейшем мы будем рассматривать системы линейных алгебраических уравнений только в собственных положительных базисах. Поэтому для сокращения письма слова «собственный» и «положительный» опустим.

Рассмотрим систему (15). Определим правила перехода от одного базиса к другому. Для этого воспользуемся матрицей (17).

I. Находим один из столбцов j (r-j- 1 /г), у которого среди коэффициентов axj, a2/-, ..., air . .., arJ (1 =^r) при неразрешенной переменной Xj имеются положительные коэффициенты*) (случай, когда такого столбца не существует, рассматривается в § 8).

Пусть это будет столбец jx.

II. Определяем min \ — ^ по всем *» Для которых а{^ положительны. ^

*) Учитываются знаки коэффициентов, находящихся в скобках, при записи уравнений в виде системы (15).

Пусть одно из min отношений будет при i = iv Элемент назовем разрешающим по отношению к системе (15).

III. Разрешим /\-е уравнение относительно переменной дгу и подставим ее выражение в остальные уравнения системы (15). При этом система (15) перейдет в эквивалентную ей систему (18):

(18)

а группа векторов Р,, Р2, ..., Pi%mmV PyV • • •» Рг станет новым базисом А2. В самом деле. Из (18) следует, что эти векторы образуют базис, так как соответствующий им определитель отличен от нуля

Этот базис положительный, потому что новые свободные члены неотрицательны. Действительно, свободные члены имеют вид

Если a(jx > 0, то по правилу II — ^ — и свободный член

неотрицателен; если же а/у) ^ 0, то свободный член опять неотрицателен.

Преобразование системы (15) в систему (18), определяемое правилами 1, 11, 111, называется тождественным или симплекс-преобразованием.

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

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

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

Последовательности тождественных преобразований соответствует последовательность Л, —► А2 —► А8 —► ... переходов от базиса к базису. Так как при конечных г и п существует конечное число различных базисов, то в последовательности Ах—>А2—»As—.. должны быть возвращения к уже встречавшимся базисам. Будем говорить, что в этом случае имеет место «зацикливание».

Если при каждом тождественном преобразовании наименьшее отношение min /-^-i свободных членов bf к соответствующим коэффициентам где ik — номер столбца, содержащего разрешающий элемент аг/кУ отлично от нуля, то значение свободного члена в r-м уравнении системы (18) с каждым шагом только убывает, что видно непосредственно из выражения этого свободного члена. Выбор базиса одно-

*) Рассуждения, проводимые ниже, справедливы для любого /-го уравнения системы (15) (l^i^r).

значно определяет значение свободных членов системы уравнений, поэтому разным базисам соответствуют разные совокупности свободных членов, и наоборот. Поэтому в этом случае возвращение к одному из ранее встречавшихся базисов невозможно, а следовательно, не может быть и бесконечной последовательности преобразований. Это означает, что после конечного числа преобразований или все коэффициенты при неизвестных справа в г-м уравнении становятся неположительными, агу<;0 (г-\- 1 ^ п)у или разрешающий элемент при некотором преобразовании оказывается принадлежащим этому уравнению.

Если же, начиная с некоторого преобразования, разрешающий элемент принадлежит уравнениям с нулевым свободным членом biy то значение свободного члена в г-м уравнении остается неизменным. Действительно, из последнего уравнения системы (18) видно, что вычитаемое в выражении свободного члена br — arjx- в этом случае равно нулю. В этих условиях возникает возможность зацикливания.

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

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

Таким образом, необходимым условием зацикливания является существование вырождения.

В качестве примера рассмотрим систему уравнений:

Соответствующее векторное уравнение имеет вид д^Р, -j-~ЬХ2Р2~ЬхзР8= Ро — (х*РА-\-хшРш). При этом компоненты векторов определяют матрицу

Векторы Pv Р2, Ра, Р4, Р5 (рис. 17, а) образуют несколько базисов, например базисы Pv Р2, Р, и Р2, Р8, Р4. Базису

Pj, P2, P8 соответствует основное решение xl = 2; хг = 3; jcs = 2; л:4 = 0; л:5 = 0. В этом случае вектор Р0 представляется линейной комбинацией с положительными коэффициентами

Р„ = 2^ + 3^ + 2^.

Геометрически это означает, что вектор Р0 «пронизывает» параллелепипед, построенный на векторах Рр Р2, Р8 (рис. 17, б). Представим те же уравнения в базисе Р2, Р3, Р4. Для этого произведем тождественное преобразование. В колонке при переменной л:4 имеются положительные коэффициенты. Находим min (у; у ; у) . Принимаем за разрешающий элемент коэффициент при хх в первом уравнении. Разрешаем это уравнение относительно хА и полученное выражение подставляем в остальные два; при этом уравнения принимают вид:

Рис. 17.

Из последних уравнений следует, что в базисе Р2, Р8, Р4 вектор Р0 представляется в виде Р0 = 0-Р2 -f-P8 "b^Y В этом случае имеет место вырождение, так как вектор Р0 находится в базисной плоскости, определяемой векторами Рв и Р4, поэтому Р0 лежит на грани параллелепипеда, образованного векторами Р2, Р8, Р4 (рис. 17, в). Заметим, что если бы мы нарушили правила тождественных преобразований, то пришли бы к базису, в котором Р0 не может быть представлен неотрицательной линейной комбинацией векторов базиса. Напри-

мер, если за разрешающий элемент принять не тот, которому соответствует min ( ; у ; -у- J , а коэффициент при переменной л;4 в третьей строке, то после преобразования уравнений будем иметь:

Из этих уравнений следует, что в базисе Pv Р2, Ра вектор Р0 представляется отрицательной комбинацией, содержащей отрицательные коэффициенты

р^-гр.-зр. + гр,,

а решение оказывается неположительным:

х1 = —2; х2 = — 3; хл = 0; х4 = 2; х6 = 0.

В этом случае вектор Р0 не пересекает параллелепипеда, построенного на векторах Р,, Р2, Р4 (рис. 17, г).

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

Рассмотрим пример системы уравнений, тождественные преобразования которой могут привести к зацикливанию:

Будем рассматривать преобразования этой системы относительно третьего уравнения. В этом уравнении коэффициент при л;4 положителен и равен единице. Среди отношений /"ООП гл [у ; у; у отметим первое. Оно является одним из наименьших среди этих отношений. Поэтому за разрешающий элемент можно принять коэффициент при переменной хА в первом уравнении. После разрешения первого уравнения относительно л:4 и подстановки выражения хА в два других уравнения получим преобразованную систему:

В последнем уравнении снова имеются положительные коэффициенты при неременных в правой части, например при х6. Разрешающим элементом в этом случае является коэффициент при хь во втором уравнении, так как min |-р ; у) соответствует второму уравнению. Проведем тождественные преобразования, соответствующие новому разрешаещему элементу. В результате получим систему:

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

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

Как видим, после шести тождественных преобразований мы возвратились к исходной системе уравнений.

Таким образом, последовательность тождественных преобразований в базисах

приводит к зацикливанию.

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

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

Проведя тождественное преобразование, будем иметь:

Продолжая этот процесс, получим:

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

Произведя тождественные преобразования, соответствующие разрешающему элементу а48 = -^- и положив значение неосновных переменных равным нулю, мы найдем одно из основных решений исходной системы уравнений:

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

Покажем, что при наличии только двух уравнений

(19)

зацикливания быть не может. Матрица векторов, соответствующих системе (19), имеет вид:

По допущению Ь > 0. Тогда векторы Р, и Р2 образуют базис. Значение компонент вектора Р8 в этом базисе можно представить определителями

Пусть a2i и а,з больше нуля. Это означает, что уравнения (19) можно подвергнуть преобразованиям, переходя от базиса Vv Р2 к базису Р8, Р2 и принимая элемент а18 за разрешающий. В новом базисе Р„ Р2 коэффициенты уравнений (19) принимают значения, определяемые по формулам (7) предыдущей главы. Так, значения коэффициентов

при переменной хх будут иметь вид:

в первой строке во второй строке

Если числители этих выражений положительны, то в базисе Р„ Ря коэффициенты при х4 положительны. Так как наименьшее отношение для системы (19) снова приходится на первое уравнение, то, принимая коэффициент при хг в первом уравнении за разрешающий элемент, можно повторить преобразование системы уравнений, перейдя от базиса Р„ Р2 к базису Р4, Р2.

Допустим, что после каждого преобразования можно провести следующее так, что последовательность базисов

Pi. Р.^Р» Р. —Р4, Р2->... — Р*, Р, — Plf Р,

образует цикл. Тогда каждый из определителей в следующей последовательности:

(20)

должен быть положительным (определители нижнего ряда соответствуют последовательности положительных коэффициентов во втором уравнении, определители верхнего ряда — последовательности разрешающих элементов). В данном случае векторы Ру двухмерные, и поэтому значение каждого из определителей в последовательности (20) как по знаку, так и по величине совпадает с соответствующим векторным произведением. Тогда требование положительности всех определителей (20) равносильно требованию, чтобы вектор Р, лежал между векторами Рг и Р2, образующими острый угол; вектор Р4 — между векторами Р8 и Р2 и т. д. Продолжая эти рассуждения, получим, что вектор Pt должен лежать между векторами Pk и Р2, чего быть не может (рис. 18). Противоречие легко может быть обнаружено и аналитически. Запишем систему векторных равенств:

Рис. 18.

(21)

Умножая каждое из равенств (21) векторно один раз справа на Р2, а другой раз слева на второй вектор, входящий в правую часть каждого равенства, убедимся, что все коэффициенты в равенствах (21) положительны, так как по допущению все соответствующие векторные произведения также положительны. Так, для уравнения Р8 = =a8iPi + аз2Р2 имеем (Р8Р2) = а81 (РгР2) + а32 (Р2Р2), откуда а81 > 0. Умножая то же уравнение слева на Pv получим, что аа2 > 0. Далее, подставим в выражение для Pk вместо ï*k-\ его выражение, в полученное выражение подставим вместо Pä_2 его выражение и т. д. В результате будет иметь Pk = 4lkPx -f- f2kP2, ilk > 0; > 0, откуда

P, = — Pk — —P*.

Сопоставляя полученное равенство с последним равенством системы (21)

Pi = «,*р* + «Л ^>0; <*12>0, приходим к противоречию.

Покажем, что для образования цикла при любом числе п уравнений, п > 2, нужно совершить не менее шести тождественных преобразований. Так как мы рассматриваем только однократные замещения в базисах, то возвращение к исходному базису можно ожидать после 2k преобразований, где £=1, 2, 3, ... Возвращение при k=z\ невозможно, так как определители, отвечающие этому случаю, имеют вид:

Два последних определителя отличаются одной перестановкой векторов Р/ и Ру, а поэтому имеют разные знаки, что противоречит предположению их положительности.

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

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

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

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

Раскрывая эти семь определителей, будем иметь:

Из 1), 2), 4) и 7) следует, что ail/2 < 0. Из 2), 5), 6) и 7) следует, 4TOÛWi<°-

Введем обозначения:

*» с* kv qx — положительные числа.

Тогда из 3) имеем из 4) имеем • из 6)

Сопоставляя неравенство 1 > kxk с ранее полученным £,Л>1, обнаруживаем противоречие.

Итак, зацикливание может наступить только после того, как будет совершено не менее шести преобразований.

§ 8. Метод определения неотрицательного решения системы линейных алгебраических уравнений

Пусть задана система m линейных алгебраических уравнений с п переменными:

(13)

Без ограничения общности будем считать, что bi ^ 0 (этого всегда можно достигнуть умножением обеих частей соответствующих уравнений на —1).

Представим систему (13) в виде

(22)

Если в системе (22) имеется переменная, входящая только в одно уравнение, и коэффициент при переменной внутри скобок имеет знак «-["»» то такое уравнение можно разрешить относительно этой переменной.

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

или сокращенно:

где

Любое уравнение в системе (23), не разрешенное относительно какой-либо переменной, будем называть ^-уравнением.

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

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

1. Отыскиваем О-уравнение, у которого свободный член £у больше нуля. (Если такого О-уравнения нет, то значения переменных

xt = bt\ Xj = 0 (/=1,2, /0; yW0 + l, k)

образуют неотрицательное решение системы (23).) Пусть это будет /-е уравнение.

2. Отмечаем в /-м уравнении положительный коэффициент a(j **).

3. Находим разрешающий элемент a{jt и производим тождественное преобразование системы (23).

4. /-е О-уравнение используем для дальнейших преобразований системы до тех пор, пока мы не разрешим его или не установим, что система (23) несовместна**).

5. После разрешения 1-го О-уравнения отыскиваем следующее О-уравнение с положительным свободным членом и производим с ним аналогичные действия.

*) Если в системе (23) нет ни одного уравнения, разрешенного относительно какой-либо переменной, то 10 = 0, и система (23) состоит только из О-уравнений.

**) Если в /-м уравнении нет положительных коэффициентов при неизвестных, то система (23) оказывается несовместной, так как уравнение 0 = Ь( — (EcLijXj), в котором Ь( > 0, а все а{у ^ 0, не может быть удовлетворено ни при каких неотрицательных значениях переменных

6. Этот процесс продолжаем до тех пор, пока не освободимся от всех О-уравнений.

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

II. Пусть в исходной системе (23) или в преобразованной системе обнаружено уравнение, разрешенное относительно некоторой переменной, имеющее свободный член, равный нулю: X/= 0 — (Eß^), и такое, что все его коэффициенты при переменных в правой части неотрицательны. Так как роль таких переменных может быть только нулевая, чтобы Х( были неотрицательны, следует положить их равными нулю во всех уравнениях, от чего испытуемая система значительно упрощается. Аналогично исключаем те 0-уравнения, у которых свободный член равен нулю, а отличные от нуля коэффициенты при переменных в правой части имеют одинаковый знак. Значения этих переменных в остальных уравнениях принимаем равными нулю.

Рассмотрим, к каким результатам могут привести последовательные тождественные преобразования, удовлетворяющие условиям 1—6.

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

б) Возможно, что после конечного числа тождественных преобразований обнаружится, что используемое 0-уравнение превращается в уравнение вида

о=*;—CS *//*/>•

где */>0, aJy^O для всех у. В этом случае система несовместна.

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

уравнением

где s — сколь угодно малое положительное число, и рассматривая последнее уравнение вместе с разрешенными, мы видим, что в случае в) происходит зацикливание.

Изложенное выше дает возможность высказать следующее утверждение:

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

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

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

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

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

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

Рассмотрим примеры.

Проверка наличия положительных коэффициентов при неизвестных в уравнениях системы

система несовместна

Останов машины

Выбор первого положительного коэффициента ау/* в первом О-уравнении

Выбор положительных коэффициентов aty* в столбце /* среди всех уравнений системы

Вычисление отношений

Нахождение min —— среди чисел—L.

Разрешение уравнения /'* относительно переменной Лу*

Перемещение разрешенного уравнения на место первого в системе уравнений

Запоминание номера у* переменной х^

Исключение переменной Xj* из всех уравнений системы

Проверка наличия тождеств вида 0 = 0 в системе и соответственно сокращение числа уравнений

Проверка наличия 0-уравнений

Переход к поиску оптимального решения

Выдача неотрицательного решения

Рис. 19.

Пример. Определить, совместна ли система в области неотрицательных значений переменных:

В первом О-уравнении положительный коэффициент при а:,, равный единице, одновременно является и разрешающим элементом:

Во втором О-уравнении коэффициент при хг положителен; разрешающий элемент принадлежит первому уравнению:

Система несовместна, так как в последнем уравнении свободный член положителен, а оба коэффициента в скобках отрицательны; поэтому второму уравнению не удовлетворяет ни одна точка, для которой хх^0; х2^0.

Пример. Найти неотрицательное решение системы уравнений:

Производим тождественные преобразования системы:

Одно из неотрицательных решений системы есть

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

Примем ее столбцы за векторы Pv Р2, ...,Р„ и составим уравнение

в котором положим Р0 = РГ Ясно, что это уравнение имеет неотрицательное решение (например, хг = 1\ Xj=0; J = 2, 3, ... ,/z). Представляя векторное уравнение 0 = Р0 — (У] Х/Ру) в виде системы m уравнений и подвергая последнюю тождественным преобразованиям, освободимся от О-уравнений. Число разрешенных уравнений, полученное после исключения О-уравнений, определяет ранг матрицы. При этом, как можно показать, число преобразований, которые необходимо провести, также равно рангу матрицы. Пример. Найти ранг матрицы

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

I шаг

II шаг

III шаг

§ 9. Решение задачи линейного программирования

Задача линейного программирования, как сказано выше, может быть сформулирована следующим образом:

задана система m линейных уравнений с п переменными

(13)

и линейная форма /= сххх -\- с2х2 -f- ... -f- c;Xj -{-... -f- спхп тех же переменных. Требуется среди всевозможных неотрицательных решений

(jfj, Х2у , . é, хп)

системы (13) найти такое решение (х?; х\\ лг£), при котором / принимает наименьшее возможное значение.

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

в эквивалентную ей систему*):

Подставляя выражения основных переменных в линейную форму и вводя соответствующие обозначения для постоянных величин, представим / в виде линейной функции

(25)

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

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

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

*) После соответствующей перенумерации неизвестных.

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

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

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

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

при котором линейная функция

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

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

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

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

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

Пример. Определить наименьшее значение линейной функции f=5x1 — \0x2-\-7xs — Зл:4 на множестве неотрицательных решений системы уравнений:

(роль xt может быть только равна О!).

Пример. Среди неотрицательных решений системы неравенств:

найти такое, при котором линейная форма f=xx -J- х2 -f-я, достигает наименьшего значения.

Решение. Систему неравенств путем введения дополнительных переменных сводим к системе уравнений:

и подвергаем тождественным преобразованиям:

Одним из неотрицательных решений системы неравенств является решение х1 = -^; хг = 0; х3 = -g-. Выразим теперь линейную форму через неосновные переменные: /=2—

Как видно из последнего выражения линейной формы, дальнейшее ее уменьшение в области неотрицательных значений переменных невозможно. Поэтому первое решение хх = ^\ д:2 = 0; a;8 = -g- явилось и оптимальным, а соответствующее значение линейной формы /min = 2.

§ 10. Об одной задаче на минимакс

Пусть задано п /я-мерных векторов Ру и множество Т =2 = [tj) соответствующих им вещественных чисел tp j= 1, 2,. .. п.

Рассмотрим множество Y={y} всевозможных неотрицательных решений у = {лгу} уравнения

x1P1 + x2P2+...+xnPw = P0,

где Р0 — заданный вектор в т-мерном пространстве, не равный нулю.

Переменные Xj=^=0 в любом из решений у условимся обозначать через Xj, а соответствующие значения tj — через tj.

Через {tjy} обозначим систему чисел tj, соответствующих переменным Ху^О в решении у.

Наибольшее число среди системы чисел [tjy) условимся обозначать через t .

Таким образом,

Теперь поставим задачу:

Среди всевозможных решений у Ç У найти такое уоптУ для которого соответствующее

или

Решение у (если оно существует), удовлетворяющее этому условию, будем называть оптимальным и обозначать через .Уопт. Такие задачи называются задачами на минимакс. (Частным случаем этой задачи является транспортная задача по критерию времени, которая подробно рассмотрена в главе IV.)

Подвергая систему m линейных алгебраических уравнений с п переменными

соответствующую векторному уравнению ^лгуРу = Р0, тождественным преобразованиям, мы можем через конечное число шагов получить оптимальное решение.

Для этого надо:

1. Построить начальное неотрицательное решение системы уравнений.

2. Среди основных переменных х( найти ту, которой соответствует наибольшее значение tt, равное #"ах.

3. Исключить из дальнейшего рассмотрения неосновные переменные лгу., для которых tj ^ #"ах.

4. В /-й строке найти под знаком 2 положительный коэффициент afj* и определить разрешающий элемент a^j* после чего провести тождественное преобразование.

5. Повторяя (если необходимо) этап 4 несколько раз, вывести переменную х{ из совокупности основных переменных и исключить ее из дальнейшего рассмотрения.

6. Этапы 2 — 5 повторять до тех пор, пока на некотором шаге в соответствующей строке преобразованной системы уравнений все коэффициенты при переменных станут неположительными.

Основное решение, полученное на этом шаге, является оптимальным.

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

Пусть переменной xik соответствует наибольшее значение im?\ Тогда, если bik < 0, то, исключив xik из дальнейшего рассмотрения, получим несовместную систему. (Если ^ = 0, то согласно примечанию II на стр. 52 следует положить Х: =0, а также Лу = 0 для тех у, для которых 0/^у^5 0. После этого следует продолжить тождественные преобразования.)

ГЛАВА III

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ПО КРИТЕРИЮ СТОИМОСТИ

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

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

Первая задача является частным случаем задачи линейного программирования и может быть решена изложенным в предыдущей главе симплексным методом. Однако в силу особенностей этой задачи она проще решается так называемым комбинаторным методом. При малом количестве пунктов отправления и назначения этот метод позволяет решать такие задачи вручную. При большом количестве пунктов отправления и назначения задача может быть решена лишь с применением электронных вычислительных машин. Так, задача транспортировки из 30 пунктов отправления в 40 пунктов назначения решается на машине «Стрела» за 25—30 мин.

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

§ 11. Постановка задачи

Транспортная задача по критерию стоимости может быть сформулирована следующим образом.

Обозначим через av av..., ат количество единиц однородного груза, находящегося в каждом из m пунктов отправления, а через bv b2,. .., bn — количество единиц груза, потребного для каждого из п пунктов назначения.

Пусть x{j означает количество единиц груза, которое мы планируем для перевоза из /-го пункта отправления в у'-й пункт назначения, а Сц — стоимость перевозки единицы груза от /-го пункта отправления к у-му пункту назначения.

Таблица 2

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

(26)

Будем записывать условия такого типа задач в виде таблицы 2. Матрицу Х—(х^) порядка m X п с неотрицательными элементами Xij ^ 0, которая удовлетворяет условиям

(26') (26")

назовем решением задачи транспортировки. Условие (26') означает, что из /-го пункта отправления вывозится весь груз, а

условие (26") означает, что потребность у-го пункта удовлетворяется полностью. Задача сводится к определению таких неотрицательных значений xif1 чтобы общая стоимость перевозки была наименьшей.

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

Пусть задана матрица C=(c{j), где Су — вещественные неотрицательные числа. Требуется среди всех решений Ху записанных в виде матриц и удовлетворяющих условиям (26') и (26"), найти такое, для которого скалярное произведение (СХ) достигает минимального значения. Решение, представляемое матрицей X, удовлетворяющей этому условию, назовем оптимальным.

§ 12. Основные решения транспортной задачи по критерию стоимости

Рассмотрим заданную матрицу С=(с1у) и произвольную матрицу-решение Х=(Ху) (/=1, 2,..., т)\ (7=1, 2, ...,л). Будем считать, что т^п, так как в противном случае их можно поменять ролями.

Введем некоторые определения.

Пару натуральных чисел ij назовем клеткой, a произвольное множество клеток — набором. Последовательность клеток, имеющая вид iljv i1j2, i2j2, i2j\, называется цепью.

Цепь называется замкнутой, если она имеет вид

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

Каждой клетке ij соответствует один и только один элемент x(j матрицы-решения X, а также один и только один элемент си матрицы стоимости С. Поэтому всякий набор клеток является одновременно и набором соответствующих элементов как Хц, так и с^.

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

этой цепи с нечетными номерами образуют нечетную полуцепь 6Н, а элементы с четными номерами — четную полуцепь 6Ч.

Условимся сумму элементов Сц нечетной полуцепи обозначать через 2*7/' а СУММУ элементов четной полуцепи через

Теорема. Каково бы ни было решение X с циклическим набором отличных от нуля элементов x(j, существует решение Y с ациклическим набором элементов ytJ и такое, что (CY) (СХ), а число отличных от нуля элементов решения Y меньше числа таких же элементов решения X.

Доказательство. Пусть отличные от нуля элементы Xjj матрицы X образуют замкнутую цепь 6t. Сравним суммы 2jC;j и одна из СУММ> например 2^7» должна быть такой, что 2^7^2С/У

Образуем новую матрицу X' = (x-j) из матрицы Х = (х^) изменением элементов в цепи дх следующим образом:

Здесь /, jv /2 /2,..., ifjf — клетки нечетной полуцепи 6Н, а ixj2, tfji — клетки четной полуцепи в4, xfjn — наименьший элемент в нечетной полуцепи 6Н. Для всех других клеток ij положим х'ц = Хц.

Легко видеть, что матрица X', получаемая из матрицы X перемещением по цепи в элемента xfjn, также будет решением транспортной задачи. Число всех элементов х^, отличных от нуля, у матрицы X' станет по крайней мере на единицу меньше.

Так как (СХ')=(СХ) + (JJ с(/—geti) х™п, то (СХ')^(СХ).

Продолжая построение таких решений и далее, мы через конечное число шагов придем к решению Y, у которого отсутствуют замкнутые цепи в среди элементов Ху, отличных от нуля, a (CY) ^(СХ). Теорема доказана.

Следствие. Для нахождения хотя бы одного оптимального решения достаточно рассмотреть всевозможные решения X с ациклическими наборами отличных от нуля элементов Хц.

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

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

Теорема. Число N элементов х{/, отличных от нуля, в любом основном решении удовлетворяет условию п ^N^т-\-п — 1, где m — количество пунктов отправления, а п — количество пунктов назначения.

Доказательство. Предварительно убедимся в справедливости двух лемм. Построим в (тп)-мерном пространстве m X п векторов и поставим их во взаимно однозначное соответствие с множеством всех клеток ij матрицы С=(с/у). Клетке ij поставим в соответствие вектор Р/у., имеющий всё компоненты, равные нулю, за исключением 1-й и т-\-у-й, каждая из которых равна единице. Очевидно, всякому набору клеток соответствует некоторое подмножество векторов и, обратно, всякому подмножеству векторов соответствует некоторый набор клеток.

Лемма 1. Если множество векторов {Р/у} линейно зависимо, то соответствующий набор клеток циклический.

В самом деле. Пусть известно, что множество {Р/у} векторов линейно зависимо. Тогда существует линейная комбинация этих векторов, приводящая к нулевому вектору q (О, 0,..., 0), причем по крайней мере один из коэффициентов отличен от нуля. Будем рассматривать векторы, входящие в эту комбинацию, только с коэффициентами, отличными от нуля. Пусть это будет, например, вектор Р^д. Тогда обязательно в линейную комбинацию должен входить по крайней мере один вектор с тем же индексом /\, например Р^у2. Это происходит потому, что в векторе q все компоненты равны нулю, но поскольку в комбинацию входит вектор Pi1yl, то для обращения /-й компоненты в нуль надо иметь в комбинации по крайней мере еще один вектор с той же компонентой, отличной от нуля. Так как теперь входит вектор с компонентойу*2, то должен входить по крайней мере еще один вектор с такой же компонентой, например вектор Р/2/2. Рассуждая аналогично, мы построим последовательность векторов

Поскольку имеется только конечное число векторов, то после некоторого числа шагов мы должны прийти к вектору PitJn от него — к вектору Р,-,;1. Этой последовательности векторов соответствует набор клеток

который является циклическим.

Лемма 2. Всякий набор из т-\-п клеток является циклическим.

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

Рассмотрим (m я)-мерный вектор

Он ортогонален ко всем Р^. Отсюда следует, что все векторы P;j принадлежат m -\-п—1-мерному пространству, а поэтому всякие т-\-п из них линейно зависимы.

Из условия (26") § 11 и последней леммы следует, что n<^N<^т-\- п. А так как непосредственно на примерах можно убедиться, что существуют задачи, для которых N=n, и задачи, для которых N= m -\- п — 1, то окончательно получаем, что N действительно удовлетворяет условию п ^ ^т-{-п—1, и теорема доказана.

Из только что доказанных лемм следует, что множество векторов {Р,у}, соответствующее ациклическому набору из т~\-п—1 клеток, является базисом в (m -j- я)-мерном пространстве построенных векторов Р/;.. Обозначим через И произвольный ациклический набор из т-\-п—1 клеток.

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

Свойство 1. Пусть Их — некоторый ациклический т-\-п—1 набор и (ij) £ Нх*). Тогда набор Я2, полученный присоединением (ij) к набору Hv содержит один и только один цикл 6.

*) Знак Ç означает, что клетка ij набору Их не принадлежит.

Свойство 2. Пусть (/', /)=£(/, у) и (/', /) Ç в. Тогда набор Яв, получаемый из Н2 исключением клетки (/", у"), снова является ациклическим т-\-п—1 набором.

Наборы Их и о которых говорится в свойствах 1 и 2, отличаются только одной клеткой.

Определение. Два ациклических т-\-п—1 набора, отличающиеся только одной клеткой, называются ациклическими m -\-п—1 наборами однократного замещения.

Рассмотрим произвольное основное решение Х=(х^). По теореме (см. стр. 69) число N отличных от нуля элементов х^ удовлетворяет условию n^N^m-\-n — 1. Остальные /»ХЛ — N элементы решения равны 0.

Построим ациклический т-\-п — 1 набор H такой, что все отличные от нуля элементы Хц решения X расположены в клетках этого набора.

Определение. Элементы x{j решения X, равные нулю и расположенные в клетках ациклического т-\-п — 1 набора И у называются выбранными нулями.

Определение. Совокупность ненулевых элементов лг/у. основного решения X вместе с дополняющими их до ациклического т-\-п — 1 набора H выбранными нулями называется выбором.

Определение. Элементы Сц матрицы С, соответствующие элементам выбора Ху называются х-выбранными.

Следовательно, выбор есть основное решение, в котором из всех нулевых элементов X;f = 0 выделены те, которые дополняют множество ненулевых элементов x^j^O до ациклического m -)- п — 1 набора Н. Окончательно приходим к выводу, что для нахождения хотя бы одного оптимального решения достаточно рассмотреть всевозможные выборы.

§ 13. Оптимальный выбор

Методика определения оптимального решения заключается в том, что, отправляясь от некоторого начального выбора, мы переходим последовательно к другим выборам с меньшим значением скалярного произведения (СХ) и через конечное число шагов приходим к оптимальному решению. Поэтому возникает вопрос о построении первого выбора.

Рассмотрим следующий способ построения первого выбора.

Определяем элементы первой строки матрицы Х = (х^). Для этого в первой строке матрицы С=(с^) отыскиваем наименьший элемент. Пусть это будет элемент c\jv Тогда

полагаем хух = min (ах; bjx). Если ax^>bjv отыскиваем в той же строке второй наименьший элемент С\]г, удовлетворяющий условию С\]г^С\]х, и полагаем x\j2 = mm(ax—Хух\ Ь]2). Эти шаги продолжаем, пока полностью не удовлетворим первому уравнению ах = 2 xij- Если на некотором шаге этого процесса окажется, что остаток от ах точно равен соответствующему bjk, то, положив x\jk равным этому остатку x\jk = bJky дополнительно полагаем следующее, соответствующее по величине, значение переменной xiJk+x = 0. После этого переходим ко второй строке, третьей и т. д. При этом в столбцы, соответствующие уравнения которых полностью удовлетворены, нуль не записывается.

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

Для пояснения рассмотрим следующий пример. Пусть требуется построить первое решение для транспортной задачи, определяемой матрицей, представленной в таблице 3.

В первой строке наименьшим из чисел (8, 3, 5, 2) является число 2, поэтому принимаем x14 = min(10; 15) — = 10. Так как груз первого пункта отправления полностью распределен, то переходим к распределению груза второго пункта отправления. Для этого во второй строке таблицы 3 отыскиваем наименьшее из чисел (4, 1, 6, 7). Число 1 есть наименьшее. Поэтому полагаем х22 = min (15; 10) = 10. Так как в этом случае имеется остаток во втором пункте отправления, равный 15—10 = 5 единицам, то отыскиваем во второй строке следующий наименьший элемент. Это будет число 4. Полагаем x21 = min(15—10; 5) = 5. Учитывая, что потребность первого пункта назначения полностью удовлетворена, а остаток во втором пункте равен 0, отыскиваем третий наименьший элемент во второй строке. Таким элементом является число 6. Поэтому полагаем х23 = 0. Теперь переходим к распределению груза третьего пункта отправления. Для этого среди чисел

Таблица 3

(1, 9, 4, 3) третьей строки отыскиваем наименьшее. Так как потребность первого пункта назначения полностью удовлетворена, то число 1, стоящее на пересечении третьей строки и первого столбца, в расчет не принимается. Поэтому отыскиваем наименьшее из чисел (9, 4, 3). Число 3 наименьшее среди них. Полагаем лг84 = пип(25, 15 — 10) = 5. После этого находим в третьей строке следующее наименьшее число 4 и полагаем а:,8 = 20.

Легко убедиться, что полученное распределение есть решение. Кроме того, построенное решение является выбором. В самом деле, число выбранных элементов равно m -\- п—1 = = 3-J-4 — 1=6, и они не образуют между собою циклов.

Напротив, всякий не выбранный элемент x(j, как легко видеть, образует один и только один цикл с элементами выбора.

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

Пусть построен первый выбор — решение Хх с набором Нх. Пусть соответствующее скалярное произведение (СХХ) равно Cv Оценим каждый элемент Сф не входящий в Hv посредством выражения

суммы элементов соответственно нечетной и четной полуцепей единственной замкнутой цепи, образуемой каждым элементом Су с дг-выбранными (оцениваемый элемент с/у. принимается за первый в цепи в). Отметим элемент с^, которому соответствует наименьшая оценка Д™1", и его замкнутую цепь с jc-выбранными элементами. Построим второй выбор Х21 для чего передвинем наименьший элемент хут первого выбора из четной полуцепи в нечетную полуцепь. При этом, если в четной полуцепи имеется несколько элементов Хц, равных наименьшему х™п, то, для определенности, исключаем из набора Их клетку ij с элементом дг™ш, встречающуюся первой в четной полуцепи при обходе ее по часовой стрелке. Вместо исключенной из набора Нх клетки // вводим клетку ijv которой соответствует и новый элемент выбора х^ = хул (заметим, что за счет передвижения элемента x™ïn по цепи в выборе Х2 может оказаться несколько нулевых элементов). Так как выбор Х2 отличается

от выбора Хх только изменением в цепи элемента c-j^ то, если справедливо неравенство ^jß(cij)—^^/y<CÖ, скалярное произведение (СХ2) будет меньше (СХХ) на величину [^(citj)—^]*™m- Считывая, что х™т может оказаться равным нулю, мы приходим к выводу, что СХ^С2. Только что проведенное построение можно повторить и, отправляясь от выбора Х2, построить выбор Хг и т. д. В результате образуется последовательность выборов Хх, Х21 Xk1 ... такая, что соответствующая последовательность значений скалярных произведений Сх ^ С2 ^ . . . ^ Ck ^ ... является невозрастающей функцией номера выбора.

Выбор Хк с набором Hk называется оптимальным, если каждый из элементов c{J, не входящих в Hk, имеет неотрицательную оценку Д^О.

Так как для любого элемента Сф не входящего в набор Hk, справедливо неравенство ^(cij) — ^CU^*®> то пеРех°Д посредством однократных замещений к любому другому выбору от выбора Xk, не может уменьшить значение скалярного произведения по сравнению со значением скалярного произведения Ck, соответствующего выбору Xk*).

Теорема. Для всякой матрицы С=(с^) с вещественными элементами при а{^>0, bj^>0 последовательность выборов Хх, Х2, Xk, ... через конечное число шагов заканчивается оптимальным выбором.

Доказательство.

/ случай. Если при переходе от выбора к выбору при построении последовательности Хх, Х2, ... ни в одном из выборов не появляется лг/у. = 0, то и x?/in, переносимое по цепи, отлично от нуля. В этом случае значение скалярного произведения с каждым шагом уменьшается. А так как при конечных тип может быть только конечное число различных наборов /У, на каждом из которых однозначно определяется выбор, то бесконечного числа шагов быть не может.

// случай. Если при переходе от выбора к выбору в последних могут появляться нулевые значения xtj, то возникает сомнение в конечности последовательности Хх, Х2У ..., так как в этом случае лг/уш = 0, и значение скалярного произведения

*) Ниже будет показано, что оптимальный выбор есть в то же время и оптимальное решение,

не уменьшается. Однако сомнение полностью устраняется, если наряду с исходной задачей транспортировки рассмотреть задачу с той же матрицей С=(с/у), но с

где s — достаточно малое положительное число. Назовем эту вторую задачу е-задачей. Построим первые выборы Хх и Х\ для этих двух задач. Тогда в силу малости s наборы Нх и Н\ совпадут и в выборе Х\ не будет нулевых элементов jt//=0. В самом деле, появление нулевых значений x(j в выборе в исходной задаче происходит в тех случаях, когда существуют такие сочетания строк и столбцов, что имеют место равенства

Поэтому появление нулевых значений х^ в задаче может быть в двух случаях:

Выбирая s отличным от корней уравнений, выражаемых условиями а) и б), мы исключаем возможность появления нулевых элементов в выборе Х\. Так как матрица C=(c{j) одна и та же для обеих задач, то совпадают элементы с наибольшей отрицательной оценкой, замкнутые цепи этих элементов с элементами выборов Хх и Х\, а также положение в наборах Н\ и Н\ элементов х™п и подлежащих переносу по цепи. Переход от выбора Хх к выбору Хг в исходной задаче является переходом от выбора Х\ к выбору Х\ для е-задачи. В силу малости s эти рассуждения справедливы на любом шаге. Так как е-задача является задачей при отсутствии Ху = 0, когда имеет место уменьшение скалярного произведения на каждом шаге, то для е-задачи через конечное

число шагов мы придем к оптимальному выбору Х%. В силу совпадения матриц C=(ci}) и наборов Hk и /У|, выбор Xk также является оптимальным. Теорема доказана.

§ 14. Инвариантность последовательности выборов эквивалентным преобразованиям матрицы стоимости

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

Для этого введем понятие эквивалентного преобразования матрицы.

Определение. Пусть задана матрица С = (c(j) и произвольные числа гх\ г2; rm; sv s2, sn. Назовем матрицу D = (d{j) эквивалентной матрицей C=(ctj), если она получена из матрицы С по формуле D = (ci;--\- r(-\- Sj).

Теорема. Последовательность выборов инвариантна относительно эквивалентных преобразований матрицы.

Доказательство. Преобразуем матрицу С в эквивалентную ей матрицу D. Построим для матрицы С начальный выбор Хх и, отправляясь от него, посредством однократных замещений построим последовательность Х1У Х2У Xz, сходящуюся к оптимальному выбору Xk.

Отправляясь от того же самого выбора Хг, построим последовательность Х1У Х[, Х'г, .. . для матрицы Д сходящуюся к оптимальному выбору X'k. Легко видеть, что разность оценок Azy — Д^- для любых двух элементов cjj и c?j, не входящих в выбор Х1У равна нулю:

Последние две суммы равны по величине и противоположны по знаку, так как всякое число г{ (или Sj), содержащееся в нечетной полуцепи, содержится и в четной полуцепи.

Поскольку оценки элементов для матриц С и D совпадают,

то совпадают и элементы с наименьшей оценкой. Поэтому при переходе от выбора Хх к следующему выбору как для матрицы С, так и для матрицы D выборы Х2 и Х[ совпадают. Проведенные рассуждения остаются справедливыми на любом шаге. Это означает, что последовательность Хх, Х2, Xk выборов не изменяется при эквивалентных преобразованиях матрицы. Теорема доказана.

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

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

Матрица с нулевыми л;-выбранными элементами обладает тем свойством, что оценка любого из ее элементов, не являющегося лг-выбранным, равна самому элементу. Поэтому не требуется производить огромные расчеты для определения оценок всех элементов. Для построения следующего выбора достаточно указать наибольший отрицательный элемент (по абсолютному значению). Если же все элементы преобразованной матрицы оказываются неотрицательными при нулевых л:-выбранных элементах, то последний выбор и есть оптимальный. Из инвариантности последовательности матриц следует, что оптимальный выбор есть в то же время и оптимальное решение. В самом деле. Оптимальный выбор с эквивалентно преобразованной матрицей, у которой х-выбранные элементы равны нулю, обладает тем свойством, что скалярное произведение для него меньше (или, в крайнем случае, равно) скалярного произведения любого из решений. Поэтому найденный нами оптимальный выбор есть оптимальное решение.

§ 15. Алгоритм нахождения оптимального решения

I. Условия задачи записываются в виде таблицы.

II. Определяем первый выбор.

III. Обращаем х-выбранные элементы в нули. Если при этом остальные элементы преобразованной таблицы оказываются неотрицательными, то первый выбор и является оптимальным.

IV. Если после обращения дс-выбранных элементов в нули в таблице имеются отрицательные числа, то находим наибольший отрицательный элемент (по абсолютному значению).

V. Образуем замкнутую цепь наибольшего отрицательного элемента с обращенными в нуль лг-выбранными элементами и строим второй выбор, передвигая по цепи число лг/у-, равное наименьшему в четной полуцепи.

VI. Так как наибольший отрицательный элемент стал л:-выбранным, то обращаем его в нуль, но так, чтобы остальные л;-выбранные элементы, соответствующие новому выбору, оставались также равными нулю.

Рис. 20.

VII. Эти шаги повторяем до тех пор, пока не придем к выбору, для которого в преобразованной таблице все л;-выбранные элементы равны нулю, а остальные — неотрицательные. Этот последний выбор и будет оптимальным решением.

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

Для наглядности процесса нахождения оптимального решения приведем его геометрическую интерпретацию (рис. 20).

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

ная таблица не имеет отрицательных элементов, то решение, соответствующее точке Av и есть оптимальное. Если этим свойством преобразованная таблица не обладает, находим точку А2 и вновь возвращаемся на оси в точку А'2 и исследуем, не достигли ли мы оптимального решения. Если нет, определяем точку А8 и т. д.

Через конечное число шагов мы обязательно достигнем последней точки, которой и соответствует оптимальное решение. Мы получим ломаную стоимости, как изображено на рис. 20. Как видно из рисунка, с каждым шагом значение стоимости уменьшается (во всяком случае не возрастет).

Таблица 4

Продолжим решение транспортной задачи, поставленной на стр. 72. Первый выбор для нее представляется таблицей 4. Обращаем лг-выбранные элементы в нули. Для этого из элементов первого столбца матрицы стоимости вычтем 4, из элементов второго столбца — вычтем 1. В результате л:-выбранные элементы, стоящие на пересечении второй строки с первым и вторым столбцами, обратятся в нули. Из элементов третьего столбца вычтем 6, тогда л;-выбранный элемент, стоящий на пересечении второй строки с третьим столбцом, также обратится в нуль, а элемент матрицы стоимости, стоящий на пересечении третьей строки и третьего столбца, примет значение, равное (4 — 6 = —2). Прибавим к элементам третьей строки матрицы стоимости число 2, а из элементов четвертого столбца вычтем число 5. Тогда элементы, стоящие на пересечении третьей строки с третьим и четвертым столбцами, обратятся в нули.

Наконец, остается обратить в нуль л:-выбранный элемент, стоящий на пересечении первой строки и четвертого столбца. Для этого к элементам первой строки нужно прибавить число 3. В результате такого эквивалентного преобразования матрицы стоимости таблица 4 примет вид таблицы 5.

Как видно, в таблице 5 имеется отрицательный элемент (—1). Поэтому мы не можем быть уверены, что первый выбор является оптимальным. Так как в данном примере имеется один отрицательный элемент, то он же является и наибольшим (по абсолютной величине).

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

Таблица 5

Таблица 6

Таблица 7

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

вого столбца в таблице б число, равное 1. В результате получим таблицу 7, в которой нет ни одного отрицательного элемента, а все дг-выбранные элементы равны нулю.

Поэтому выбор, представленный в таблице 7, является оптимальным решением. Соединим в одну таблицу 8 исходную матрицу стоимости и оптимальное решение. Стоимость перевозок, соответствующая этому плану, составляет С=2-10-|-—1~ 5 • 6 10-1 5 • 3 —4-15 —1 - 5 = 140 единиц стоимости.

Таблица 8

Рис. 21.

Согласно этому плану перевозку нужно организовать следующим образом (рис. 21). Весь груз первого пункта отправления транспортируется к четвертому потребителю; второй пункт отправления обеспечивает 10 единицами груза второго потребителя и 5 — третьего; с третьего пункта отправления 5 единиц груза транспортируется к первому потребителю,

15 — к третьему, а остальные 5 единиц груза доставляются четвертому потребителю. При таком плане стоимость перевозок (при всех прочих равных условиях) будет минимальна. Рассмотрим более сложный пример.

Пример. Найти оптимальный план перевозки однородного груза из четырех пунктов отправления в шесть пунктов назначения при условиях, определяемых таблицей 9. В этой таблице ai% bj выражены в тысячах тонн, а с{, — в тысячах рублей.

Таблица 9

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

Таблица 9а

Таблица 9б

Таблица 9в

Таблица 9г

Таблица 9д

Таблица 9е

Соединим вместе первоначальную таблицу стоимости и оптимальное решение (таблица 10).

Таблица 10

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

Интересно отметить, что таблица с оптимальным вариантом (5-й выбор) указывает не одно оптимальное решение, а все решения с той же стоимостью.

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

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

Это позволяет принять за оптимальное решение, например, такое, как представлено в таблице 11. Стоимость, соответствующая этому плану перевозок, также равна

С= 1.2 + 4-3+ 4.1 + 1-5+ Ы + 1-2+ 1.2 + 5-1 + + 3-5 = 48.

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

ния оптимального варианта перевозок по времени, можно указать план перевозок, реализация которого требует наименьшего времени.

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

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

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

Мы рассмотрели методику решения транспортных задач по критерию стоимости при условии, что 2а*"= В этом случае количество груза во всех пунктах отправления равно количеству потребного груза для всех пунктов назначения.

Таблица 11

Если S^i^S^y» т0 вводим фиктивный пункт назначения с потребностью ^„+1 = 2а/ — и со стоимостью перевозки груза в этот пункт rt+1 = 0 для /=1, 2, т.

Таблица 12

Таблица 13

Пример. Пусть в четырех хранилищах имеется соответственно 70, 40, 50, 20 тонн горючего. Требуется спланировать перевозки горючего к трем потребителям так, чтобы затраты на транспортировку были минимальны. Пусть условия задачи определяются таблицей 13. В этом случае построение первого решения целесообразно вести по столбцам. Это решение отмечено кружками в таблице 14.

Легко проверить, что решение, представленное в таблице 14, является оптимальным. Согласно этому решению к первому

потребителю надо подвезти 10 тонн из первого и 20 тонн из четвертого хранилища, ко второму потребителю 30 тонн из первого и 10 тонн из второго хранилища, к третьему потребителю 30 тонн из второго хранилища, при этом в первом хранилище еще остается 30 тонн горючего, запасы третьего хранилища в данных условиях использовать нецелесообразно.

Таблица 14

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

Таблица 15

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

Для матриц порядка m X л <С 500 время решения задачи не превышает 8—10 минут; для матриц порядка ^ХЯ<при решении задачи может потребоваться до 25—40 минут; для матриц порядка /я X я в несколько тысяч для решения задачи на машине «Стрела» требуется до 8—10 часов.

Так, на машине «Стрела» была решена следующая транспортная задача.

Построение начального выбора

Обращение я-выбранных элементов матрицы стоимости в нули (преобразование матрицы)

Отыскание в преобразованной матрице наибольшего по абсолютной величине отрицательного элемента

Контроль окончания решения: проверка наличия отрицательных элементов в преобразованной матрице

Отыскание замкнутой цепи, образуемой наибольшим по абсолютной величине отрицательным элементом и х-выбранными элементами

Построение нового выбора

Вычисление стоимости перевозок по оптимальному плану

Выдача оптимального плана перевозок и соответствующей стоимости

Останов машины

Рис. 22.

Требуется из девяти пунктов отправления перевезти груз к четырнадцати пунктам назначения (таблица 15). Начальный выбор, полученный на машине, представлен в таблице 16.

Таблица 16

Конечный выбор, соответствующий оптимальному решению, изображен в таблице 17.

Легко подсчитать, что величина стоимости, соответствующая начальному выбору, имеет значение, равное С = 971, а для оптимального С=703.

Таблица 17

Время решения этого примера (в один просчет) составило около одной минуты.

Время решения другой транспортной задачи с матрицей стоимости /и X я = 30 X 38 (при двойном просчете) составило 37 минут.

ГЛАВА IV

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ПО КРИТЕРИЮ ВРЕМЕНИ

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

Задача такого типа является задачей транспортировки по критерию времени. Ниже рассматривается один из алгоритмов решения транспортной задачи по критерию времени.

§ 16. Постановка и решение задачи

Пусть имеется m пунктов отправления однородного груза и п пунктов назначения. Обозначим через av а2, ... ..., а,., .. ., ат количество единиц груза, находящегося в первом, втором, ..., 1-м, ..., т-м пунктах отправления, а через bx, Ь2, bj, bn — количество единиц груза, которое должно быть доставлено в каждый из п пунктов назначения. Пусть ttj есть время (в сутках, часах), потребное на перевозку груза из /-го пункта отправления в у-й пункт назначения, a xtj — количество единиц груза, которое мы планируем перевезти из /-го пункта отправления в у-й пункт назначения. Требуется найти оптимальный план перевозок, т. е. такие неотрицательные числа х^, при которых время доставки всех необходимых грузов к пунктам назначения было бы минимально.

Математическая формулировка этой задачи сводится к следующему.

Задана система линейных алгебраических уравнений:

причем числа а( и bj удовлетворяют условию

Пусть, кроме того, задана матрица времен T=(t{j). Каждому неотрицательному решению X = (xtj) системы уравнений (27), т. е. плану перевозок, соответствует определенная матрица Tx = (tij), элементы которой равны tij = tij.i если лг^^О, ^• = 0, если лг,у = 0. Обозначим через /™ах наибольший элемент матрицы fx:

Требуется определить такое неотрицательное решение Л^опт, для которого ^?зх будет наименьшим среди всех *™ах, соответствующих различным неотрицательным решениям X. Условия этой задачи удобно представить в виде таблицы 18.

Таблица 18

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

Так, например, решение, для которого линейная форма С=2^ул:/у достигает минимального значения, как правило, не является оптимальным по времени. Для примера, заданного таблицей 19 и изображенного на рис. 21, оптимальное решение

по минимуму линейной формулы С=2представляется таблицей 20. Из этой таблицы видно, что весь груз будет доставлен в пункты назначения только через шесть суток. С другой стороны, варианту перевозок, представленному в таблице 21, соответствует несколько большее значение линейной формы, но перевозка грузов к пунктам назначения выполняется за четверо суток.

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

Доказательство описываемого ниже метода решения следует из общей теории линейного программирования, изложенной в главе II.

Таблица 19

Таблица 20

Таблица 21

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

Таблица 22

Вышенаписанную таблицу (будем называть ее малой) представим в виде большой таблицы (таблица 23).

Верхняя строка содержит индексы переменных x(j от 11 до 67, а нижняя — значения^., содержащиеся в соответствующих клетках ij. Например, пара чисел 43 в верхней строке означает место переменной х48, а соответствующее этой переменной значение времени ti9 есть 39; поэтому 43 и 39 находятся в одной колонке.

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

Таблица 23

выражение остатка груза в четвертом пункте отправления:

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

27 х14 л;24 хгх л;44 л;54 хв4.

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

Построим первое решение, используя способ, который применялся в главе III. 15 единиц первого пункта отправления распределим между пунктами назначения с наименьшим временем пробега; 7 единиц второго пункта отправления — между не удовлетворенными еще пунктами назначения с наименьшим временем пробега и т. д. Это дает нам первое решение (вообще говоря, еще не оптимальное), представленное таблицей 24,

Таблица 24

Как видим, элементарное построение привело к решению, реализация которого требует 28 часов на перевозку грузов. Это позволяет нам в дальнейшем исключить из рассмотрения клетки с ^у>28, что и сделано в приведенной таблице.

Для построения следующего варианта решения, реализация которого требовала бы менее 28 часов, обратимся к большой таблице. Построение первого выбора применительно к этой таблице происходит так: в нижней строке значений t(j отыскиваем наименьшее из чисел в первой полосе. Это — число 7, соответствующее колонке 14, т. е. переменной л:14. Просматривая эту колонку, убеждаемся, что л:14 можем положить равным

15, так как запас груза составляет 15 единиц, а потребность—27. Это позволяет записать переменную ххх слева от равенства в первой строке, а знак минус на пересечении первой строки и колонки 14 опустить. Что касается второго минуса этой колонки, стоящего против 27, то его также нужно опустить, а из строки, соответствующей числу 27, вычесть строку, соответствующую числу 15.

В первой и десятой строках в первой полосе произошли изменения. Эти изменения имеют вид:

Переходим ко второй строке и второй полосе. Отыскиваем наименьшее из чисел tt, второй полосы. Это число 6, соответствующее переменной х26. Пробегая колонку по вертикали, выбираем наименьшее из двух чисел, стоящих слева против минусов этой колонки. Это число 5. Записываем слева от равенства против 5 переменную л:2в, опуская минус, стоящий на пересечении этой строки и колонки 26. Минус опускаем также на пересечении второй строки и колонки 26, а из второй строки, соответствующей числу 7, вычитаем строку, соответствующую числу 5. Во второй строке остается число 2. Это означает, что груз второго пункта отправления еще не распределен между пунктами назначения. Поэтому во второй полосе в строке значений отыскиваем следующее по величине число. Это число 7, стоящее в колонке переменной х2х. Пробегая по колонке, находим наименьшее из чисел слева против минусов колонки (20, 2). Опускаем минусы в колонке 21, записываем слева от равенства против 2 переменную х21 и вычитаем из седьмой строки вторую. Этим заканчиваем распределение единиц второй строки. Этот процесс продолжаем до распределения единиц шестой строки. В результате получаем первое решение, совпадающее с решением, записанным в таблице 24. Большая таблица теперь преобразовалась в таблицу 25.

В правильности решения убеждаемся отсутствием « » и « — » в одной из строк. В этой строке, в случае отсутствия ошибок в распределении, должны быть только нули. Такой строкой в данном примере оказалась последняя. (В силу условия —2^/ одно из уравнений системы (27) должно быть следствием остальных.)

Таблица 25

В таблице колонки, соответствующие основным переменным, обозначены прямой штриховкой, а колонки, для которых соответствующие >28, — косой. Последние из дальнейшего рассмотрения исключаем. Таблица 25 указывает пути построения лучшего варианта по сравнению с первым. В самом деле, нам желательно найти такое решение, в котором бы переменная, стоящая в той же колонке, что и /.у = 28, т. е. л:в7, равнялась бы нулю. Но шестая строка в этой таблице показывает, что уменьшение значения переменной х91 может быть получено за счет увеличения или хй1, или x6i.

Таблица 26

Поскольку переменной л;в1 соответствует /в1=15, а переменной jce5 /в5 = 23, то произведем уменьшение х61 за счет увеличения лгв1. Пробегая по колонке 61, находим, что наименьшим числом, стоящим с левой стороны таблицы против « — » колонки 61, является значение хв7 = 5.

Теперь произведем преобразование последней таблицы следующим образом. Исключим колонки с косой штриховкой и колонку, соответствующую переменной х61 (или, что то же,— числу ttj, равному 28). Вместо л:в7 напишем хв1. Далее, из строк с минусами в колонке 61 вычтем строку, соответствующую переменной л:в1, а к строкам с плюсами в колонке 61 прибавим строку, соответствующую той же переменной, после чего в колонке 61 все « — » и « -\- » исчезнут.

В результате получим таблицу 26. Из этой таблицы следует, что нами построено второе решение, реализация которого требует значительно меньше времени: не 28 часов,

а только 21. (Заметим, что если бы обращение переменной х61 в 0 мы начали производить не за счет увеличения x6V а за счет увеличения хв5, то был бы построен вариант решения с максимальным временем = /в5 = 23. После этого, вычеркивая все колонки с ti;^>2Sy нам нужно было бы сделать еще шаг для построения третьего решения с максимумом г/у. = 21.)

Отметим переменные, изменение которых привело ко второму решению: л:в7, хгъ, л;47, х81, л;48, хьх. Эти переменные образовали замкнутую цепь (таблица 27). Занумеруем клетки с переменными, образовавшими цепь, принимая клетку с переменной хв7 (подлежащей исключению) за первую. Эта цепь обладает тем свойством, что в ее нечетных клетках находятся обязательно лг-выбранные элементы, а в четных — значения tu^t^K, где — значение ttj, подлежащее исключению (в данном случае t^K = 2S). Назовем такую цепь разгрузочной. После нахождения разгрузочной цепи для образования нового решения передвигаем по цепи количество единиц груза, равное минимальному из них в нечетной полуцепи. Это построение на малой таблице приводит нас ко второму решению, совпадающему со вторым решением, построенным на большой таблице. Исключим из дальнейшего рассмотрения колонки (клетки) со значениями г/;.>21. В результате получаем малую таблицу 28 и большую таблицу 26 (считая колонки 41, 55, 65 вычеркнутыми). Спрашивается: имеется ли более оптимальное решение, т. е. решение, реализация которого требует менее 21 часа? Для ответа на поставленный вопрос обращаемся к таблице 26. В строке значений t.j отыскиваем наибольшее— 21. Этому значению г84 = 21 соответствует переменная x9V в строке которой находятся только «-]-». Отсутствие

Таблица 27

« — » означает невозможность уменьшить значение л:34 за счет какой-либо переменной. Вывести л:34, а следовательно, и освободиться от /34 = 21 не представляется возможным. Таким образом, полученный последний вариант является оптимальным по времени. Его реализация, как уже сказано выше, требует 21 часа. В малой таблице 28 в этом случае не представляется возможным построить разгрузочную цепь.

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

Правила нахождения оптимального варианта по времени при пользовании малой таблицей сводятся к следующему:

1. Записываем условие задачи в малой таблице.

2. Находим первое решение (например, указанным выше способом).

3. Определяем f//max, соответствующий этому решению.

4. Зачеркиваем в таблице все клетки с f/y>///max.

5. Исследуем tjjmax на наличие разгрузочных цепей с оставшимися элементами в таблице.

6. При наличии разгрузочных цепей строим новое решение.

7. Если не представляется возможным полностью разгрузить клетку, соответствующую /Jymax (обратить соответствующее Хц в 0), то решение с tfjymax является оптимальным.

8. При полной разгрузке клетки с //ушах находим //утах во вновь полученном решении.

Таблица 28

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

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

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

Можно привести и другие приемы решения этой задачи.

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

§ 17. Решение задач транспортировки с учетом времени и стоимости

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

Для рассмотренного выше примера оптимальный вариант по стоимости представляется таблицей 29 и выполняется, как

Таблица 29

видно, за 28 часов при стоимости затрат на перевозки С=/Г(7.15 + 6-5 +10-2 +11- 20 +20.13+21.12+ 5-9+ +12.21 + 14.12+16-11+28.5)=К- 1668 единиц стоимости. Стоимость перевозок, соответствующая оптимальному варианту по времени (таблица 28), составляет 0 = 7^(7«15 + 7-2 + + 6-5+ 11 - 13 + 20-13 + 21 .12 + 21.7 + 5.2+12.28 + + 14« 12+15 -5+16« 11 ) = 1716/С единиц стоимости. Затрачивая дополнительную стоимость, равную 1716 К— 1668 Ä== = 48 К, мы завершим операцию перевозки грузов на 7 часов раньше по сравнению с планом перевозок, определяемым оптимальным вариантом по стоимости.

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

Таблица 30

Таблица 31

портировки, то, используя описанные методы, можно найти оптимальный вариант по стоимости, реализация которого осуществляется в пределах заданного срока. Если же потеря времени недопустима, то определяем оптимальный вариант по времени. Если полученный вариант с t*}JT не является лучшим по стоимости, то, применяя алгоритм нахождения оптимального решения по минимуму линейной формы, можем получить оптимальный по стоимости из всех оптимальных по времени (выполняемых за одно и то же время, равное $/т). Так, оптимальное решение по времени для рассматриваемого примера, представленное таблицей 30, не является оптимальным по стоимости.. В самом деле, обратим лг-выбранные элементы в 0 (при обращении л;-выбранных элементов в 0 значения элементов, стоящих в перечеркнутых клетках, во внимание не принимаются) (таблица 31).

В результате получим таблицу, в которой имеется отрицательное число ( —14). Преобразовав еще раз таблицу 31, получим таблицу 32. В преобразованной таблице 32 л:-выбранные элементы равны 0, а остальные неотрицательные.

Таблица 32

Поэтому построенный вариант решения является оптимальным по стоимости. Стоимость реализации этого варианта, выполняемого также за 21 час, составляет 0=1688/^, что значительно меньше, чем 1716 К.

* * *

За последние годы методы линейного программирования находят все более широкое применение в таких областях, как экономика, техника, военное дело и т. п. Теория и методы

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

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

ЛИТЕРАТУРА

1. Л. В. Канторович, Математические методы организации и планирования производства, изд. ЛГУ, 1939.

2. Л. В. Канторович и М. К. Гавурин, Математические методы анализа грузопотоков, сб. АН СССР «Проблемы повышения эффективности работы транспорта», 1953.

3. Б. М. Каган и Т. М. Тер-Микаэлян, Решение инженерных задач на автоматических цифровых вычислительных машинах, Госэнергоиздат, 1958.

4. А. И. Китов, Электронные цифровые машины, изд. «Сов. радио», 1956.

5. А. Г. Курош, Курс высшей алгебры, Физматгиз, 1959.

6. Л. А. Люстерник, Выпуклые фигуры и многогранники, Гостехиздат, 1956.

7. С. И. Черников, Линейные неравенства, УМН, т. 8, вып. 2 (1953).

8. Н. В. Черникова, Наименьшие и наибольшие значения линейной формы на многограннике, УМН, т. 12, вып. 2 (1957).

9. A. Charnes, W. W. Cooper and A. Henderson, An Introduction to Linear Programming, John Wiley, New York, 1953.

10. C. W. Churchman, R. L. Ackoff, C. L. Arnoff, Introduction in Operations Research, London —New York, 1955.

11. D. Chandler, Linear Programming and Computers, New York, 1955.

12. A. Glaisel, Algorithm for Solution of Transportation Problem, 1955.

13. S. Vajda, The Theory of Cemes and Linear Programming, London— New York, 1956.