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

Введение к работе

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

АКТУАЛЬНОСТЬ ТЕМЫ. Экономические реформы, осуществляемые в настоящее время в Российской Федерации, выдвинули проблемы развития транспорта страны в ряд важнейших, от успешности решения которых существенно зависит сама возможность проведения этих реформ. Известно, что направления развития грузового транспорта любой страны определяются прежде всего сложившимися соотношениями между объемами перевозимых грузов во внутреннем сообщении и этими объемами в экспортно-импортном и транзитном сообщениях, а также тенденциями тс их изменению. Для Российской Федерации, для которой такое соотношение нельзя считать в настоящее время сложившимся, анализ направлений развития грузового транспорта объективно принадлежит к числу достаточно трудных и в то же время важнейших проблем. Действительно, резкое падение объема промышленного и сельскохозяйственного производства в стране и, как следствие этого, резкое сокращение объемов перевозок внутри Российской Федерации, устойчивая тенденция к увеличению объема импорта промышленной продукции, оборудования и продовольствия из зарубежных стран и объема экспорта природных ресурсов за рубеж, резкое снижение объемов транзитных перевозок через территорию Российской Федерации, вследствие отсутствия эффективной системы экспедирования и охраны грузов, изношенность основных фондов транспорта, неразвитость сети автомобильных дорог и грузового автомобильного транспорта в транспортной инфраструктуре, отсутствие законодательной базы для привлечения иностранных инвестиций в транспортную отрасль, отсутствие современных систем управления транспортом, з частности, воздушным движением, затрудняющее интеграцию транспорта Российской Федерации с транспортом других

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

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

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

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

Программные комплексы для исследования возможностей грузовых транспортных систем на основе методов оптимизации (оптимизационного анализа) являются тем инструментарием, который принципиально может быть эффективно использован для выработки и оценки направлений развития всех элементов грузовой транспортной системы Российской Федерации равно как и системы в целом в современных экономических условиях. Поэтому разработка методологии, математических моделей и методов оптимизационного анализа, так же как и рассмотрение опыта его применения для исследования возможностей грузовых транспортных систем является актуальной, поскольку создает предпосылки как для использования богатейшего арсенала уже разработанных методов оптимизации, весьма успешно зарекомендовавших себя во многих отраслях промышленного производства, сельского хозяйства и непроизводственной сферы, так и для создания новых методов оптимизации, ориентированных на транспортную специфику формулировок решаемых задач. Значительный вклад в указанную разработку был сделан ведущими отечественными учеными в области транспорта: О.И.Авеном, А.А.Вороновь"!, Л.В.Канторовичем, Г.А.Крыжановским, Н.А.Кузнецовым, С.А.Пановьш, Н.С.Соло-менко, В.А.Трапезниковым, С.М.Резером, так же как и воду-

щими отечественными учеными в области оптимизации работы транспорта: Е.Г.Голыптейном, С.С.Лебедевым, И.Х.Сигалом, Д.Б. Юдиным, разработавшими ставшие сегодня классическими принципы, модели и методы оптимизации для транспортных систем. Вместе с тем, изменение экономических условий в стране и транспортной инфраструктуры требует как осмысления уже разработанных методологии, моделей и методов оптимизации применительно к новым условиям работы грузового транспорта, так и создания новых элементов оптимизационного анализа грузового транспорта, учитывающих эти условия.

ЦЕЛЬЮ РАБОТЫ является создание методологии и формализованного аппарата исследования возможностей грузовых транспортных систем на основе использования известных и построения новых математических моделей функционирования грузовых транспортных систем и методов оптимизации как элементов информационно-аналитических систем широкого профиля, ориентированных на работу с научно-исследовательскими и проектными организациями государственных учреждений и коммерческих структур, осуществляющих инвестирование в транспорт, внешнюю и внутреннюю торговлю, промышленное производство и экономику Российской Федерации вцелом.

НАУЧНАЯ НОВИЗНА. В диссертационной работе впервые для транспортных систем:

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

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

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

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

математические модели интермодальных перевозок (трансрегиональных контейнерных перевозок);

математические модели для исследования работы транспортных систем в условиях конкуренции (анализа транспортных тарифов, планирования рекламы транспортных услуг, планирования подготовки и переподготовки кадров на транспортных предприятиях);

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

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

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

основанные на указанных выше условиях конечные методы отыскания седловых точек и точек Нэша в соответственно антагонистических играх и играх 3-х лиц на полиэдральных множествах;

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

проверяемые необходимые и достаточные условия мини-макса двух монотонных функций на полиэдральном множестве и на их основе конечный метод отыскания этого минимакса;

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

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

ПРАКТИЧЕСКОЕ ЗНАЧЕНИЕ диссертационной работы состоит в создании:

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

рабочих методик, рекомендаций и технической документа-

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

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

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

АПРОБАЦИЯ РАБОТЫ. Основные результаты работы обсуждались на: XIV и XV Международных конгрессах по математическому программированию (Амстердам 1991, Анн Арбор 1994); I и II Международном конгрессе по анализу транспортных систем TRISTAN (Монреаль 1991, Капри 1994), ГУ и VI Международных симпозиумах по глобальной логистике и транспорту (Принстон 1990, 1992), Первом Международном конгрессе по новым информационным технологиям и методам исследования операций в транспортных и телекоммуникационных системах (Бостон 1992), V, VI и VIII Международных транспортных конференциях компании Salomon Brothers (Нью-Йорк, 1990, 1991, 1993), Всероссийском семинаре по применению математических методов в планировании и управлении транспортом (Меняно 1989), Всесоюзных школах по оптимизации и ее приложениям (Ашхабад 1984, Душанбе 1986), IX Всесоюзном совещании по проблемам управления (Ереван 1983), семинарах и лекциях в Массачусетском Технологическом Институте, Принстон-ском Университете, Бостонском Университете, Университете им. Дж.Валшнгтона, Вашингтонском Университете в г. Сент-Луис

(США), Университете Эколе Централ г.Париж (Франция), Университете г.Удина (Италия), Центральном экономико-математическом институте и Институте проблем управления Российской Академии наук.

ПУБЛИКАЦИИ. По теме диссертации автором опубликовано 28 научных работ, в том числе три монографии, четыре брошюры и два обзора. Общий объем опубликованных материалов, включенных в диссертационную работу и написанных лично автором, составляет более 80 авторских листов. Всего автором опубликованы 82 научные работы.

1. Методологические принципы реализации и основные элементы систем оптимизационного анализа для ис-' следования возможностей грузового транспорта.

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

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

Методологические принципы формирования такой стратегии включают:

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

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

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

2. Математические модели функционирования грузовых транспортных систем [1.2].

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

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

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

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

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

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

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

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

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

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

Для решения задач оптимизационного анализа грузопых

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

Среди пакетов программных комплексов общего вида наиболее развитыми являются: ПЛАНЕР, предназначенный для решения задач производственно-транспортного типа большого размера и ориентированный прежде всего на задачи, в которых присутствуют блоки транспортного или распределительного типа, включающий модули для решения задач математического программирования блочной структуры, целочисленного программирования, транспортных (в сетевой и матричной постановках), об отыскании кратчайшего пути, стохастических транспортных, многопродуктовой транспортной, размещения (одно-этапной и двухэтапной), о рюкзаке и др.; ПАОЭМ, предназначенный для решения задач и исследования моделей линейного и нелинейного программирования, потокового типа (и включающий модули линейного и квадратичного программирования для решения задачи транспортного типа в сетевой и матричной постановке) и для решения задач безусловной и условной оптимизации; ЛП АСУ, предназначенный для решения задач линейного, сепарабельного и параметрического программирования, а также для решения задач целочисленного программирования и.задач со смешанными переменными, и его усиленная версия СПО МПР-2; ПРОЛОГ, предназначенный для решения задач оптимизации с линейными ограничениями и включающий модули для решения задач минимизации выпуклых дифференцируемых функций общего вида, выпуклого квадратичного программирования, дробно-квадратичного и дробно-линейного программиро-

