авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 |
-- [ Страница 1 ] --

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Тихоокеанский государственный

университет»

Г. М. Вербицкий

ОСНОВЫ ОПТИМАЛЬНОГО

ИСПОЛЬЗОВАНИЯ МАШИН

В СТРОИТЕЛЬСТВЕ И ГОРНОМ ДЕЛЕ

Утверждено издательско-библиотечным советом университета

в качестве учебного пособия

Хабаровск

Издательство ТОГУ 2009 УДК ББК В Р е ц е н з е н т ы:

кафедра “Строительные и путевые машины” Дальневосточного государственного университета путей сообщения (завкафедрой проф. Ю. А. Гамоля);

завлабораторией Института горного дела ДВО РАН РФ заслуженный деятель науки РФ, д-р техн. наук, проф. Г. В. Секисов Научный редактор д-р техн. наук, проф. С. Н. Иванченко Вербицкий Г. М.

Основы оптимального использования машин в строительстве и гор ном деле : учеб. пособие / Г. М. Вербицкий. – Хабаровск : Изд-во Тихооке ан. гос. ун-та, 2006. – 105 с ISBN 978-5-7389-0789- Учебное пособие написано к курсам «Комплексная механизация строительства»

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

Учебное пособие предназначено для студентов специальностей 190205. “Подъёмно-транспортные, строительные, дорожные машины и оборудование”, 130403.65 “Открытые горные работы” и инженерно-технических работников.

УДК ББК © Вербицкий Г. М., ISBN 978-5-7389-0789- © Тихоокеанский государственный университет, ОГЛАВЛЕНИЕ ВВЕДЕНИЕ …………………………………………………………………… 1. ПРИНЦИПЫ ОПТИМАЛЬНОЙ ОРГАНИЗАЦИИ СТРОИ ТЕЛЬНОГО ПРОИЗВОДСТВА И ИСПОЛЬЗОВАНИЯ МАШИН В СТРОИТЕЛЬСТВЕ…………………………………………. 1. 1. Сущность и значение экономико-математических методов планирования организации строительства и использования машин……..…………………………………………………………… 1. 2. Задачи оптимизации использования машин в строительстве…. 1. 3. Критерий оптимальности использования машин в строи тельстве……………………………………………………………… 1. 4. Определение областей эффективного применения машин и их комплектов…………………………………………………………... 1. 4. 1. Общие сведения об областях эффективного применения машин…………………………………………………………. 1. 4. 2. Области эффективного применения бульдозеров………….

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

Достижение цели возможно и без привлечения дополнительных ма шинных ресурсов за счёт повышения выработки машин. Вместе с тем ана лиз рабочих процессов в строительстве позволяет утверждать, что значи тельные потери рабочего времени используемых машин (15–20 %) обу словлены неудовлетворительной организацией механизированного произ водства и неисправностью машин. Одной из возможностей повышения выработки машин является совершенствование методов планирования и оперативного управления на основе применения экономико математических методов для выбора оптимальных решений.

Задачи планирования и организации строительства, управления им, в том числе и механизированным как составляющим процесса, решаются во многих случаях на основе накопленного опыта выполнения аналогичных работ и интуиции руководителей – организаторов производства. При этом могу быть допущены те или иные просчёты, которые иногда остаются не замеченными или выявляются тогда, когда их уже трудно исправить. При нимать правильные решения (а это основной элемент любого процесса управления) в условиях существенного усложнения технологии производ ства, расширения номенклатуры выполняемых работ, широкой взаимоза меняемости машин и их комплектов, быстрого роста всех хозяйственных связей становится всё труднее и труднее. Это обусловливается возможным наличием множества вариантов принятия руководящего решения. Руково дители предприятий и организаций оказались жертвами “информационно го взрыва”. Объём информации, поступающей в их адрес, значителен, воз растает с течением времени всё с большей интенсивностью, а перерабаты вать её по-старому уже невозможно. В связи с этим потребовалось созда вать новую форму и методы управления на основе использования элек тронно-вычислительной техники и экономико-математических методов.

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

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

Учебное пособие подготовлено по результатам исследований, прове дённых в своё время А. И. Власовым, Н. С. Ваном, Г. М. Вербицким и др.

под руководством доктора технических наук, профессора П. И. Сорокина, и на основе некоторых публикаций в печати [1, 3, 8, 11, 14].

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

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

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

В приложении приведён пример реализации одной из задач. При этом объём исходной информации принят приемлемым для реализации модели без привлечения ЭВМ.

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

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

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

Категория приведенных затрат, как критерий экономической эффек тивности строительства был обоснован в работах академика Т. С. Хачату рова [15 ] и в настоящее время принят основным.

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

Достоинства экономико-математических методов:

– более широкий охват условий и факторов процесса и, следователь но, более обоснованное значение оптимума;

– возможность рассмотрения множества вариантов в конкретных условиях и выбора оптимального из них;

– существенное снижение трудоёмкости расчётов при наличии отла женных программ на ЭВМ.

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

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

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

Крупнейший советский математик Л. В. Канторович ещё в 1939– 1945 г. г. опубликовал работы, которые определили основные направления развития линейного и других форм математического программирования [7]. За короткий срок в нашей стране разработка и внедрение этих методов в практику строительства и его механизацию получили значительное раз витие.

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

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

Необходимость решения задач оптимизации использования машин объясняется:

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

– широкой взаимозаменяемостью машин и их комплектов, ремонт ных средств для выполнения работ;

– возможностью комплектования оптимального состава парка машин специализированной организации;

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

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

Физический смысл задач оптимизации (рис. 1. 1) следующий:

– задача 1. 1 – так как каждая машина наиболее выгодно может быть применена при выполнении определённых работ в пределах реального парка машин, то и программа работ для парка машин на плановый период при минимизации общих затрат на их выполнение может быть конкретной;

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

Задачи оптимизации использования машин 1.Задачи производственной 2. Задачи технической эксплуатации машин эксплуатации машин 1.1. Формирование 2.1. Определение оп программы работ тимальной потребнос парку машин ти в ремонтах машин 1.2. Распределение 2.2. Определение видов механизиро- структуры и опти ванных работ по спо- мального состава ре собам выполнения монтно-эксплуата ционных средств пар ка машин 1.3. Оптимизация по точных механизиро ванных работ 2.3. Оперативное управление подвиж ными средствами экс 1.4. Распределение плуатации машин машин парка по объ ектам программы работ 2.4. Календарное пла нирование эксплуата ции парка машин при 1.5. Определение строительстве рассре структуры и опти- доточенных объектов мального состава парка машин Рис. 1. 1. Состав задач оптимизации использования машин – задача 1. 2 – при заданной программе работ парку машин каждая машина или комплект машин могу быть использованы прежде всего на тех работах, где их применение наиболее выгодно в сравнении с другими, при минимизации затрат на выполнение программы работ с условием макси мальной загрузки парка машин;

– задача 1. 3 – минимальные затраты на выполнение поточных меха низированных работ обусловливаются оптимальными параметрами пото ка;

– задача 1. 4 – оптимальные результаты работы организации, эксплу атирующей машины и выполняющей подрядные работы, обусловливаются не только оптимальным распределением работ по способам выполнения с максимально возможной загрузкой машин парка (задача 1. 2), но и в соче тании с этим оптимальным распределением машин парка по объектам про граммы работ;

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

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

