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

ГЛАВНОЕ УПРАВЛЕНИЕ УЧЕБНЫМИ ЗАВЕДЕНИЯМИ МПС

ВСЕСОЮЗНЫЙ ЗАОЧНЫЙ ИНСТИТУТ ИНЖЕНЕРОВ ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

Печатается согласно Тематическому плану, утвержденному ГУУЗом МПС в качестве учебного пособия

В. И. ТИХОМИРОВ

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

ВОРГАНИЗАЦИИ

ИПЛАНИРОВАНИИ ПУТЕВОГО ХОЗЯЙСТВА

Конспект лекции

для студентов специальности

СТРОИТЕЛЬСТВО ЖЕЛЕЗНЫХ ДОРОГ, ПУТЬ И ПУТЕВОЕ ХОЗЯЙСТВО

М о с к в а — 1974

В В Е Д Е Н И Е

Программа Коммунистической партии Советского Союза, принятая XXII съездом КПСС, ставит величественные задачи создания материально-технической базы коммунистического общества. Это требует повседневного совершенствования ме­ тодов планового руководства народным хозяйством, повыше­ ния эффективности производства, экономии ресурсов, улучше­ ния методов экономических расчетов и строгого их научного обоснования.

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

Математическая модель является абстрактным отображе­ нием реального процесса.

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

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

3

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

Составленная математическая модель становится са­ мостоятельным объектом изучения математическими сред­ ствами.

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

Составление линейной математической модели процесса получило название — линейное программирование.

Линейное программирование находит широкое применение в практике планирования и при решении конкретных эконо­ мических задач.

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

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

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

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

П р и м е р 1.

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

4

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

Рис. 1

В данном примере примем в качестве такого критерия от­ сутствие пересечения линий, соединяющих обе точки; отсюда следует, что решения, в которых линии, соединяющие точки, пересекаются, не являются допустимыми. Из совокупности допустимых решений (рис. 1,6) теперь необходимо выбрать решение, являющееся наилучшим с точки зрения некоторого критерия оптимальности. В данном случае таким критерием оптимальности будет являться протяженность соединения. Оп­

5

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

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

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

П р и м е р 2.

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

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

Нетрудно выявить здесь все три условия общей задачи наилучшего распределения ресурсов: объем ресурсов ограни­ чен; существуют альтернативные возможности их использова­ ния (выпуск двух видов изделий); имеется целевая установ­ ка — максимум рентабельности.

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

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

.6

Соединив точки .Vi и х2, подучим искомую прямую. Анало­ гично строим прямую, соответствующую второму уравнению.

Здесь X] = 1100; л'2 = 300.

В итоге получим график, представленный на рис. 2, где первому уравнению соответствует прямая АВ, второму — СД-

Любой программе выпуска изделий соответствует на гра­ фике определенная точка. Если эта точка лежит на прямой АВ, то она отвечает программе, при которой полностью ис­ пользуются ресурсы древесины. При неполном использовании древесины соответствующая точка будет лежать внутри треу­ гольника ОАВ.

То же относится и к треугольнику ОСД: программам с полным использованием фанеры соответствуют точки на сто­ роне СД, с неполным — точки внутри треугольника ОСД.

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

8