вания. Существуют модули для решения оптимизационных задач различных типов, разработанные в рамках пакетов ДИСО, -,, ОМЕГА, СЛИП, ОПТИМУМ, ДИСНЕП, РАФОС, ГИПЕРКУБ, ОПТИМА-2, КВНК, МКО ДИСО, ГЛОБ, СИМОП, ВЕКТОР-2, ЗОНД и др., которые как и модули из перечисленных основных пакетов могут быть переадаптированы для использования на современных ЭВМ, включая персональные.

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

РАЗДЕЛ И. НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ИСПОЛЬЗУЕМЫЕ ПРИ ФОРМУЛИРОВКЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ИССЛЕДОВАНИЯ ВОЗМОЖНОСТЕЙ ГРУЗОВЫХ ТРАНСПОРТНЫХ СИСТЕМ.

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

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

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

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

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

1. Выбор структуры контейнерной линии морского транспорта в условиях фидерного обслуживания портов.

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ. Имеются два региона, между которыми осуществляются контейнерные перевозки в рамках линейного судоходства по фидерному принципу, предусматривающему движение крупных (магистральных) судов между регионами и менее крупных (фидерных) судов внутри каждого региона; при этом магистральные суда посещают базовые порты в каждом из регионов, а фидерные суда осуществляют перевозки контейнеров между базовыми и небазовыми, а также между небазовыми портами в каждом из регионов.

Известны: числа судов каждого типа, которые могут работать только как магистральные и только как фидерные; рассто-

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

В случае, когда построение схем движения "регион 1 - регион 2" и "регион 2 - регион 1" осуществляется раздельно, требуется выбрать в каждом из регионов базовые порты и схемы прикрепления фидерного сервиса для базовых и небазовых портов региона, в предположении, что число базовых портов в каждом из регионов не превосходит двух.

ПЕРЕМЕННЫЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ. В модели используются булевы переменные: Х,-,,-₃, і і Є 1,п, г₂ Є l,m, принимающие значение 1, если порт ij из п портов первого региона и порт г₂ из m портов второго региона соединяются магистральным отрезком; «,-,;,+<,,, к_х Є l,n — t'i, t\ Є l,n — 1, принимающие значение 1, если порты г* і и г_г + к первого региона являются базовыми; го,-,, принимающие значения 1, если t"i — единственный базовый порт, выбираемый в первом регионе; «,,_t-,₊fc,j, принимающие значение 1, если в первом регионе к базовым портам і_г и г'_г + кх прикрепление небазовых портов осуществляется

ті—2

по схеме /, / Є 1,2 ; аналогичный смысл имеют переменные ^vi*ii+k₂, fc», l,"i — t₂, i₂ Є l,m- 1 и i4i,+Jfc₃т-².

ОГРАНИЧЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ отражают следующие эксплуатационные условия функционирования контейнерной линии: оба региона связаны по крайней мере одним магистральным отрезком; в каждом из регионов выбирается не менее одного и не более двух базовых портов; каждый магистральный отрезок и каждый фидерный отрезок в каждом из регионов имеют общий порт; прикрепление небазовых портов к базовым в каждом из регионов при наличии двух базовых портов

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

ЦЕЛЕВАЯ ФУНКЦИЯ ЗАДАЧИ. В качестве целевой функции задачи рассматривается чистая валютная выручка, являющаяся функцией булевых переменных задачи.

ВЕКТОРНО-МАТРИЧНАЯ ФОРМА ЗАДАЧИ. Введением векторных переменных X Є i?4."\ и Є R%, w & R+, и 6 R+ , v Є R+, к Є Л, v Є. R+ , где ц = 0,5n(n — 1) и ц = 0,5m(m — 1), векторов є_х Є R+^m, _u Є i?+, є_ш Є R+, E_v Є R+, є_к Є R+, все компоненты которых равны единице, а также векторов а,-, Є

ДГ, б*, є /. с;, є /Q, d_fl е R% d'₀ є R»²ⁿ~\ /,-, є ДГ> _9ії є

itj., Лі, Є -R+, р_ы Є іц., Pu,< Є R\ , компоненты которых состоят из нулей и единиц, чередуемых в определенных закономерностях, и в Є l,fi, супервектора t — (x,u,w,v,к, и , и) и матриц A_X,B_V, CutDufDu^F^jGxjHkiPviPv¹, строками которых являются соответственно Векторы аі^Ьі^С^^о^Оі/іггЯіц^іггРи/іРи¹

и векторов «;х Є щ ^{м v}, w₂ Є R , компонентами которых

являются нули и единицы, и, наконец, матриц

є_х ol ol ol ol ol ol.

ol ol.

Гі =

D_u Ot Ot Oi -D

oi ol H_k ol 01}

ol ol ot

% =

Ot Ol

о:

в_и o^b_u a

o²_v, ol. o⁴_v.

-o:

-Pi,

o^e_v,

ot oi ob

ol ol ol ol

ol ol

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

(с, t) —> max ,

<Є{(: T_li=w_uT_it^w₂]

где с = (c_x,c_u,c_w,c_v,Ck,c_ui,c_vi), элементы матриц Ті,Т₂ вида Од — нулевые матрицы соответствующих размеров и векторные компоненты супервектора с вычисляются с использованием специальных эксплуатационных методик на основе указанных выше исходных данных о работе линии.

2. Планирование трансрегиональных контейнерных перевозок грузов иностранных фрахтователей на морском транспорте.

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ. Для контейнерной линии, связывающей порты двух регионов, известны: число судов каждого типа, работающих на линии; нормативно-справочная информация по каждому судну; последовательность и периодичность посещения судами портов линии; схемы движения судов между портами; схемы прикрепления пунктов отправления (назначения) перевозимых в контейнерах грузов к каждому из портов; типы перевозимых контейнеров; предполагаемые объемы перевозок грузов в контейнерах между любой парой пунктов и портов (заявки от агентов о потребности контейнеров под груз); дислокация порожнего и груженого контейнерного парка по всем пунктам и портам регионов; ставки фрахта на перевозку грузов между любыми двумя пунктами (портами); нормативные расходы по обслуживанию каждого судна в каждом порту линии; расходы на судозаход по каждому порту; время движения контейнеров (оборот контейнеров) на всех направлениях между каждой парой пунктов и портов и стоимость контейнеро-суток; расходы по хранению порожних контейнеров в портах, пунктах и депо; суточные ставки аренды контейнеров; расходы по доставке контейнеров на линию (из пункта отправления в порт отправления и из порта выгрузки в пункт назначения); расходы по переброске порожних контейнеров внутри региона неморским путем; формулы

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

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

ПЕРЕМЕННЫЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ. В модели ИСПОЛЬЗУЮТСЯ Следующие Переменные: XilJjkh tiUjakU

iTihuaki — соответственно объемы трансрегиональных перевозок груженых контейнеров, порожних контейнеров и объемы внутрирегиональных перевозок собственных порожних контейнеров, осуществляемых для контейнеров fc-го типа, к 1,к, в /-ом отрезке периода планирования, / Є 1, п, судами обслуживающими порты по s-му варианту сервиса, s 1, S; r^i — число собственных контейнеров fc-го типа, поступивших в ремонт в г'-ом пункте в 1-й интервал периода планирования; xnjj_skh^xiiJjski — объемы трансрегиональных груженых контейнеров соответственно по схемам аренды в одном направлении и на круговой рейс; tiijki — неудовлетворенная часть заявки на контейнеры к-го типа, подлежащие перевозке по (г, і)-му направлению, оставшаяся на конец 1-го отрезка планирования, Л,^ — число собственных контейнеров к-то типа, поступивших в г'-м пункте на хранение в течение /-го отрезка планирования; P,_ajtb V^u — число контейнеров к-го типа, соответственно погруженных в г'-м порту на суда s-ro сервиса в течение 1-го отрезка планирования и выгруженных в а'-м порту с этих судов; Sj_ski — число неиспользованных мест на всех судах s-ro сервиса для 1-го порта по контейнерам к-го типа в течение 7-го отрезка планирования; Mj_Ski — число контейнеров fc-го типа на всех судах s-ro сервиса, проходящих через 1-й порт транзитом в течение 1-го отрезка планирования; Njskl — недостающее число свободных мест для контейнеров к-

го типа на всех судах а-го сервиса в 1-м порту в течение 1-го отрезка планирования; аналогичный смысл имеют переменные

PjskU ^vJski) ^sJskU N_Jski, Mj_akt.

ОГРАНИЧЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ включают линейные уравнения и неравенства балансового типа: определяющие долю числа контейнеров, поступающих на ремонт в пункте каждого региона за текущий отрезок периода планирования; связывающие числа имеющихся в каждом пункте и вывозимых из него контейнеров (кроме арендованных); исключающие ввоз порожних контейнеров каждого типа в пункты каждого из регионов, из которых нет вывоза груженых контейнеров; обеспечивающие выполнение заявок на вывоз груженых контейнеров по каждое из направлений; обеспечивающие полное удовлетворение заявок на контейнеры под груз на направлениях, в которых возможна аренда контейнеров только на круговой рейс; обеспечивающие возврат в исходный пункт при I = 2 всех контейнеров, взятых в аренду на круговой рейс при / = 1 на каждом из указанных направлений; обеспечивающих равенство суммарных контейнеровместимостей всех судов, обслуживающих два последовательно расположенных порта внутри каждого региона; связывающие числа контейнеров, перевозимых судами, занятыми на разных типах сервиса; учитывающие начальные условия задачи.

ЦЕЛЕВЫЕ ФУНКЦИИ. В качестве целевых функций задачи рассматривались следующие эксплуатационные пог'азате-ли: чистая валютная выручка; неудовлетворенная часть заявок на вывоз груженых контейнеров; превышение провозной способности линия (суммарное число недостающих свободных мест яа всех судах, проходящих через все порты). Все эти функции являются линейными функциями рассмотренных выше переменных.

ВЕКТОРНО-МАТРИЧНАЯ ФОРМА ЗАДАЧИ. Можно показать, что переменные модели могут быть сгруппированы в векторы хі,..., х_п; ух,..., у„, так, что система ограничений задачи

записывается в виде

AiXi = В_х

CjXj + ZJij/x =^i

RiVx = ^1

L_lx₁ + M₂x₂ = J₂

A₂x₂ . = B₂

C₂x₂ + D₂y₂ = 0₂

Л22/2 . =N₂

L₂x₂ + ...

M_nx_n = J_n

A_nx_n - B_n

C_nx_n + D_ny_n =П„

C_nx_n+R_ny_n = N_n