– задача 2. 2 – аналогична задаче 1. 5;

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

– задача 2. 4 – носит комплексный характер, объединяет в себе усло вия и цели задач 2. 1, 2. 2 и 2. 3.

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

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

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

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

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

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

Мобильный критерий эффективности должен иметь следующие ха рактеристики:

1) определять выгодность выбранного варианта;

2) выражаться количественно;

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

4) определяться точно и быстро без больших затрат времени;

5) обеспечивать учёт всех существенных сторон решаемой задачи;

6) иметь физический смысл, что делает его понятным и ощутимым.

Одной из экономических характеристик производственных процес сов в хозяйстве страны, в том числе и в строительстве, принята себестои мость Cед (себестоимость единицы продукции), для механизированных процессов зависящая от величины Cчq – стоимости часа рабочего времени машины, используемой в процессе:

Счq Cиq Cеq, (1. 1) где Cиq – стоимость часа использования машины типоразмера q непосред ственно в работе, р./ маш.-ч;

Cеq – затраты на перебазирование машины типоразмера q, отнесённые к машино-часу нахождения машины на объек те, р./ маш.-ч.

В развёрнутом виде 1 Cиq kн.р Сг C тек (1. 2) Фг q где Cгq – годовые затраты на капитальный ремонт и реновацию, р./ год;

Cтекq – текущие эксплуатационные затраты в течение часа работы маши ны, р./ маш.-ч;

kн.р – коэффициент накладных расходов на затраты по экс плуатации машины;

Фгq – годовой фонд рабочего времени машины, маш.-ч/ год.

o o o, Cеq kн.р Сп Cс C т Lт (1. 3) 1 1 q где Cп q – затраты на погрузку-разгрузку машины на транспортное сред ство и связанный с этим (если необходимо) монтаж-демонтаж или сцеп ку-отцепку от буксирующего средства (тягача), р.;

Cсq – стоимость устрой ства сооружений, необходимых для нормальной работы машины на объек те, р.;

C тq – стоимость транспортирования машины q на средствах типа o o 1,..., на 1 км по дорогам с характеристиками 1,...,, р./ км;

Lтq – длина пути транспортирования по дороге с характеристикой, км.

Непроизводительные расходы от простоя машины в течение часа оцениваются величиной Cч.пq Cпq Cеq, (1. 4) где Cпq – затраты на один час простоя машины типоразмера q, р./ маш.-ч, 0,5Cэн Cсм.о P.

Cпq kн.р Cг (1. 5) Фг q Здесь Cэнq – затраты на энергию (горючее), отнесённые к машино часу работы машины, р./ маш.-ч;

Cсм.о q – затраты на смазочные и обтироч ные материалы на один машино-час работы, р./ маш.-ч;

Pq – часовая зара ботная плата мащиниста (машинистов), р./ ч.

Таким образом, затраты на выполнение механизированных работ, определяемые в такой постановке, как критерий эффективности, и пред ставляемые в виде трёх слагаемых, назовём общими и обозначим o C Cи Се Сп min, (1. 6) где Cи, Cе, Cп – затраты соответственно на исполнение работ, перебазиро вание машин и простой их из-за недогрузки.

Экономическое сравнение различных вариантов выполнения меха низированных работ может быть проведено и по критерию себестоимости (затрат на измеритель объёма работ):

o ИC Сед, (1. 7) Q где И – измеритель объёма работ;

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

1. 4. Определение областей эффективного применения машин и их комплектов 1. 4. 1. Общие сведения об областях эффективного применения машин Одна и та же работа в определённых условиях строительства может быть выполнена различными машинами, отличающимися друг от друга конструктивно-техническими параметрами: мощностью, мобильностью, рабочими органами и т. п. Это обусловит различные результаты, которые характеризуют эффективность производства: продолжительность выпол нения работ, их себестоимость, трудоёмкость и др. Кроме того, условия выполнения одной и той же работы на разных объектах могут существен но изменяться, что неизбежно отразится на эффективности выполнения этой работы конкретной машиной. Изменение условий производства работ влияет на эффективность их выполнения машинами разных марок далеко не одинаково.

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

– планирования оптимального использования наличного парка взаи мозаменяемых машин;

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

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

В соответствии с рекомендациями проф. С. Е. Канторера область эффективного применения машин устанавливается по минимуму себесто имости единицы объёма работ Cед.

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

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

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

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

И Си Cе o ИC И Cедq kн.р Cг Cтек Фг q П ч.эq Q Q И Cт.п Ст Lт q, (1. 8) Q где C т.пq – затраты на перебазирование машины типоразмера q, не зави сящие от расстояния перебазирования (на погрузку-разгрузку, буксировку отцепку, необходимые демонтаж-монтаж и т. д.), р.;

C тq – затраты на пе ребазирование машины типоразмера q на расстояние 1 км, р./ км;

Lтq – расстояние перебазирования машины типоразмера q, км.

1. 4. 2. Области эффективного применения бульдозеров Эксплуатационная часовая производительность бульдозеров в (м3/ ч) 3600 Bh k укл П ч.э (1. 9) k1k 2, 2tgTц k р где B и h – соответственно ширина и высота отвала, м;

k р – коэффици ент разрыхления грунта, kр 1,1 1,3 ;

k укл – коэффициент, учитывающий влияние уклона на величину производительности бульдозера ( k укл 1 – при работе вниз по уклону, k укл 1 – при работе вверх по уклону);

– угол естественного откоса грунта в движении, равный примерно 2/3 угла естественного откоса грунта в покое;

Tц – продолжительность рабочего цикла бульдозера, с, которая для общего содержания рабочего цикла нахо дится из выражения lр 2l Tц 2tп tо 2tпов. (1. 10) vср v р Здесь l – дальность перемещения грунта, м;

lр – длина пути резания грун та, равная обычно 5 7 м;

t п – время на переключение передач, t п 4 5 c;

t о – время опускания отвала, tо 1 2 с;

tпов – время поворота бульдозе ра, tпов 10 с;

– скорость движения бульдозера при резании грунта, м/с;

v ср – средняя скорость движения бульдозера при перемещении грунта и обратном ходе, м/с;

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

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

По рекомендациям С. Е. Канторера [11] принимаем для бульдозеров k1 0,56, k2 0,75.

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

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

kр 1,1;

k укл 0,9;

30 и tg 0,577.

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

978Bh vср П ч.э (1. 11), 2l t1vср где t1 – затраты времени на все элементы рабочего цикла, не зависящие от дальности перемещения грунта и средней скорости бульдозера.

Тогда себестоимость единицы Cед ( р./ 100 м3) с учётом предыдуще го соотношения после некоторых преобразований выглядит следующим образом:

И И Cт.п Ст Lт Cед Стек l kн.р Сг Фг Q 489 Bh vср t1И Стек.

kн.р Сг (1. 12) Фг 978Bh Таким образом, функция себестоимости в зависимости от аргумен тов-факторов, характеризующих условия производства работ, будет иметь вид И A BLт Сl D,, Сед (1. 13) Q где A, B, C, D – постоянные для данной машины величины (из (1. 5)).

Если в качестве примера рассмотреть бульдозеры ДЗ-54, ДЗ-9 и ДЗ 34С, то при условии перебазирования последних на объект на трейлере по дорогам III категории со скоростью 11,5 км/ч постоянные величины A, B, C, D будут иметь значения, представленные в табл. 1. 1.

