Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf

-ниях, налагаемых на эти переменные (например, ограничения вида (7)), рассматривались в математическом анализе уже давно и получили название задач на условный экстремум с использованием аппарата дифференциального исчисления (например, метод Лагранжа). Однако при применении этих методов к задачам линейного программирования возникают дополнительные трудности. Объясняется это тем, что указан­ ные методы дают возможность определить локальные экстре­ мумы функций (т. е. экстремальные ее значения по сравнению со значениями Ь некоторой окрестности данной точки), а не так называемые глобальные экстремумы (т. е. наибольшие или наименьшие значения функции в данной области). А именно это, последнее, и представляет интерес в задачах ли­ нейного программирования.

методов исследования на экстремум. Однако наибольшее зна­ чение данной функции на отрезке (а б) достигается не в точ­ ке х\, а на границе заданного отрезка, ибо /( б) > Zmax = fix,)-

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

(7) —(8) и нахождение в этой области оптимального решения.

К р а т к а я и с т о р и ч е с к а я с п р а в к а

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

11

ревозок встречается в работе советского экономиста

A.Н. Толстого (1930 г.).

В1931 г. венгерский математик Б. Эгервари рассмотрел в математической постановке одну из частных задач линейного программирования, получившего название «проблемы выбо­ ра». Этот метод в последующем был развит американским ма­ тематиком Г. У. Куном применительно к общему классу транс­ портных задач и получил название венгерского метода.

Систематическое исследование задач линейного програм­ мирования, разработка общих методов их решения были на­ чаты в 1939 г. в работах советского математика академика Л. В. Канторовича и его учеников. Л. В. Канторовичем был предложен общий метод решения задач линейного програм­ мирования, названный им методом разрешающих множителей, тесно связанный с проблемой двойственности. Этот метод ма­ ло чем отличается от общепринятого сейчас симплексного ме­ тода. Для решения транспортных задач им же совместно с М. К. Гавуриным в 1949 г. был предложен метод потенциалов, представляющий собой реализацию метода разрешающих множителей применительно к решению транспортной задачи. В последующих работах Л. В. Канторовича, В. С. Немчинова, B. В. Новожилова, А. Л. Лурье, А. Брудно, Г. Ш. Рубинштей­ на, Ц. Б. Юдина, Б. Г. Гольдштейна, А. Г. Аганбегяна, Е. П. Нестерова, И. Л. Калихмана и многих других советских уче­

следований академикам Л. В. Канторовичу и В. С. Немчинову в 1965 г. была присуждена Ленинская премия.

Большие исследования в области линейного программиро­ вания были проведены зарубежными, и прежде всего амери­ канскими, учеными. В американской литературе первая рабо­ та, содержащая постановку транспортной задачи, опублико­ вана в 1941 г. Ф. Л. Хичкоком. Основной метод решения за­ дач линейного программирования — симплексный метод — был опубликован Дж. Данцигом в 1949 г. Дальнейшее .разви­ тие методы линейного, а затем и нелинейного программиро­ вания получили в работах Форда, Фулкерсона, Куна (общий метод), Лемки (двойственный симплексный метод), Гасса (па­ раметрическое программирование), Чарнеса (проблема выро­ ждения), Била, Данскииа и Радиера (выпуклое программи­ рование и др.).

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

12

чески нет ни одной работы в области путевого хозяйства (не считая [12]).

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

Л Е К Ц И Я 1

ОСНОВНЫЕ ПОНЯТИЯ ЛИНЕЙНОЙ АЛГЕБРЫ

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

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

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

Решением системы (10) называется упорядоченная сово­ купность п чисел а,, а,, ак. , ап, которые, будучи под­ ставлены в уравнения системы вместо соответствующих неиз­ вестных хп . ., х„. обращают их в тождественные равенства.

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

1.Совместна заданная система или нет?

2.В случае если совместна, как определить, сколько она имеет решений — одно или несколько?

3'. Как найти все эти решения?

Ответ на все эти вопросы дает теория линейных урав­ нений.

Система (10) называется совместной, если она имеет хотя бы одно решение, и несовместной, если она не имеет ни одного решения. Совместная система называется определенной, если она имеет единственное решение, и неопределенной, если она

.имеет больше одного решения.

13

П р и м е р ы .

1.Система 2xt — 3jc4 = 4 }

+Зх, = 5 J

является неопределенной. Действительно, второе уравнение— следствие первого и получено путем почленного умножения обеих частей первого уравнения на 2. Следовательно, система сводится к одному уравнению с двумя неизвестными. Взяв, например, первое уравнение и разрешив его относительно Л'|, получим

Задаваясь любыми значениями х2 и вычислив из послед­ него равенства соответствующее значение хь получим таким

Действительно, записав второе уравнение в виде- 2х,—Зх2=12, замечаем, что при любых значениях %i и х2 ле­ вая часть этого уравнения совпадает с левой частью первого уравнения, а правые части у них различны.

Таким образом, оба уравнения не могут одновременноудовлетворяться ни при каких значениях х\ и х2.

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

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

14

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

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

2.Почленное умножение обеих частей уравнений на один

итот же отличный от нуля множитель.

3.Почленное вычитание из уравнений системы одного ка­ кого-либо уравнения.

Указанные эквивалентные преобразования лежат в основе

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

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

§ 2. /г-мерные векторы

/г-мерные векторы тождественны понятиям двухмерного

пли трехмерного векторов. Двухмерный вектор а (или эквива­ лентное ему понятие — точка плоскости) однозначно опреде­ ляется двумя числами ai и аг, взятыми в определенном поряд­ ке и называемыми координатами этого вектора (точки). Век­

тор.а с координатами см и а2 записывается в виде а=(см, ао).

Аналогично определяется и трехмерный вектор а = (смщо.аз) или, что то же, точка в трехмерном пространстве.

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

/г-мерным вектором а(Или точ)сой /г-мериого простран­ ства) называется совокупность /г чисел а,, а2, .., ал, взятых в определенном порядке. Запись его производится в

15