где Ai,Ci,Li,Di,Ri и Bi,Q{,Ni,Ji — матрицы и векторы соответствующих размеров, и исходная задача планирования оказывается задачей линейного программирования с квазиблочной структурой системы ограничений, причем число блоков п равно числу отрезков, на которые разбивается период планирования (как это принято в практике решения задач линейного программирования большого размера, в которых переменные по физическому смыслу должны быть большими целыми числами, рассмотренная задача сформулирована как обычная задача линейного программирования, решение которой подлежит затем округлению).

3. Расчет возможных тарифов на перевозку грузов в условиях неопределенности спроса и предложения.

СОДЕРЖАТЕЛЬНАЯ. ПОСТАНОВКА ЗАДАЧИ. В условиях рынка некий грузовладелец предлагает набор товаров (грузов) определенной номенклатуры, интересующей его торгового партнера, осуществляющего покупку и перевозку товаров, в количествах, меняющихся (по каждому виду груза) в некоторых диапазонах, связанных с продажными ценами и тарифами на их перевозку. Покупатель груза и транспортная компания, выступающие согласованно как единый участник торговой сделки, стре-

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

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

ПЕРЕМЕННЫЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ. Переменными в модели являются объемы предлагаемых к продаже

ГруЗОВ Уі, І Є 1,71, Тарифы На ПереВОЗКу ЭТИХ ГруЗОВ X;, і Є 1,71,

и продажные цены на товары (грузы) щ, і Є 1, ті.

ОГРАНИЧЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ. В простейших случаях ограничениями модели являются линейные неравенства вида х,- ^ х,- ^ х;, у. ^ t/i < Уі, u_i ^ Ui < її,-, отражающие возможности участников торговой сделки и конъюнктуру рынка товаров и услуг. В более общих случаях могут существовать дополнительные балансовые соотношения, связывающие переменные внутри каждой из трех групп; такие соотношения описываются линейными неравенствами соответствующих переменных.

ЦЕЛЕВАЯ ФУНКЦИЯ ЗАДАЧИ. Поведение участников торговой сделки в рассматриваемом случае соответствует поведению участников антагонистической игры, в которой один из игроков (грузовладелец) стремится получить максимальный доход от продажи товара, а другой игрок стремится приобрести предлагаемые товары в нужной номенклатуре и с наименьшими затратами. В этом случае можно говорить о платежной функции игры, описывающей доход одного и затраты второго игрока. Эта функция представляет собой нелинейную функцию переменных задачи.

ВЕКТОРНО-МАТРИЧНАЯ ФОРМА ЗАДАЧИ. Вводя векторные переменные х = (хі,...,г„), у — (Уі,...,у_п)> " =

(щ,... ,u_n), так что х Є П_х, у Є П_у, и Є П_и где П*, П^, П_и — параллелепипеды, описываемые приведенными выше системами двусторонних линейных неравенств на компоненты соответствующих векторов, функцию дохода грузовладельца в рассматриваемой ситуации математически можно описать как гр(у,х) — ^maxuen„ (У> ") ^— {у,х)> так чтр при конкретном выборе значений объемов продаваемых грузов (вектор у ) и тарифов на их перевозку (вектор х ) соответствующий этим векторам доход грузовладельца составит (у ,и ) — {у ,х ) — max_un„ (у ,и) — (у ,х ). При этом значение функции ф(у ,х ) определяет расходы (затраты) покупателя и перевозчика, связанные с приобретением груза.

Исходная задача расчета тарифов формулируется в виде следующей непрерывной минимаксной задачи

max -f max (у,и) — (у,х)\ — min їЄП, Чеп« "" ' ^{х /J} хєп_х.

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

4. Планирование рекламной кампании транспортных услуг.

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ. Имеется п видов рекламы (телевизионная, радио, печатная, кино и т.д.), известны предельные затраты (в денежном выражении) д,-, і Є 1, п, на каждый из видов рекламы и суммарный лимит денежных средств q на планируемую рекламную кампанию, в рамках административной единицы (для которой планируется рекламная кампания), существуют fc центров реализации рекламируемой услуги, известны результаты анкетирования, по которым могут быть восстановлены зависимости вида pj = ipj(xj), где Pj — вероятность возникновения у жителя административной единицы намерения воспользоваться рекламируемой услугой под воздействием jf-ro вида рекламы, j Є 1,п, и Xj — объем рекламного сообщения, вычислены вероятности приобретения рекла-

,0

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

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

ПЕРЕМЕННЫМИ МАТЕМАТИЧЕСКОЙ МОДЕЛИ являются объемы рекламных сообщений Xj, j Є 1, n, по каждому из п видов рекламы.

ОГРАНИЧЕНИЯМИ МАТЕМАТИЧЕСКОЙ МОДЕЛИ яв-ляются линейные ограничения балансового типа, образующие си-

стему линейных неравенств вида 2y=i ^сз^хз ^ 9> 0 ^ ^cj^xj ^ Qj> j Є 1, п, где Cj — затраты на единицу рекламного сообщения.

ЦЕЛЕВОЙ ФУНКЦИЕЙ ЗАДАЧИ является среднее значение (математическое ожидание) числа жителей административной единицы, которые приобретут услугу в центрах реализации услуг, расположенных в этой административной единице, описываемое функцией следующего вида

1 ""' 1_ Д(І-л^) 6_fc7fcV -t-Cl

где , — вероятность события, состоящего в выборе жителем административной единицы 2-го варианта использования рекламной информации, в^ — вероятность события, состоящего в выборе жителем, намеревающемся приобрести рекламируемую услу-' гу, к-то центра реализации услуг, 7fc — условная вероятность события, состоящего в приобретении рекламируемой услуги в fc-OM центре реализации услуг, т) — число жителей административной единицы, реально способных получить информацию о рекламируемой услуге из рекламных сообщений и обладающих покупательной способностью приобретения этой услуги, Ні — множество видов рекламной информации, образующих і-й вариант использования рекламной информации, /Зу, aj — параметры в выражении 1 — «ji^, описывающем вероятность события, противоположного событию, состоящему в том, что намерение приобрести рекламируемую услуґу у жителя, получившего информацию об этой услуге при г-ом варианте использования рекламных сообщений, возникло за счет j-ro вида рекламы.

ВВЕДЕНИЕ ВСПОМОГАТЕЛЬНЫХ ПЕРЕМЕННЫХ. При достаточно естественных предположениях о виде функций 1 —

д. л,

(XjXj' Введением ВСПОМОГатеЛЬНЫХ ПереМеННЫХ Zj = 1 — OjX-',

Ti_iiHiZj = щ, і Є 1,2"-1, l.-ti,- = v_it ЕііГЧ.у." = to,

!jfc=i &k~tk — P> 1 — pw = s, можно показать, что исходная задача нелинейного программирования с линейными ограничениями может быть переформулирована в виде некоторой задачи геометрического программирования.

5. Планирование профессиональной подготовки кадров для транспортных предприятий.

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ. На транспортном предприятии в течение некоторого планового периода Т требуется выполнить п видов работ объема #,-, і Є l,n. Предполагается, что к началу периода планирования на предприятии будет pj специалистов j-ой квалификации, j Є l,m, и р₀ рабочих, не имеющих квалификации. Известны объемы а,-,-работ г-го вида, выполняемых специалистами jf-й квалификации в единицу времени, время Sjk, необходимое для переподготовки специалиста j'-й квалификации в специалиста к-ч квалификации (индивидуально — 5*^д и в группе — -ву*!), а также время tj, необходимое для подготовки специалиста j-й квалификации из неквалифицированного работника.

Подготовка специалистов на предприятии может осуществляться группами и индивидуально; размеры групп определяются числами hj и h_}- — минимального и максимального числа рабочих, которые могут входить в одну группу. Известны стоимости rj_k индивидуальной переподготовки специалистов j-й квалификации в специалистов к-й. квалификации, а также стоимость qj подготовки группы специалистов j'-й квалификации и стоимость Cj индивидуальной подготовки специалистов j-й квалификации. Предполагается, что новые специалисты и неквалифицированные рабочие в течение периода Т не будут увольняться, а также, что в период подготовки и переподготовки участвующие в этих процессах неквалифицированные рабочие и специалисты не выполняют никаких работ (из имеющихся п видов). Предполагается, что стоимость групповой переподготовки специалистов j-й квалификации в специалистов А;-й квалификация равна стоимости подготовки специалистов fc-й квалификации из неквалифицированных рабочих, причем групповая переподготовка, равно как

и групповая подготовка специалистов j-й квалификацфии, осуществляется в одних и тех же группах, а любая переподготовка и подготовка специалистов происходит только с начала периода планирования.

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

ПЕРЕМЕННЫЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ. В модели используются следующие переменные: Xji — число специалистов j-й квалификации, используемых для выполнения г-го вида работы; yji — число специалистов j-й квалификации, которые будут подготовлены из неквалифицированных рабочих и использованы для выполнения г-го вида работы; z^ — число специалистов к-й квалификации, которые будут подготовлены из специалистов j-й квалификации, а затем использованы для выполнения і-го вида работ; т,-^ — время в течение которого специалисты к-й квалификации, подготовленные из специалистов j-й квалификации будут использованы для выполнения г'-го вида работ; 9j — число групп подготовки специалистов j-й квалификации; Vji > у]ї^й — соответственно числа специалистов j-й квалификации, которые будут подготовлены из неквалифицированных рабочих групповым методом и индивидуально и использованы для

г гр ИНД

выполнения г-го вида работы; z^, Zj_ki — соответственно числа специалистов к-й квалификации, которые будут подготовлены из специалистов j-й квалификации групповым методом и индивидуально и затем использованы для выполнения г'-го вида работ*

ОГРАНИЧЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ отражают: условия выполнения всех запланированных работ в плановом периоде; соотношения между числами подготавливаемых, переподготавливаемых и имеющихся специалистов; распределение времени между подготовкой, переподготовкой и использованием специалистов в периоде планирования; ограничения по числу спе-

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

ЦЕЛЕВАЯ ФУНКЦИЯ ЗАДАЧИ. В качестве целевой функции в задаче рассматривается стоимость подготовки и переподготовки специалистов, являющаяся линейной функцией используемых непрерывных и целочисленных переменных.

ВЕКТОРНО-МАТРИЧНАЯ ФОРМА ЗАДАЧИ,

пусть t/^p = {«&.}, „*-» = {«j»-}, _у = ад-»},,— =

ДО. у^р = Ц?М = {Oj}, u = (u'-.u*), *^rp = {*&},

х = {аг,-,-}, у = (2/^гр,у^инд), z = (2^тр,г^япя), v = (х,у,г,в), и^ =_ ^z*jki^aki V, ^"кГ^акі ^Л<Т = «S,"i П = conv^¹ ,...,^), Tj-jfci -= Yll=i A'wffci, где E'=i^Aff = 1, A^0- > 0, о- Є l,g, w^ = {wj_fc,}-Рассматриваемую задачу можно записать в виде

Aiu + A_zv > Ь,

(c_uu) + {c₂,v)—>mia,

где компоненты матриц Ах,А₂ и векторов с_г,с₂ легко выписываются по коэффициентам и правым частям модели, имеющей форму системы линейных неравенств со смешанными перемен-ными. В частности, например, матрица А±, имеет вид

_т [цг^т-є^т ОТ ~є^т е^т Е^Ті Е^Т2 0^Т2 0^Ті \ .¹ \W^T-eZ Ог ОІ ОІ 0^Т_т,_п 0%,_п Е%,_п Е%*_п)

где W — (пхт па) — матрица, у которой ненулевые элементы в 1-й строке равны ш*_кі і Є l,n,j,k Є 1, m, а Є 1,?и стоят в столбцах с номерами (сг — l)m q + 1, m дг; є_т—тх (mng) — матрица, у которой все ненулевые элементы равны ог^і , причем в j'-й строке этой матрицы ненулевые, элементы стоят в столбцах с номерг -ми (J - l)m + (о- - l)m² + (t - l)m²q - 1, (і - l)m -f (cr - l)m²+ (і — l)m q + m, l,ro, » el,n;0„ - (і/ x m tig) — матрица, все элементы которой нулевые, E_mi_n — (тп п х тп nq) -

матрица, у которой все ненулевые элементы равны единице и стоят в столбцах с номерами (j — l)m + h + (і — l)m q + (cr~ l)m, о^- ЄІГ9> fc Є l,m, j Є l,m, і Є l,n.

РАЗДЕЛ III. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ИССЛЕДОВАНИЯ ВОЗМОЖНОСТЕЙ ГРУЗОВЫХ ТРАНСПОРТНЫХ СИСТЕМ НА ПОЛИЭДРАЛЬНЫХ МНОЖЕСТВАХ

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

1. Задачи нелинейного программирования с монотонными функциями общего вида.

1.1. Определения и математические формулировки задач.

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

Пусть /: М —+ R , /<: М —* R і 1,п — монотонные функции на полиэдральном множестве М. Задача 1. Найти х* Є Arg тіп^л/ /(і) Задача 2. Найти х** Є Arg тіп_вЄм max_iey^/,(:r).

1.2. Основные теоремы.

Пусть 21(Я^П) — семейство множеств, включающее Я^п и все его выпуклые многогранные подмножества.

Теорема 1.1 (необходимое и достаточное условие монотонности непрерывной функции на множестве М Є %(Rⁿ).

Для того -чтобы функция f(x), отличная от постоянной и

непрерывная на множестве М Є й(ії^п), была монотонной на М необходимо и достаточно, чтобы для любого с Є R , для которого множество S_c = {х Є М: f(x) = с} непусто, выполнялось равенство S_c = Г_с П М, где Г_с — некоторая гиперплоскость в Rⁿ.

Пусть М С Rⁿ — выпуклое многогранное множество, 0⁺М — рецессивный конус множества М и tp_k: М —* R , ^_k(x)=max_ieT^fi(x).

ТЕОРЕМА 1.2. Если fi(x) — монотонные на М функции, і Є 1, к, достигающие минимумов на множествах х + /д/ Vx Є М и V/д/ Є О М, то ^x) достигает минимг/ма на любом выпуклом многогранном подмножестве множества М.

СЛЕДСТВИЕ. Если fi{x) — монотонные на Rⁿ функции г Є 1,к, достигающие минимумов наМ, то<р_к(х) достигает минимума на любом выпуклом многогранном подмножестве множества М.

Пусть S — непустое выпуклое множество, /»(х), «6l,fc, — монотонные на S функции, Di(x*) = {х Є S: fi{x) = Ji{x*)}, Df(x*) = {x Є 5: /,(*) ^ ji{x*)}, R_k(x*) = {і Є 1^: /<(**) = M**)h GfeOO = nti{x S: fi(x) < _k{x*)} Vx* Є S.

Теорема 1.3. (необходимые и достаточные условия мини-макса конечного числа монотонных функций на выпуклом множестве).

Для того, чтобы _k(^x*) — ^m^ⁿs^sfk(^x)> необходимо и достаточно, чтобы для некоторого t Є R_k[x ) выполнялось равенство mhjgg^j..) f_t(x) = f_t(x*).