Таблица 1. Постоянные величины формулы себестоимости единицы объёма работ бульдозерами Величина Бульдозер C A B D ДЗ-54 242,6 46,86 3,6 106, ДЗ-9 383,9 59,85 3,15 124, ДЗ-34С 628,4 86,79 2,85 141, Если область эффективного применения машин устанавливается на уровне конкретной строительной организации, то себестоимость может быть представлена в виде функции трёх аргументов: объёма работ на объ Q екте, расстояния перебазирования машины на объект Lт и дальности И перемещения разрабатываемого грунта l :

– для бульдозера ДЗ- И 46,86 Lт 241, Cед 3,6l 106,5;

Q – для бульдозера ДЗ- И 59,85Lт 383, Cед 3,15l 124,2;

Q – для бульдозера ДЗ-34С И 86,79 Lт 628, Cед 2,85l 141,3.

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

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

Если приравнять себестоимости для бульдозеров ДЗ-54 и ДЗ-9:

И 46,86 Lт 241,6 И 59,85 Lт 383, 3,6l 106,5 3,15l 124,2, Q Q то из равенства можно записать соотношение Q 59,85 46,86 Lт 383,9 241,6 13,0Lт 142, 3,6 3,15l 106,5 124,2 0,45l 17,7.

И Это соотношение есть функция такого объёма работ на объекте в за висимости от расстояния перебазирования на объект Lт и средней дально сти перемещения грунта на объекте l, при котором себестоимости едини цы объёма работы для сравниваемых машин равны. Эту функцию можно назвать границей областей эффективного применения сравниваемых ма шин (рис. 1. 2).

Естественно, что границы областей эффективного применения должны быть рассматриваемы в положительном квадранте параметров, ха рактеризующих объекты. Расположение одной из ветвей графика в области фиктивных (отрицательных) объёмов (рис. 1. 2) означает, что в диапазоне дальностей перемещения грунта l 0 40 м одна из рассматриваемых ма шин при любых объёмах работ на объекте и расстояниях перебазирования в сравнении со второй выгодна всегда. Остальная часть положительного квадранта (при дальностях перемещения грунта l 40 100 м) оказывается поделённой графиком при конкретном расстоянии перебазирования Lт на две области (рис.1. 2, 1. 3).

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

Q 20 измерителей ( И 100 м3), l 20 м, Lт 5 км:

При И – для бульдозера ДЗ- 100(46,9 5 241,6) Cед 3,6 20 106,5 202,3 р./ 100 м3;

– для бульдозера ДЗ- 10059,9 5 383, Cед 3,2 20 124,2 221,1 р./ 100 м3.

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

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

Q,100 м И LT =5 км 10 LT =10 км LT =15 км l, м 10 20 30 40 50 60 70 80 - - - - - - Рис. 1. 2. Границы областей эффективного применения бульдозеров ДЗ-54 и ДЗ- Q,100 м И ДЗ- ДЗ- l, м 0 10 20 30 40 50 60 70 80 Рис. 1. 3. Области эффективного применения бульдозеров ДЗ-54 и ДЗ-9 при Lт 5 км По графикам (см. рис. 1. 2) видно, что при увеличении расстояния перебазирования Lт область эффективного применения менее мощного бульдозера расширяется, и наоборот. Такие графики могут быть построены для большинства конкурирующих машин.

На основании графиков границ областей эффективного применения парка бульдозеров при их попарном сравнении (см. рис. 1. 4) можно по строить совокупный график областей эффективного применения парка бульдозеров (пример графика для трёх бульдозеров на рис. 1. 5).

На объектах, характеризующихся средней дальностью перемещения грун та – l 40 м, любым объёмом работ (см. рис. 1. 5), и на объектах с мень шими объёмами работ и любой дальностью перемещения грунта, экономи чески более выгоден бульдозер ДЗ-54. На объектах с большими объёмами работ и дальностями перемещения грунта лучше применять бульдозер ДЗ 34С, во всех остальных случаях – бульдозер ДЗ-9.

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

Q,100 м И ДЗ ДЗ - ДЗ С ДЗ - ДЗ - - ДЗ 4С - l, м 40 60 Рис. 1. 4. Границы областей эффективного применения бульдозеров при попарном сравнении ( Lт 5 км) Q,100 м ДЗ- 34С И ДЗ- ДЗ- l, м 40 60 Рис. 1. 5. Совокупный график областей эффективного при менения бульдозеров при Lт 5 км 1. 4. 3. Установление областей эффективного применения машин разного вида Рассмотрим области эффективного применения бульдозеров и скре перов в зависимости от дальности перемещения разрабатываемого грунта при возведении земляного полотна.

Себестоимость единицы объёма работ:

– для скрепера ДЗ- И 289,8 53,34 Lт Cед 1,93l 239,1, Q – для скрепера ДЗ- И 240,9 48,06 Lт Cед 1,00l 277,8.

Q В соответствии с этим при объёме работ на участке Q 5000 м3 и расстоянии перебазирования Lт 5 км зависимости себестоимостей от дальности перемещения грунта будут иметь следующий вид:

Cед 3,6l 115,8;

– для бульдозера ДЗ- Cед 3,15l 137,7;

– для бульдозера ДЗ- Cед 2,85l 162,3;

– для бульдозера ДЗ-34С Cед 1,93l 250,2;

– для скрепера ДЗ- Cед 1,00l 287,4;

– для скрепера ДЗ- По этим зависимостям на рис. 1. 6 построены графики, на которых достаточно чётко прослеживаются области эффективного применения сравниваемых машин.

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

3,6l 115,8 3,15l 137,7;

137,7 115, lг 48,6 м.

3,6 3, руб.

Сд., 100 м е 450 ДЗ- ДЗ- 360 ДЗ- ДЗ- ДЗ- ДЗ- ДЗ- ДЗ- l, м 10 20 30 40 50 60 70 80 Рис. 1. 6. Графики зависимостей себестоимостей от дальности перемещения грунта Для бульдозера ДЗ-9 и скрепера ДЗ-11:

3,15l 137,7 1,00l 287,4;

287,4 137, lг 69,9 70 м.

3,15 1, Одновременно с этим можно установить, какие из всех рассматри ваемых машин целесообразно использовать в данных условиях, чтобы обеспечить минимальные затраты. Наиболее эффективным является при менение следующих машин на объекте: бульдозера ДЗ-54 – при перемеще нии грунта на расстояние до 50 м, бульдозера ДЗ-9 – в пределах 50–70 м, скрепера ДЗ-11 – свыше 70 м (см. рис. 1. 6).

Определение областей эффективного применения комплектов ма шин производится аналогичным образом с учётом затрат на все машины комплектов и зарплату рабочих.

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

Этот метод эффективен при однократном назначении машины на объект и не гарантирует оптимальности назначений машин на все объекты в сово купности.

2. ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ ЗАДАЧ ОПТИМИЗАЦИИ ИСПОЛЬЗОВАНИЯ МАШИН В СТРОИТЕЛЬСТВЕ 2. 1. Формирование экономико-математической модели задачи оптимизации Прежде чем рассматривать вычислительные методы задач оптимиза ции использования машин, необходимо рассмотреть постановку простей шей задачи.

У с л о в и е з а д а ч и. Участок насыпи земляного полотна автомо бильной дороги с объёмом земляных работ в 34400 м3 (344 измерителя) должен быть отсыпан из карьера, находящегося в среднем на расстоянии 400 м от участка, двумя звеньями машин, в которых ведущими машинами являются скрепер самоходный ДЗ-11 (3 машины) и экскаватор ЭО-4111 с автомобилями-самосвалами ЗИЛ-ММЗ-555. Срок отсыпки не должен пре вышать 50 рабочих смен (продолжительность смены – 8,2 ч). Каждое из звеньев имеет достаточное (по производительности основных машин) ко личество комплектующих машин (бульдозеров ДЗ-54, катков Д-630), поз воляющих выполнять законченный цикл работ по отсыпке земляного по лотна.

Себестоимости разработки, транспортирования, разгрузки и уплот нения измерителя грунта: звеном скреперов – 2100 р./ 100 м3, звеном экс каватора – 2570 р./ 100 м3. Расчётная норма времени на измеритель грунта:

для скрепера – 4,42 маш.-ч/ 100 м3, для экскаватора – 2,77 маш.-ч/ 100 м3.

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

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

Допустим, что звеном скреперов должно быть отсыпано x1 измери телей грунта, а звеном экскаватора – x2. При этом суммарный объём ра бот, который должен быть выполнен обоими звеньями, не должен быть меньше заданного.

x1 x2 344. (2. 1) Для выполнения скреперных работ необходимо 4,42 x1 машино часов скреперов при наличном количестве 3 8,2 50 1230 маш.-ч.

Значит, 4,42 x1 1230. (2. 2) Для выполнения работ экскаватором требуется 2,77 x2 машино-часов при наличии 8,2 50 410 маш.-ч.

Значит, 2,77 x2 410. (2. 3) Помимо ограничений, для решения задачи необходимо сформулиро вать целевую функцию, т. е. величину, которую необходимо минимизиро вать. В рассматриваемой задаче такой целевой функцией являются затра ты, равные o C 2100 x1 2570 x2. (2. 4) Стремление их минимизировать обозначается в виде o C 2100 x1 2570 x2 min. (2. 5) Очевидно, что искомые объёмы работ звеньев не должны быть отри цательны. Следовательно, x1 0;

x2 0. (2. 6) Таким образом, математическая формулировка рассматриваемой за дачи будет иметь вид o C 2100 x1 2570 x2 min x1 x2 1230 (2. 7) 4,42 x 2,77 x2 x1 x2 Из (2. 7) видно, что математическая формулировка задачи линейного программирования включает в себя три части: целевую функцию, ограни чения и граничные условия на переменные.

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

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

2. 2. Некоторые графоаналитические сведения для графической интерпретации задач оптимизации Л и н е й н ы е у р а в н е н и я. Уравнения различаются по степени переменных и их числу. Уравнения с переменными в первой степени назы ваются линейными. Графическое изображение – прямая линия. Уравнения могут быть записаны в следующих различных формах.

Пусть дано линейное уравнение с двумя переменными (рис. 2. 1) a1x1 a2 x2 b (2. 8) Рис. 2. 1. График линейного уравнения с двумя переменными Если x1 0, то x2 b / a2, точка – A(0, b / a2 ). При x2 0, x1 b / a1, а точка – B(b / a1,0). Форма (2. 8) – общая форма записи линейного уравне ния.

Разделим обе части на b :

a1x1 a2 x 1. (2. 9) b b Обозначим 1 b / a1, 2 b / a2. Тогда x1 x 2 1. (2. 10) 1 Значения 1 и 2 равны отрезкам, отсекаемым прямой на осях ко ординат. Поэтому уравнение, записанное в форме (2. 10), называется урав нением в отрезках. Его признаком является единица в правой части. Поль зуясь такой формулой, удобно строить график.

П р и м е р : x1 2 x2 4.

x x Уравнение в отрезках 1 2 1. График – рис. 2. 2.

-4 Рис. 2. 2. График уравнения в отрезках Уравнение (2. 8) представим в виде a2 x2 b a1x1 или b a x2 (2. 11) x1.

a2 a Обозначим d b / a2 ;

k a1 / a2. Тогда после подстановки получим x2 d kx1. (2. 12) Коэффициент k называется угловым коэффициентом, а уравнение (2. 12) – уравнением с угловым коэффициентом. Графически уравнение (2. 12) име ет вид, подобный рис. 2. 3.

Рис. 2. 3. Графическое изображение уравнения с угловым коэффициентом Из рис. 2. 3 видно, что k tg, а d есть отрезок, отсекаемый прямой на оси ординат. Изменение k приводит к изменению угла, а изменение d – к параллельному перемещению прямой.

Линейное уравнение с тремя переменными в общей форме записи имеет вид a1x1 a2 x2 a3 x3 b, (2. 13) а в геометрической интерпретации представляет собой плоскость. Разде лив обе части уравнения на b и обозначив b b b 1 ;

2 ;

3, (2. 14) a1 a2 a получим уравнение в отрезках:

x x1 x 2 3 1, (2. 15) 1 2 где 1, 2, 3 – отрезки, отсекаемые плоскостью на осях x1, x2, x3 (рис. 2. 4).

По аналогии с трёхмерным пространством полагают, что линейному уравнению с n неизвестными соответствует “плоскость”, которую назы вают гиперплоскостью.

Рис. 2. 4. График линейного уравнения с тремя переменными Уравнение гиперплоскости в n -мерном пространстве a1x1 a2 x2 an xn b. (2. 16) Линейные н е р а в е н с т в а. Пусть дано линейное неравен ство с двумя переменными:

a1x1 a2 x2 b, (2. 17) где b 0. Для того чтобы неравенство представить графически, во-первых, строят уравнение a1x1 a2 x2 b и, во-вторых, выясняют, что произойдёт, если от знака равенства перейти к знаку неравенства.

Вместо прямой, удовлетворяющей уравнению, получают часть плос кости, лежащей ниже прямой, так как координаты любой точки ниже пря мой будут удовлетворять неравенству (рис. 2. 5). Следовательно, неравен ство представляет собой полуплоскость. Эту полуплоскость называют об ластью разрешённых значений, а другую полуплоскость – областью за прещённых значений. Область запрещённых значений штрихуется. Об ласть запрещённых или разрешённых значений удобно определять для начала координат.

Рис. 2. 5. Графическое изображение линейного неравенства с двумя переменными П р и м е р : построить неравенство 2 x1 3x2 3. Рассмотрим уравнение 2 x1 3x2 3 и построим его на плоскости (рис. 2. 6).

Для определения той полуплоскости, которая удовлетворяет нера венству, определим, в какую полуплоскость входит начало координат. Для этого подставим в неравенство значения x1 0, x2 0 и получим 0 3.

Неравенство удовлетворено. Следовательно, начало координат находится в области разрешённых значений. Значит, область разрешённых значений расположена ниже прямой, а область запрещённых значений – выше пря мой, что и показано на рис. 2. 6 штриховкой.

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

П р и м е р: дана система неравенств 5x1 4 x2 20 (1) x1 x2 1 (2) 2 x1 x2 2 (3) (2. 18) 0 (4) x x2 0. (5) Построим эти неравенства (рис. 2. 7).

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