Пусть Ті и Т₂ — множества точек минимума функций /і (х) и /г(х) на соответственно (которые могут быть пустыми).

ТЕОРЕМА 1.4. Пусть в точке х* Є 5\(Tj UT₂) справедливо /i(x*) = /г(^г*)- Для того, чтобы фг(х*) = тіп_гЄЗ угС¹) необходимо и достаточно, чтобмтіп_іЄО+, .«^(i) = /i(x*).

СЛЕДСТВИЕ. Если М — выпуклое многогранное множество, имеющее крайние точки, и минимум функции <Р2(х) на М достигается, то этот минимум достигается в точке, лежащей на ребре множества М.

Пусть /,(х), t Є l, к, достигают минимумов на М и (pk(x) также достигает минимума на М. Пусть далее а — ^minielTfc^minxM /»(*), ^b < ^sup_x6m Л/(0) = і^х Є М: /,(х) < 0, і Є hk}.

ТЕОРЕМА 1.5. Функция ф_к: [а,Ь] —* R :

4,_к(Є\ = І^в> ^{если м}()ї⁰>

V^у*:v. ; ^ _q ^_ 2|5| _е противном случае,

унимбдалъна, причем тіп.д^[_а<ь] ФкіР) — пг^шгєл/ fk{x)-

1.3. Вычислительная схема конечного метода минимизации Дх) на М.

Пусть М С -R+. — выпуклое многогранное множество, имеющее крайние точки, Дх) — монотонная на М функция, Г — множество точек минимума Дх) на М (которое может быть пустым) и пусть Vi' Є М ^с{^х*) Є Rⁿ- D(x*) = {х Є М: /(х) = /(ж*)} = МП{іЄД^н: (с(х*), х - х*) = 0}, причем ⁺(х*) = {х Є М: Дх) < Дх*)} = М П {х Є Я^п: (с(х*), х - х*) < 0}.

В разработанном конечном методе минимизации Дх) на М вначале из решения некоторой задачи линейного программирования определяется какая-либо крайняя точка М. На шаге метода с номером к (к ^ 1) либо осуществляется итерация модифицированного симплекс-метода в задаче минимизации функции (с(х ~ ),х) на D⁺(x ), в результате которой находится точка х , где х — крайняя- точка М, полученная на предыдущем шаге, — текущее базисное решение, либо осуществляется направленный перебор крайних точек D⁺(x ~ ), лежащих в D(x ^-1) с последующим анализом ребер D (х ~ ), выходящих из этих точек. В последнем случае в ходе указанного перебора либо устанавливается, что рассматриваемая задача минимизации Дх) на М неразрешима (т.е. Г = 0), либо осуществляется итерация модифицированного симплекс-метода в той "е самой задаче минимизации (с(х ~ ), х) на D (х ~ ), в которой текущее базисное решение соответствует какой-либо крайней точке D{x ~ ), имеющей конечное ребро D⁺(x ), не лежащее в D[x ). В результате этой итерации находится точка х , при этом ана-

лиз ребер осуществляется путем построения последовательности симплекс-таблиц, каждая из которых соответствует крайней точке D(x ~ ), и стандартного преобразования этих таблиц, связанного с переходом от одной крайней точки множества D(x ) к другой.

1.4. Вычислительная схема конечного метода минимизации <>₂(х) ка М.

Пусть М С R+ — выпуклое многогранное множество, имеющее крайние точки и А(х) и /г(я) — монотонные на М функции. Пусть далее /і (і) достигает минимума на множествах х +- 1м УхЄМиУ/д/ЄО М, /г(^) достигает минимума на М и на 7\, а <Р2І^Х) достигает минимума на М.

Пусть М1(Н), М2(Н) — конечные методы минимизации со-' ответственно функций f\(x) и fa(x) на Н, где Н С М — выпуклое многогранное подмножество множества М, на котором указанные минимумы достигаются.

В нетривиальном случае (когда минимум функции ^(х) ^на М не достигается на Т\ UT2) предложенный конечный метод минимизации (2(¹) ^на М представляет собой направленный перебор ребер М. На шаге этого метода с номером к (к > 1) определяется ограниченное ребро * выпуклого многогранного множества Н для которого функция /i(x) —/2(1) — либо принимает нулевое значение в одном из его концов, либо принимает значения разных знаков на концах этого ребра, и точка и(к) Argmin_xg^_t ф2(х). Каждый шаг метода может включать конечное число итераций М1(Н), М2(Н), причем Н либо совпадает с М, либо (при к > 2) является выпуклым многогранным подмножеством множества М вида >₂ (и(к — 1)), а в точках u(fc), к > 1 может достигаться минимум функции ф2І^х) ^на М.

Чередование итераций М1(Н) и М2(Н) начинается с одной из крайних точек Т₂ (для к ^ 1) и с одной из крайних точек множества Argmin_xeD+,_u,_fc_₁N4/i(a;) (для к ^ 2) и производится при изменении знака функции /i(x) — /2(я) в последовательно определяемых в результате этих итераций крайних точках Н.

Точка и(к) на ребре д, либо совпадает с одной из крайних

точек этого ребра, либо находится из решения уравнения /j [Axj.+ (1 - A)y_fc] = /₂[Ax_fc + (1- X)y_k], А Є [0,1], где [х_к,у_к] = _к, при этом проверка условия и(к) Є Argmin_xg_M <р₂{х) производится в соответствии с критерием, сформулированном в теореме 1.4, в результате конечного числа итераций M1(D₂ (и(к))).

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

1.5. Вычислительная схема итеративного метода минимизации ц>ь(^х) ^на М.

Положим о — (fk(x ), где х Є М\ Argmin_zM <р_к(х) и заметим, что это включение может быть установлено с помощью теоремы 1.3. Из теоремы 1.1 следует, что М(в) — полиэдральное множество, проверка непустоты которого при 6 = 9*, эквивалентная вычислению может осуществляться решением любой задачи линейного программирования, в которой какая-либо линейная функция минимизируется на М(0*).

Из теоремы 1.5 следует, что решение задачи 2 сводится к отысканию минимума унимодальной функции на отрезке [а,Ь], которое целесообразно осуществлять методом Фибоначчи, обеспечивающим минимальное число шагов для получения заданной точности вычисления минимума рассматриваемой унимодальной функции и, следовательно, минимакса в исходной задаче 2.

2. Задача нелинейного программирования с монотонными функциями частного вида.

2.1. Математическая формулировка задачи. Пусть fi'.M—*R і Є l,fc — дробно-линейные функции вида /<(х) = 1 и {d_itx) >0 Vx Є М, где _Ci,di ЄЛ" і є hk, П С Rⁿ — выпуклое многогранное множество, h,r,p,s Є R^m, D-(m x n) — матрица с действительными элементами, Р = {(t,x) > 0: tB ^ —g — xD, Ax > b), где A-(l x m) — матрица с действительны-

ми элементами и М = {х Є Я+: Ах ^ Ь}, а также (5,1) > О, (h,x) >OVxEM,qERⁿ. Задача 3. Найти

а: Є Arg гшп тахтах < -; г, г;—г г-

хьм уєп К*,^) (Л, a;) J

2.2. Основная теорема. ТЕОРЕМА 2.1. Функция

(*,,,)-max |^, ^ 1

«лсеет седловую точку на М х Q. Следствие.

Г (г,g) {p,x) + {x,Dy) + (q,y)')
U;*V (*,*) J.

1(₅, а:)' (Л,*) /'

max mm max yen хЄМ

= mm max

2.3. Вычислительная схема метода отыскания максимина функции (х, у) ко М х Q.

В силу следствия из теоремы 2.1

mm max

(t,x)ZP

t(r,x) (-d,t) + (p,x)~)

достигается на выпуклом многогранном множестве Р, так же как и минимумы дробно-линейных функций, стоящих под знаком максимума. Далее, функция |р|у достигает минимума на любом выпуклом многогранном подмножестве множества Р, а из теоремы двойственности линейного программирования следует, что функция /hgl достигает минимума на множестве точек

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

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

3.1. Математическая формулировка задачи.

Пусть f:MxCl—*R — функция двух векторных аргументов, монотонная на М Уу Є Сі и монотонная на Q Vx Є М, где М С Rⁿ и П С R — выпуклые многогранные множества. Пусть далее О М и О П — рецессивные конусы соответственно множеств М и Cl, Sf(_x)(M хП) — множество седловых точек функции /(х, 7/) на М х Cl.

Задача 4. Найти (х*, у*) Є 5д_І)У)(Л/ х fi)

3.2. Основные теоремы.

ТЕОРЕМА 3.1. Если }[х) — монотонная функция на выпуклом многогранном множестве М С R , достигающая минимумов на множествах х + Іщ Ух Є М и У1_М Є О М и М = х₀ 4- ж, где Я" — подпространство некоторой размерности, то f{x) = /(х₀) Ух Є М.

ТЕОРЕМА 3.2. Функция /(х), монотонная на выпуклом многогранном множестве М, достигает минимума на множествах х + 1_М Ух U и У1_М Є 0⁺М тогда и только тогда, когда f(x) достигает минимума на любом выпуклом многогранном подмножестве множества М.

ТЕОРЕМА 3.3. Если /(х) — монотонная на Rⁿ функция достигает минимума ма выпуклом многогранном множестве М С Rⁿ, то f{x) достигает минимума на любом выпуклом многогранном подмножестве множества М.

ТЕОРЕМА 3.4. (достаточные условия существования седловых точек у монотонной по каждому векторному аргументу на М и С1 соответственно функции f{x,y) на М х СЇ). Если У у Є СІ функция f{x,y) достигает минимума на множествах х + 1_Л/ Vx 6 М, Уїм Є О М и Ух Є М достигает максимума на множествах у + f_n Уу Є Cl, VJn Є О СІ, то /(х, у) имеет на М хСі седловую точку.

СЛЕДСТВИЕ 3.1. Если fix,у) монотонна по каждому векторному аргументу на Rⁿ и R соответственно, Vy Є СІ до-

стигает минимума на М и Vx Є М достигает максимума на 17, то /(х, у) имеет на М X П седловую точку.

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

4.1. Математические формулировки задач.

Пусть М = {х Є R+: Ах > Ь}_} Q = {у i?+: By > d) выпуклые многогранные множества в R+ и R+, Ь Є R , d Є Л , Л, В — матрицы с действительными элементами размера (I х т) и (к х п). Пусть далее р Є R^m, g Є Л, D — (тп х п) — матрица с действительными элементами, Q = {(-2,2/) > 0: і Л < р + Dy, By ^ d}, Р = {(t_yx) > 0: tB < -g - x>, Ax ^ b},.

/(*»У) = (Pi *) + (*> -^2/) + (9, У).

Задача 5. Найти (x*, у") Є 5/(_ГіУ)(.М x fi) Положим далее

Ь=(0„,О_п;Ь), ji = (y,u,z),

/0 E 0\ f-D^T

W=\0 0 0, П=-В
\0 0 0/ \ 0

где 0„ — нулевой вектор в Rⁿ, v = (j>,—d,—g), q* = (Z>x*,0_n),

^W= (o o)'⁵⁼(~o^B -^)^ = 0/.^ = (-^)^-

единичная матрица порядка n, P(u) = {(t,x) > 0: tB < -u — .Dx, Ax > 6}, <р(х,т/) = тах_иЄЯ {у, и) + (y,Dx) + (p,x), где Я =

Задача 6. Найти (х**,у**) Є S^^M х П)

Пусть х = (х,х_п+1), Ь = (Ь.1,-1), р = (р,0), z = "А 0 "І _ (*,*«.!,*і+₂), А = 0 1 , М = {х Є R+⁺¹: Ах > Ь},

. -¹. D = [Z?g], Р(«) = {(*,) > 0: Ш < -u - І?х,Лх > Ь}, З = {(?, У) > 0: zA < р + _УД % ^ d}.

Задача 7. Найти точку Нэша в игре 3-х лиц с платежными

функциями игроков

fi(x,y,u) = max{(y,u) + {y,Dx) + (p,x)} f₂{x,y,u) = max {{у, и) + {y,Dx) + (q,y) + {p,x)} /з (x, у, и) = max max {(у, u) + (у, Dx) 4- (p, x)}

в которой множества if, (7 и М являются множествами допустимых стратегий соответственно первого, второго и третьего игроков.

А.2. Основные теоремы.

ТЕОРЕМА 4.1. (Необходимые и достаточные условия седло-вой точки для функции /(х,у) на М х 1). Для того чтобы (х*,у*) была седловой точкой функции /(х, у) = (р, х) + (х, Dy) + (g,y) наМхСі необходимо и достаточно существование t* ^ 0, z* ^ 0 таких, что (г*,у*) и (t*,x ) являются решениями задач линейного программирования (b,z) + {q, у)—maX(_Z)J/)_eg u ( — d,t) + (p,x) —>miri(_t)a.)_ep, образующих двойственную пару.

СЛЕДСТВИЕ 4.1. Пусть Ф(г,у,<, х) — функция Лагран-жа для пары двойственных задач линейного программирования (b,z) + (q,y) —max_(2tJ/)6Q и { - d,t) + (р,х) —>тіп_(1)Х)єР и L(x,y) = (р,х) + (ж,Dy) + (g,у). Для того чтобы ((л , у ), (t ,х )) бьиа седловой точкой функции Ф(г,у,і,х) необходимо и достаточно, чтобы (х*,у*) была седловой точкой функции L(x,у) на М х П. При этом Ф(г*,у*,t*,x*) = L(x*,y*).

ТЕОРЕМА 4.2. (необходимые и достаточные условия седловой точки для функции у(х,у) на М х )). Для того, чтобы (х ,у ) была седловой точкой функции <р{х,у) = тах„_ея (у> и) + (y,Dx) + (р,х) на М х U необходимо и достаточно существование t* ^ 0, и* > 0, z* > 0, таких что и* Є Argmax_u# (y*_f и), a (z^y^o*) и (і*,х*, и*) являются решениями соответственно задач

max ((6,2).+ (у,и)}—>тах