рис. 2. 7). Из рис. 2. 7 ОДР системы линейных неравенств с двумя пере менными имеет вид многоугольника. Однако ОДР не всегда является мно гоугольником.

Пусть в неравенстве (1) исходной системы знак будет изменён на об ратный. Область разрешённых значений для неравенства (1) будет обрат ной, а ОДР для системы будет незамкнутой (см. рис. 2. 8).

Если в исходной системе (2. 18) знаки в первых трёх неравенствах изменить на обратные, то, судя по рис. 2. 9, нет такой точки на плоскости, которая удовлетворяла бы всем неравенствам. В таких случаях говорят, что система неравенств несовместна, и поэтому ОДР отсутствует. Рас смотренные варианты ОДР могут быть сведены в схему (рис. 2. 10).

Рис. 2. 7. Графическое изображение системы неравенств с двумя переменными с замкнутой ОДР Рис. 2. 8. Графическое изображение системы неравенств с двумя переменными с незамкнутой ОДР Рис. 2. 9. Графическое изображение системы неравенств с двумя переменными и отсутствующей ОДР ОД Р Есть Отсутствует Замкнута Незамкнута Рис. 2. 10. Схема возможных вариантов области допустимых решений Если уравнение с тремя переменными представляет собой плоскость, то неравенство с тремя переменными a1x1 a2 x2 a3 x3 b (2. 19) представляет собой полупространство, и поэтому система неравенств с тремя переменными a11x1 a12 x2 a13 x3 b a21x1 a22 x2 a23 x3 b2 (2. 20) ……………………………… am1x1 am2 x2 am3 x3 bm определяет ОДР, которая в общем случае представляет собой многогран ник в трёхмерном пространстве. Аналогично системам неравенств с двумя переменными ОДР системы неравенств с тремя переменными может иметь те же варианты, которые показаны на рис. 2. 10. На число переменных n 3 можно распространить сделанные ранее выводы и сформулировать следующее.

Уравнение с n 3 переменными представляет собой гиперплоскость в n –мерном пространстве. Неравенство с n 3 переменными представляет собой полупространство в n –мерном пространстве. ОДР системы m нера венств с n переменными представляет собой многогранник в n –мерном пространстве. При этом ОДР для любого значения n могут иметь все ва рианты, приведённые на рис. 2. 10.

Таким образом, если задана система неравенств, то мерность про странства, в котором может быть представлена ОДР, равна числу перемен ных, входящих в неравенства, и не зависит от числа неравенств, входящих в эту систему.

Система m линейных неравенств с n переменными в общем виде записывается так:

a11x1 a12 x2 a1 j x j a1n xn b a21x1 a22 x2 a2 j x j a2n xn b …………………………………………………. (2. 21) ai1x1 ai 2 x2 aij x j ain xn bi ………………………………………………….

am1x1 am2 x2 amj x j amn xn bm или сокращённо n a1 j x j b j n a2 j x j b j ………………. (2. 22) n aij x j bi j ……………….

n amj x j bm j или ещё короче n aij x j bi, i 1, m, (2. 23) j где i – номер неравенства;

j – номер переменной. i 1, m показывает, что i поочерёдно принимает все целые значения от 1 до m, т. е. система включает m неравенств, в каждом из которых имеется n переменных.

2. 3. Графическое решение задач оптимизации Используя приведённый выше материал, рассмотрим решение си стемы, к которой свелась простейшая задача (2. 7).

Перепишем ограничения и граничные условия:

x1 x2 4,42 x 2,77 x2 x1 x2 0.

ОДР этой системы неравенств показана на рис. 2. 11. Любая точка, принадлежащая ОДР, имеет такие значения x1 и x2, которые удовлетво ряют всем неравенствам. Задача линейного программирования (ЛП) за ключается в том, чтобы из всех точек ОДР найти такую, в которой целевая функция приобретает оптимальное значение. Для нахождения такой точки o целевую функцию C 2100 x1 2570 x2 перепишем в виде x2 0,000389C o 0,817 x1.

Это уравнение прямой с угловым коэффициентом, где угловой ко k tg 0,817, 140o 45, эффициент а свободный член 0,000389C o.

Проведём линию равных значений целевой функции с произвольным значением C o.

Очевидно, что значениями x1 и x2, удовлетворяющими ограниче ниям и придающими целевой функции минимальное значение, будут ко ординаты такой точки, которая, во-первых, находится в ОДР, во-вторых, расположена на линии равных значений целевой функции, соответствую щей её минимальному значению. Это будет точка C, так как дальнейшее уменьшение C o приведёт к тому, что линия равных значений не будет проходить через ОДР. Координаты точки C есть искомые оптимальные значения переменных. Координаты точки C могут быть непосредственно измерены или найдены решением системы 4,42 x x1 x2 344.

Рис. 2. 11. Графическое решение задачи линейного программирования При этом суммарные затраты будут минимальными и составят:


minC o 2100 278 2700 66 762000 р.

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

Следует отметить, что, когда ОДР незамкнута, возможны случаи не ограниченности целевой функции. На рис. 2. 12 целевая функция не огра ничена сверху, и значения её могут быть какими угодно большими.

Рис. 2. 12. Неограниченность целевой функции Возможны и альтернативные решения, когда угол наклона линии равных значений целевой функции совпадает с углом наклона одного из ограничений. На рис. 2. 13 оптимальным решением, соответствующим максимальному значению целевой функции, будут координаты не только вершин B и C, но и координаты любой точки из множества точек, при надлежащих стороне BC многоугольника ОДР.

Рис. 2. 13. Наличие альтернативного решения задачи Возможные варианты решения задачи линейного программирования приведены на схеме (рис. 2. 14).

Оптимальное решение Не существует Существует Неограниченная Отсутствует Альтерна Единственное целевая функция ОДР тивное Сверху Снизу Рис. 2. 14. Возможные варианты наличия оптимального решения Итак, графическое решение задачи линейного программирования рассматривалось в двухмерном пространстве при наличии ограничений типа неравенств, обусловливающих ОДР.

Возможно решение и при ограничениях типа равенств, если общее количество неизвестных больше количества равенств ( N m ). Решение задачи будет иметь место в k –мерном пространстве ( k N m ). При этом m неизвестных должны быть выражены через остальные k. Если k 2, то задача решается графически. При этом область допустимых решений для системы равенств вырождается в ломаную замкнутую или нет линию, яв ляющуюся границей многоугольника. Если N m, то система ограниче ний является избыточной и не имеет единственного решения. Если N m, ОДР превращается в точку. Об оптимизации говорить не приходится, а за дача независимо от вида целевой функции имеет единственное решение.

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

М е р н о с т ь п р о с т р а н с т в а. Мерность пространства k при ограничениях-неравенствах равна числу переменных, т. е. k n, а при ограничениях-уравнениях k N m.

Если k 3, то распространяя выводы, сделанные для случая k 2, можно сформулировать следующее: 1) в трёхмерном пространстве ОДР представляет собой многогранник;

2) каждой плоскости многогранника соответствует значение одной переменной, равное нулю;

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

каждой вершине ОДР соответствуют значения трёх переменных, равные нулю;

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

4) оптимальным решением являются координаты вер шины ОДР, в которой целевая функция приобретает оптимальное значе ние.