mm {( — d, t) -\- (p,x)\—unax
(*,*)eP(u) ^lv v> it _uH

и выполнение равенства mas

max\max{y,u) + {y,Dx*) + {p,x*)} = (y*,u) + (y*,Dx*) + (p,x')

t/ЄП І иЄ// J

ТЕОРЕМА 4.3. (Необходимые и достаточные условия точки Нэша в игре трех лиц на М х П х Я). Пусть (х*, у*, и*) бМх SlxH ии* Є Argmax„_e/r {у*,и), у* Є Argmax_yen{max_lieW (У,")+ {q,y) + (y,Dx*) + (p,x*)}. Для того чтобы (х*, у*, и*) была точкой Нэша в игре трех лиц на М xflxH с платежными функциями /1,/2,/3. необходимо и достаточно, чтобы точка (х*,у*) была седловой точкой антагонистической игры наМхП с платежной функцией п(х, у) = тах_иЄн{(у,и) + (y,Dx) + {q,y) +

ТЕОРЕМА 4.4. Разрешилостъ задач тах^_г)У)_Єд{(Ь, z) -4-(у,и)} —»тах_иея и тах_їЄп{тах,,_ея (у,и) + (у,>х*) + (р, х*)} = (у*,и ) + (у ,Dx*) + (р,х*) эквивалентна разрешимости задач квадратичного программирования

(/i,W/i) + (b,/i)—» max _ (*)

<Є,ИЧ) + <9*, 0+ —v max . (**)

Приэтом, если р.* = (у*,и*, 2*) —решение 3080411(+), (i*,x*) — решение зада-чи линейного программирования

( — d.t) + (р, х) —> min . (* * *)

^{и =} (у*>^и ) — решение задачи (**), то (х*,у*) — седловая точка функции <р(х, у) на М X П.

Теорема 4.5. Разрешимость задачи

max { max (у, и) ,^ (у, Рх) + (р, х) } — min

эквивалентна разреиишоспш задачи квадратичного программирования

(«,A)-(C,W0 +

(А,{,г)єа

2t= {(A, ): A^O, >0, x >0, Лх > b,

g(x) < -2^ + 5^rA, () = (Dx,0_n)}.

Поскольку (а;*, у*) является седловой точкой функции т)(х,у) на М х П тогда и только тогда, когда точка (х*,у*) является седловой точкой функции ф(х, у) = тах_иЄя (у, и) + (у, Dx) + (р,г) ваМхЛ, заключаем, что для отыскания седловой точки функции Tj{x,y) на Mxft можно воспользоваться теоремами 4,4 и 4.5, если в формулировках этих теорем вместо Ь,z,x,D,П,Ь,и,/і,д*,р,Р(гГ),(2,21 использовать соответственно Ъ, z, х, D, П, (которая отличается от П тем, что в ней вместо

D и А стоят соответственно Z) и А ), 6 = (0_n,0_n,6), t/ = (Р. -<*,-5), = (y,u,z), q* = (-Dx*,0_n), p, P(u), Q, Я = {A > 0,>0,x>0: Ax ^ 6, g(x) < -2Wf + S^TX, А Є Л+¹}.

4.3. Вычислительная схема метода отыскания седловой
точки функции Дх, у) на М х Г2.

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

4.4. Вычислительная схема метода отыскания седловой
точки функции ip(x,y) на М х 17.

Теоремы 4.4 и 4.5 дают конечный метод решения полиэдральной а также антагонистической игры на полиэдральных множествах М и 1 с платежной функцией <р(х, у), поскольку векторные компоненты седловой точки (х*,у*) являются компонентами векторов-решений задач квадратичного программирования (*) и линейного программирования (***). 5. Задача Беллмана-Джонсона по критерию времени.

Пусть Qi — множество допустимых вариантов (расписаний) выполнения і-й работы на конечном числе единиц технологического оборудования, і Є 1,-ЛГ, /?' — время выполнения і-й рабо-