Если мерность задачи k 3, то наглядная геометрическая интерпре тация, естественно, отсутствует. Вместо трёхмерного пространства реше ние задачи будет рассматриваться в k –мерном гиперпространстве. При этом выводы для случая k 3 можно распространить и на случай k 3, а именно: 1) ОДР представляет собой многогранник в k –мерном гиперпро странстве;

2) каждой вершине ОДР соответствуют k переменных, равных нулю;

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

4) оптимальным решением являются координаты такой вершины ОДР, в которой целевая функция приобретает оптимальное значение.

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

Задачи линейного программирования, в которых на переменные накладывается требование целочисленности, называются задачами дис кретного или целочисленного программирования (рис. 2. 15).

Рис. 2. 15. Целочисленное решение задачи линейного программирования В задачах целочисленного программирования решение может быть только в узле координатной решётки, лежащей внутри ОДР. Поэтому, если графическое решение без учёта целочисленности имеет вид на рис. 2. 15, где максимуму целевой функции соответствуют координаты точки C, т. е.

x1 3,5;

x2 1,5, то данные значения нельзя считать целочисленными ре шениями. Целочисленным решением будет x1 2;

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

Н е л и н е й н о с т ь. Могут быть нелинейными ограничения при линейной целевой функции (см. рис. 2. 16, а), нелинейная функция при ли нейных ограничениях (см. рис. 2. 16, б), нелинейными целевая функция и ограничения (см. рис. 2. 16, в). Линия равных значений целевой функции может касаться ОДР не только в вершине, что существенно усложняет ре шение задач и требует применения методов нелинейного программирова ния.

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

Рис. 2. 16. Возможные варианты нелинейности задачи 2. 5. Формы записи задач линейного программирования Наиболее общая форма записи задачи линейного программирования имеет вид:

L Cо С1x1 Cn xn max(min) (1) Cjxj a11x1 a1n xn b1 a1 j x j (2) a p1x1 a pj x j a pn xn b p a( p1)1x1 a(p1) j x j a(p1) n xn b p (3) aqn xn bn aq1x1 aqj x j (2. 24) a(q1)1x1 a(q1) j x j a(q1) n xn bq (4) am1x1 amj x j amn xn bn d1 x1 D d j xj Dj (5) d n xn Dn Задача линейного программирования включает: целевую функцию (1), которую следует максимизировать или минимизировать, ограничения, записанные в виде равенств (2), неравенств со знаком “ ” (3), неравенств со знаком “ “ (4), которые надо удовлетворить, граничные условия (5), которые показывают предельно допустимые минимальные ( d j ) и макси мальные ( D j ) значения переменных.

Из анализа существующих форм записи задач ЛП следуют следую щие примечания:

– наиболее распространённым видом граничных условий в задачах ЛП является требование неотрицательности переменных, которое записы вается в виде x j 0, j 1, n ;

– ограничения (4) задачи могут быть приведены к виду (3) умноже нием обеих частей неравенств на 1.

Сокращённая форма записи задачи ЛП с учётом приведённых заме чаний имеет вид n C j x j max(min) L Co j aij x j bi, i 1, p (2. 25) aij x j bi, i p 1, m x j 0, j 1, n Такая форма записи задачи ЛП называется смешанной. Она характе ризуется тем, что часть ограничений задачи ЛП задана в виде равенств, а другая часть – в виде неравенств.

Если все ограничения задачи заданы в виде неравенств, причём все ограничения приведены к виду "", то такая форма записи называется симметричной:

n C j x j max(min) L Co j aij x j bi, i p 1, m (2. 26) x j 0, j 1, n Если все ограничения задачи ЛП заданы в виде линейных уравнений, то такая форма записи называется канонической:

n C j x j max(min) L Co j aij x j bi, i 1, p (2. 27) x j 0, j 1, n При формировании ограничений в задачах ЛП следует обратить внимание на то, чтобы уравнения, входящие в систему ограничений, были бы линейно независимыми, так как они определяют мерность пространства и результаты решения. Линейно зависимыми называются такие уравнения, которые получаются в результате умножения или деления уравнения на одно и то же число, а также сложения или вычитания уравнений.

Например, в системе линейных уравнений 3x1 4 x2 2 x1 x2 5 x1 3x2 последнее уравнение получено сложением первых двух и, следовательно, является линейно зависимым и никакой новой информации не несёт.

2. 6. Понятие о симплекс-методе линейного программирования 2. 6. 1. Методы решения задач линейного программирования Решение задач ЛП может быть осуществлено с помощью ряда мето дов, которые подразделяются на следующие группы:

– универсальные методы, примером которых могут служить сим плекс-метод, метод разрешающих множителей Л. В. Канторовича и др. [7];

– специальные методы, применяемые для решения отдельных клас сов задач. Они проще, но пригодны не для всех задач;

– приближённые методы, отличающиеся простотой и удобством ис пользования, особенно при ручном счёте. Это индексный метод, метод ап проксимации Фогеля и др. [1].

В настоящее время наибольшее распространение получил симплекс метод, предложенный Джоном Данцигом в 1947 г. [1] и имеющий ряд мо дификаций. Ниже будет рассмотрен симплекс-метод в табличной модифи кации. Для реализации на ЭВМ в зависимости от специфики задач могут применяться и другие модификации.

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


2. 6. 2. Запись задачи линейного программирования в стандартной форме Симплекс-метод обеспечивает решение задач ЛП, сформулирован ных в канонической форме записи, т. е. в том случае, когда все ограниче ния представляют собой уравнения. Если же в результате формализации задачи ограничения имеют вид неравенств, то необходимо от неравенств перейти к уравнениям. Такой переход от неравенств к уравнениям осу ществляется следующим образом.

Пусть в результате формализации задачи составлена система нера венств a11x1 a12 x2 a1n xn b a21x1 a22 x2 a2n xn b..........

..........

..........

..... (2. 28) am1x1 am2 x2 amn xn bm x j 0, j 1, n Переменные x1, x2,, xn, входящие в начальную формализованную задачу, называют основными. Для перехода от системы неравенств к си стеме уравнений вводят в каждое неравенство по одной дополнительной неотрицательной переменной y1, y2,, ym. Тогда a11x1 a12 x2 a1n xn y1 b a21x1 a22 x2 a2n xn y2 b (2. 29) am1x1 am2 x2 amn xn ym bm x j 0, j 1, n;

yi 0, i 1, m.

Для системы уравнений характерно следующее:

– система включает N переменных, причём N n m, где n и m – соответственно число основных и дополнительных переменных;

– все переменные неотрицательны.

Система уравнений в краткой форме записи имеет вид aij x j yi bi x j 0, j 1, n;

yi 0, i 1, m. (2. 30) Каноническая форма записи является исходной для решения задачи ЛП симплекс-методом, но она должна быть преобразована. Так, все пере менные задачи должны быть разделены на б а з и с н ы е, число которых равно m, и с в о б о д н ы е, число которых равно k, причём базисные пе ременные и целевая функция должны быть выражены через свободные.

При этом не следует смешивать свободные переменные с основными, а ба зисные с дополнительными.

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

Мерность пространства такой задачи равна k N m, где N n m – число основных и дополнительных переменных в уравнениях;

m – чис ло ограничений. Следовательно, k n m m n. Поэтому, приняв m дополнительных переменных за базисные и выразив их через k n основ ных переменных, получим первое базисное решение. В этом базисном ре шении все основные переменные являются свободными и равны нулю, т. к.

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

Рассмотрим составление стандартной таблицы.

Дана задача ЛП, записанная в симметричной форме, имеющая три основные переменные ( n 3 ) и четыре ограничения ( m 4 ):

L C0 C1x1 C2 x2 C3 x3 max a11x1 a12 x2 a13 x3 b a21x1 a22 x2 a23 x3 b2 (2. 31) a31x1 a32 x2 a33 x3 b a41x1 a42 x2 a43 x3 b x j 0, j 1,3.

Введём в задачу дополнительные переменные y1, y2, y3, y4 и от не равенств перейдём к уравнениям:

a11x1 a12 x2 a13 x3 y1 b a21x1 a22 x2 a23 x3 y2 b a31x1 a32 x2 a33 x3 y3 b3 (2. 32) a41x1 a42 x2 a43 x3 y4 b x j 0, j 1,3;

yi 0, i 1,4.

В данной системе N n m 3 4 7;

k N m 3.

Примем n k 3 основных переменных свободными и выразим че рез них m 4 дополнительных переменных y i, которые станут базисными.

Перепишем систему в виде y1 b1 (a11x1 a12 x2 a13 x3 ) y2 b2 (a21x1 a22 x2 a23 x3 ) (2. 33) y3 b3 (a31x1 a32 x2 a33 x3 ) y4 b4 (a41x1 a42 x2 a43 x3 ).

Форма записи (2. 33) характеризуется следующим: 1) свободный член стоит на первом месте;

2) все переменные заключены в скобки, перед которыми вынесен знак “минус”;

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

В аналогичной форме запишем целевую функцию L C0 (C1x1 C2 x2 C3 x3 ) max. (2. 34) Окончательно получаем систему L C0 (C1x1 C2 x2 C3 x3 ) max y1 b1 (a11x1 a12 x2 a13 x3 ) y2 b2 (a21x1 a22 x2 a23 x3 ) (2. 35) y3 b3 (a31x1 a32 x2 a33 x3 ) y4 b4 (a41x1 a42 x2 a43 x3 ) x j 0, j 1,3 ;

yi 0, i 1,4.

Эта форма называется стандартной.

В такой форме переменные, заключённые в скобках ( x1, x2, x3 ), яв ляются свободными, а стоящие в левых частях уравнений ( y1, y2, y3, y4 ) – базисными. Для сокращения записи стандартную форму принято записы вать в виде таблицы коэффициентов, называемой стандартной таблицей (табл. 2. 1).

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

Рассмотрим пример записи задачи в стандартной форме:

L 2 x1 2 x2 x3 min x1 x2 x3 x3 2 x x1 x2 2 x2 x3 x j 0, j 1,3.

Таблица 2. Стандартная таблица симплекс-метода Свободный x x x член 1 C C1 C C L y1 b1 a11 a12 a b2 a21 a22 a y y3 b3 a31 a32 a y4 b4 a41 a42 a Приведём ограничения к симметричной форме, в первом и втором ограничениях поменяем знак неравенства на противоположный:

L 2 x1 2 x2 x3 min x1 x2 x3 2 x1 x3 x1 x2 2 x2 x3 x j 0, j 1,3.

Введём дополнительные переменные:

L 2 x1 2 x2 x3 min x1 x2 x3 y1 2 x1 x3 y2 x1 x2 y3 2 x2 x3 y4 x j 0, j 1,3;

yi 0, i 1,4.

Перепишем условия в стандартной форме:

L 0 (2 x1 2 x2 x3 ) min y1 1 ( x1 x2 x3 ) y2 5 (2 x1 0 x2 x3 ) y3 2 ( x1 x2 0 x3 ) y4 2 ( 0 x1 2 x2 x3 ) x j 0, j 1,3;

yi 0, i 1,4.

Представим условия в виде стандартной таблицы (табл. 2. 2).