ты в соответствии с (jj-м расписанием. Пусть далее x,-_7i принимает значение 1, если і-ая работа выполняется в соответствии с ft-м расписанием и равно 0 в противном случае, X = {х = {*.,.} > 0: SgLi *іЯі = 1, '' Є hN}, П = {(х,г): а: Є A',z Є Д\*;„ Є {0,1}, _9і Є Ї707, і Є T7N, 2fei /,^?і*.« < *}, S. < 2 < І, В — (Л^г х J3i_i Qi) — матрица, в і-й строке которой все элементы, кроме стоящих в столбцах с номерами ]С}=і Qj + її » ІЗі=і Qj

и равных единице, равны нулю, А = I _ „ 1, Ь = (є, —є) , где

є Є І2+ — вектор, все компоненты которого равны единице, так

что X = {х Є i?/=>^Qj: Ах < 6} и пусть А - (ЛГ xg_al ф.) — матрица в і-й строке которой элементы /'*, l,Qi, стоят в' столбцах с номерами ^Уі~і Qj + 1,.--, Y^)=i Qj> ^a остальные элементы равны нулю, так что

= {іЄ Я^і-» ^Qy: Ах < ze\,

H С R^c-''=^t ' — множество векторов, компонентами которых могут быть лишь нули и единицы.

5.1. Математическая формулировка задачи.

УТВЕРЖДЕНИЕ 5.1. Задача Беллмана-Джонсона по критерию времени выполнения работ в введенных обозначениях может быть сформулирована как следующая

Задача 8. Z -» тіп{(_Гії)_: Аі<«,хєхпЯ}-

5.2. Основная теорема.

Пусть ф(и) — функция Лагранжа для задачи 8, X П Я = {х , t Є 1, Г}, где Т — некоторое конечное множество, (и, 1) = V, (-Є, 1) = //, <і = А^, *₂ = А₂и, где г = Ajz + А₂г, 0 Є і?+⁺¹ — вектор, все компоненты которого, кроме последней, равной единице, равны нулю, Z = {(и,^w) ^ 0^; ('i + *2 ^{— и}) = 0, faz + f₂7, /і) + («, (Ах*, 0)) > w, * Є Ї7Т}.

Теорема 5.1. Значение 9 в задаче линейного программирования ((є,и)),в)—max(_Vfllit_2ia,)_ez дает оценку снизу для задачи 8.

5.3. Вычислительная схема конечного метода отыскания оценки снизу в задаче 8.

Поскольку в силу теоремы 5:1 задача отыскания оценки снизу в задаче Беллмана-Джонсона является задачей линейного программирования, с учетом структуры множества X П Я при ее решении целесообразно использовать стандартную технику генерации столбцов, позволяющую при значительном числе Г решать задачу, двойственную к сформулированной в теореме 5.1, не имея априори всей информации о столбцах этой двойственной задачи, и определять из решения вспомогательной задачи линейного программирования в соответствии со схемой Данцига-Вулфа -вводимые в базис координирующей задачи столбцы.

6. Задачи математического программирования со смешанными переменными.

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

6.1. Математическая формулировка задачи.

Задача 9. Найти

(V,t/*) Argmin {{ci,u) + (c₂,u)}.

Пусть Tjk — гиперплоскости в R^п вида Г_,-д. = i^Tjki- E"=i^Tjfci < Т - max{s$_xs"fc"}} и TJ_k — полупространства, порожденные Tjk и содержащие начало координат в R^{m п}.

6.2. Основная теорема.

ТЕОРЕМА 6.1. А\ = I _т \, где А\ и А\ имеют одинаковые первыеп столбцов и в каждом столбце і, і Є 1,п, ненулевые элементы являются крайними точками выпуклого многогран~ ника Ні П (f)j_tkTjk), где Ні определяется линейными неравенствами, содержащими переменные т^ в системе ограничений задачи.

6.3. Вычислительная схема метода решения задачи 9.
Поскольку компоненты вектора v — целые, а компоненты

вектора и — неотрицательны, задача 9 может быть решена методом разложения (Бендерса) для решения задач математического программирования с линейными ограничениями и смешанными переменными. Однако непосредственное применение метода Бендерса предполагает, что все элементы матрицы А — (A_lt А2), ^в которой первые п строк образованы координатами векторов и* — крайних точек Q, известны априорно.

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

В соответствии с вычислительной схемой метода Бендерса при решении задачи 9 на каждом шаге (кроме начального) после фиксации целочисленных переменных должно искаться оптимальное решение в задаче линейного программирования (b—A₂v, z) —у max₂. дт₂^_с. В силу теоремы 6.1 для решения этой задачи не удается использовать процедуру генерации столбцов, однако структуру первых п столбцов матрицы Лі или, что то же, первых п строк матрицы A_t можно использовать для решения этой задачи с помощью модифицированного симплекс-метода, применяемого к прямой задаче {ci,u) — min_u: Ліи>ь-д₂«- Действительно^ нулевой строке конечной симплекс-таблицы этой прямой задачи будут находиться значения двойственных переменных, образующие оптимальное решение рассматриваемой задачи линейного программирования. В то же время, при решении

нрямой задачи удается воспользоваться процедурой генерации столбцов, если заметить, что любая крайняя точка и^р выпуклого многогранника П порождает 1т п столбцов матрицы Лі, а именно: столбцы, у которых в первых п строках ненулевыми элементами являются числа и^р_к1,... ,w^._n. Эта крайняя точка может быть найдена из решения вспомогательной задачи линейного программирования в соответствии со схемой генерации столбцов.

Пусть Т(к) — базис системы ограничений рассматриваемой прямой задачи, где к — номер итерации модифицированного симплекс-метода, применяемого к решению этой задачи, причем на первом шаге решения такой базис соответствует начальному допустимому базисному решению, легко получаемому с использованием слабых переменных. Пусть далее ігт{к) — вектор двойственных переменных, соответствующих базису Т(к), и пусть т — и^р — оптимальное решение вспомогательной задачи линейного программирования (я7(*),т) —* пгіп_гЄП) порождающее 2го п векторов-столбцов матрицы Л], у которых в первых п строках ненулевой элемент содержится только в одном столбце (эта задача решается на (fc + 1)-й итерации модифицированного симплекс-метода, применяемого к прямой задаче. Обозначим d^P_ki(k) — оценки векторов базиса Т(к), соответствующих столбцам матрицы Лі с теми же номерами, что и в {ыд.,}, которые условно далее обозначены как u^P_ki. Если для некоторых j*,fc*,»* справедливо (TT(i),j._fc.,-.) < dy._А.,-.(А:), то вектор ш^р._к._{. подлежит вводу в базис на (к 4- 1)-й итерации рассматриваемого симплекс-метода, при этом Пт(к+1) ^Е djki{k +1) пересчитываются по стандартным формулам; в противном случае базисное решение прямой задачи оптимально.

РАЗДЕЛ IV. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ ЭЛЕМЕНТОВ ОПТИМИЗАЦИОННОГО АНАЛИЗА К ИССЛЕДОВАНИЮ ВОЗМОЖНОСТЕЙ ГРУЗОВЫХ ТРАНСПОРТНЫХ СИСТЕМ.

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

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

МЕТОДОЛОГИЧЕСКИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ ОПТИМИЗАЦИОННОГО АНАЛИЗА ДЛЯ ИССЛЕДОВАНИЯ ВОЗМОЖНОСТЕЙ ГРУЗОВОГО ТРАНСПОРТА использовались при обсуждении и выработке концепции информатизации транспортно-дорожного комплекса Российской Федерации, проводимых в рамках договора между Институтом проблем управления и Министерством транспорта Российской Федерации. В частности, при выборе направлений информатизации предлагалось построение информационно-вычислительной сети, конфигурация которой должна была определяться с учетом географии основных грузопотоков и размещения производителей товаров и получателей грузов, производственных мощностей транспортных предприятий и сложившейся структуры и распределения транспортных средств по видам транспорта и по транспортным предприятиям внутри каждого вида транспорта. Была предложена структура информационно-вычислительной сети, основными элементами которой должны были служить автоматизированные системы управления транспортными предприятиями, решающие, в частности, задачи оперативного анализа и регулирования эксплуатационной деятельности транспортных предприятий.

Эти принципы использовались также при разработке основных положений и техническом проектировании двух подсистем автоматизированной системы управления морским транспортом АСУ "Морфлот": автоматизированной системы учета и слежения за движением контейнеров на морском транспорте и оперативного управления работой контейнерного терминала (АСК) и системы управления контейнерными перевозками на морском транспорте, осуществлявшихся в Институте проблем управление в рамках „аучного руководства разработками АСУ "Морфлот". В этих работах были сформулированы требования к структуре комплексов задач, связанных с планированием контейнерных пе-

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

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

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПЛАНИРОВАНИЯ РАБОТЫ ГРУЗОВЫХ ТРАНСПОРТНЫХ СИСТЕМ разрабатывались как в рамках работ по АСУ "Морфлот" , так и в рамках отдельных договоров Института проблем управления с Ростовским отделением Северо-Кавказской железной дороги, Балтийским морским пароходством, Ленинградским морским торговым портом, Отделом Тарифов Экономического управления Министерства Морского Флота СССР и Всесоюзным объединением "Совкомфлот". Так при разработке АСУ "Морфлот" для одного из грузовых районов Ленинградского морского торгового порта была сформулирована задача о загрузке контейнеров несколькими видами грузов (с учетом условий их совместимости и очередностью выгрузки отдельных грузов) в виде одной из модификаций задачи о рюкзаке, для другого грузового района порта была сформулирована задача об оценке выполнимости плана грузовых работ при имеющихся трудовых и технических ресурсах и задача об оптимальной корректировке (невыполнимых) плановых заданий в виде задач математического программирования с линейными ограничениями и специальной структурой целевой функции. Для одной из контейнерных линий Балтийского бассейна (Рига-Росток) по просьбе отдела тарифов Экономи-

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

В ходе выполнения договорной работы с Балтийским морским пароходством для одной из крупнейших линий перевозок грузов иностранных фрахтователей этого пароходства, связывающей порты Европы и Юго-Восточной Азии была построена математическая модель, описанная выше в разделе И. Использование этой модели с линейными ограничениями квазиблочной структуры давало пользователям возможность анализировать, в частности, целесообразность перевозок собственных порожних ' контейнеров между портами линии, лизинга порожних контейнеров под появляющиеся грузы и привлечения конкретных гру- ' зов для перевозки по конкретному расписанию, а также целый ряд важнейших экономических показателей работы линии, таких как чистая валютная выручка, окупаемость валютных затрат, прибыль, себестоимость перевозок на линии и на отдельных ее участках и др. Еще одна модель для выбора конфигурации линии в условиях фидерного обслуживания морских портов в виде системы линейных ограничений с целочисленными переменными была построена при выполнении договорных работ с Мин-морфлотом (эта модель также приведена выше в разделе И). Использование этой модели на одной из линий Азовского морского пароходства позволяло пользователю осуществлять выбор числа и расположения базовых портов линии и схемы развозки - сбора

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

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

МЕТОДЫ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ИССЛЕДОВАНИЯ ВОЗМОЖНОСТЕЙ ГРУЗОВЫХ ТРАНСПОРТНЫХ СИСТЕМ использовались при решении задач, сформулированных на основе перечисленных выше математических моделей.

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

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

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

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

Похожие диссертации на Оптимизационный анализ и исследование возможностей грузовых транспортных систем: методология, модели, методы, приложения

Методология, модели и методы исследования развития структурно-неоднородных электроэнергетических системЧжэн Мэй Те

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

Моделирование и метод анализа задач обслуживания с приложением к авиационной транспортной системеАмирханов, Шамиль Даниялович

МЕТОДОЛОГИЯ ПРОЕКТИРОВАНИЯ КОНЕЧНЫХ ИЗДЕЛИЙ, ВКЛЮЧАЮЩИХ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ И КОМПЛЕКСЫ, НА ОСНОВЕ СБИС КЛАССА "СИСТЕМА НА КРИСТАЛЛЕ" С ИСПОЛЬЗОВАНИЕМ ВЫСОКОУРОВНЕВЫХ СИСТЕМНЫХ МОДЕЛЕЙГубарев, Виталий Александрович

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

Разработка и исследование средств взаимодействия приложений и методов защиты вычислительного комплекса транспортной системыКорнев Дмитрий Александрович

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

Новые версии метода симплексных погружений в выпуклом программировании и их приложенияАпекина, Елена Викторовна

Численные методы решения неклассических линейных уравнений Вольтерра I рода и их приложенияМаркова, Евгения Владимировна

Синтез и анализ ортогональных преобразований, учитывающих "психофизические" свойства зрения и их приложение в сжатии изображенийБабаян, Наира Арцруновна