Таблица 2. Стандартная таблица для симплекс-метода x1 x2 x Свободный член 2 L 1 y1 5 2 1` y2 y3 1 2 y4 2 2 Представление задачи ЛП в виде стандартной таблицы позволяет выявить несовместность ограничений и неограниченность целевой функ ции.

Отсутствие ОДР, т. е. несовместность ограничений, определяется на каждой итерации поиска опорного решения с помощью признака 1.

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

Несовместность ограничений по табл. 2. 2 не выявлена.

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

П р и з н а к 2 а. Целевая функция будет неограниченна снизу (т. е.

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

П р и з н а к 2 б. Целевая функция будет неограниченна сверху (т. е.

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

Неограниченность целевой функции по приведённой таблице (табл.

2. 2) не выявлена. Решение следует продолжить.

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

2. 6. 3. Нахождение опорного решения Опорным решением являются координаты любой вершины ОДР.

При этом в любой вершине ОДР k переменных равны нулю, а остальные m переменных – неотрицательны. Исходя из этого, можно установить при знак опорного решения. Если в стандартной таблице (см. табл. 2. 1) поло жить, что все n 3 свободных переменных x1, x2, x3 равны нулю, то m базисных переменных будут равны свободным членам y1 b1;

y2 b2 ;

y3 b3 ;

y4 b4. Поскольку в опорном решении k пере менных должны быть равны нулю, а m должны быть неотрицательны, то, очевидно, что решение будет опорным, если все свободные члены будут неотрицательны: bi 0, i 1,4.

П р и з н а к 3. Решение будет опорным, если в стандартной таблице все свободные члены неотрицательны. В примере (см. табл. 2. 2) в строке y свободный член b 5, следовательно, y 5, и решение не явля 2 ется опорным.

Если первое решение, в котором все основные переменные ( x, x,, x n ) являются свободными, а все дополнительные 1 ( y, y,, y m ) – базисными, не является опорным, следует произвести 1 обмен переменных. Идея обмена переменных заключается в следующем.

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

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

Идею обмена переменных рассмотрим на примере, записанном в стандартной таблице (см. табл. 2. 1). Допустим, необходимо обменить x на y, т. е. x из свободных перевести в базисные, а y из базисных – в 3 2 свободные. Такая операция обозначается в виде x y. В рассматрива 2 емом примере y b (a x a x a (2. 36) x) 3 3 31 1 32 2 33 поменяем местами x на y. Тогда 2 x b (a x y a (2. 37) a x) 32 2 3 31 1 3 33 и окончательно a b a x 3 31 x y 33 x.

(2. 38) a 2a 1a 3a 32 32 32 При этом, если выражение (2. 38) подставить вместо x в целевую функ цию и в остальные уравнения (см. табл. 2. 1), привести подобные члены, то вместо переменной x будет переменная y, а уравнения и целевая 2 функция изменятся следующим образом:

a b aa aa a y1 b1 12 3 a11 12 31 x1 12 y3 a13 12 33 x3, (2. 39) a32 a32 a a C2 b C2 a31 C L C0 C1 x1 y a32 a a C2 a C3 x3. (2. 40) a После определения опорного решения целевая функция и ограниче ния будут выражены через соответствующие свободные переменные, и на основе полученной стандартной таблицы можно переходить к определе нию оптимального решения.

Чтобы облегчить работу по обмену переменных, составлен алгоритм, в основе которого лежит вышеизложенный метод модифицированных Жордановых исключений [6]. Алгоритм обмена переменных можно пред ставить в виде пяти этапов: 1) записать условие задачи в виде стандартной таблицы;

2) выбрать разрешающий элемент;

3) заполнить нижние правые части ячеек стандартной таблицы;

4) перейти к следующей стандартной таблице;

5) проверить соответствие признакам.

Рассмотрим алгоритм на примере поиска опорного решения.

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

Таблица 2. Стандартная таблица первого шага поиска опорного решения y Свободный x1 x2 x член 0 2 L 4 1 1 y 2 5 2 y 4 2 y 2 2 2 x1 y 0 0 2 э т а п. Выбор разрешающего элемента при отыскании опорного решения производится следующим образом.

А. Выбрать разрешающий столбец. В строке, содержащей отрица тельный свободный член, выбрать отрицательный элемент. Столбец, со держащий этот отрицательный элемент, принять в качестве разрешающего и выделить двумя чертами (табл. 2. 3). Если в строке, содержащей отрица тельный свободный член, нет отрицательного элемента, значит не выпол няется признак 1, т. е. ограничения являются несовместными. Если в стро ке несколько отрицательных элементов, то лучше брать столбец с большим по абсолютной величине отрицательным элементом (2. 39).

Б. Выбрать разрешающую строку. В разрешающем столбце рас сматривают все элементы, имеющие знак, одинаковый со свободным чле ном той же строки. В качестве разрешающей строки выбирают ту, для ко торой отношение свободного члена к элементу разрешающего столбца ми нимально. По табл. 2. b 5 min i min, min2,5;

2 2, im a 2 ij что соответствует строке с y3. Принятую i -ю строку (по табл. 2. 3 i 3 ) выделяют двумя чертами.

В. Выделить разрешающий элемент. Разрешающим элементом aij является элемент, принадлежащий j -му разрешающему столбцу и i -й разрешающей строке. По табл. 2. 3 aij 1. Разрешающий элемент выделя ют. У разрешающих строки и столбца ставят знаки обмена x j yi (см. табл. 2. 3).

3-й э т а п. Нижнюю правую часть ячейки разрешающего элемента заполняют величиной 1/ aij ;

нижние правые части ячеек разрешающей строки – элементами, стоящими в верхних левых частях каждой ячейки, умноженными на ;

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

4-й э т а п. Составляют следующую стандартную таблицу (табл. 2.

4), в которой меняют местами обмениваемые переменные x j и yi.

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

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

Таблица 2. Стандартная таблица второго шага поиска опорного решения y Свободный y3 x2 x член 4 2 4 L 1 2 2 1 3 y 1 2 2 1 - 2 x3 y 2 2 2 1 x 0 0 0 2 2 y 1 2 2 Так как свободный член в строке y2 (см. табл. 2. 4) равен 1, при знак 3 опорного решения не удовлетворяется. Следовательно, это решение опорным не является. Однако, абсолютное значение отрицательного сво бодного члена стало меньше. Значит, найденное решение ближе к опорно му, чем первое. Проверим отсутствие ОДР по признаку 1. В строке y2 с отрицательным свободным членом есть отрицательный элемент 1. Таким образом, отсутствие ОДР не установлено. Проверим неограниченность це левой функции. В данном примере находится min L. Согласно признаку 2а в столбцах, имеющих в строке целевой функции положительные эле менты (по табл. 2. 4 – все элементы положительные), должны быть поло жительные элементы (положительные элементы есть в каждом столбце).

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

Полученное решение (см. табл. 2. 5) является опорным, т. к. все сво бодные члены неотрицательны. Поскольку свободные переменные y3, x2, y2 равны нулю, то ненулевые координаты вершины, являющиеся опорным решением, равны y1 2, x3 1, x1 2, y1 1. При этом целевая функция L 3. По признаку 2а неограниченность целевой функции не вы явлена. Следовательно, необходимо перейти к определению оптимального решения.

Таблица 2. Стандартная таблица третьего шага поиска опорного решения и первого шага поиска оптимального решения y Свободный y3 x2 y член 3 4 L 2 2 2 y 3/ 3/ 2 6 3/ 2 2 x 1 4 2 1 x 1/ 2 1/ 1/ 1 4 y y 1/ 2 1/ 2 1/ 2. 6. 4. Определение оптимального решения Оптимальным решением являются координаты такой вершины ОДР, в которой целевая функция приобретает оптимальное (т. е. максимальное или минимальное) значение. Необходимо сформулировать признак опти мальности решения. Рассмотрим целевую функцию в стандартной форме:

L C0 (C1x1 C2 x2 C j x j Cn xn ) (2. 41) Для упрощения принимаем j 1. Тогда целевая функция L C0 (C1x1). (2. 42) Возможны следующие варианты исходных ситуаций:

1-й в а р и а н т.

L C0 (C1x1 ) max. (2. 43) Очевидно, что при x1 0 L C0.

Если C1 0, то при увеличении x1, т. е. при переводе её из состава свободных в базисные, целевая функция будет уменьшаться. Уменьшать x1 нельзя, т. к. она – свободная переменная, и нарушится условие x1 0.

Следовательно, полученное решение оптимально.

Если C1 0, то переводя x1 из свободной в базисную и увеличивая её (т. е. переходя от одного опорного решения к другому), будем увеличи вать и целевую функцию.

Приведённые рассуждения можно распространить и на все другие C j, j 2, n.

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

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

2-й в а р и а н т.

L C0 (C1x1) min (2. 44) Так же, как и в предыдущем случае, при x1 0 L C0.

Если C1 0, то при увеличении x1, т. е. при переводе её из состава свободных в базисные, целевая функция будет уменьшаться. Если C1 0, то любое значение x1 приведёт только к увеличению L. Таким образом, при C1 0 решение является оптимальным. Все рассуждения можно распространить на все x j, j 1, n.

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

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

3-й в а р и а н т.

L C0 (C1x1) max(min) (2. 45) Если C1 0, то L C0. Этот случай является признаком наличия альтернативного, т. е. не единственного оптимального решения. Его можно сформулировать так.

П р и з н а к 4 в. Задача ЛП имеет альтернативные, т. е. не един ственные значения x j, придающие целевой функции оптимальное значе ние в случае, когда среди C j есть нулевые элементы. При этом макси мальное или минимальное значение целевой функции определяется знака ми остальных ненулевых коэффициентов C j в строке целевой функции (без учёта свободного члена).

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

Последняя таблица (табл. 2. 6) удовлетворяет признаку 4б, так как все коэффициенты при переменных в строке целевой функции отрицатель ны. Следовательно, целевая функция имеет минимальное значение, равное min L 1. При этом переменные равны:

x1 3 / 2;

x2 0;

x3 2;

y1 1/ 2;

y2 0;

y3 1/ 2;

y4 0.

Если сравним значение целевой функции min L 1 со значением це левой функции при опорном решении, когда L 3, то увидим, что значе ние её в оптимальном решении меньше, чем в опорном.

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

Таблица 2. Стандартная таблица оптимального решения задачи y4 x2 y Свободный член 2 L 1/ y1 3/ 2 1/ x3 2 1 x1 1/ 2 1/ 1/ y3 1/ 2 1/ 2 1/ 2. 6. 5. Выбор первого базиса В том случае, когда задача ЛП задана в симметричной форме, т. е.

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



Pages:   || 2 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.