Применение методов теории графов и линейного программирования для решения производственных и технологических задач: Методические указания

Министерство образования Российской Федерации Ульяновский государственный технический университет

Н.И. Веткасов, Ю.В. Псигин

ПРИМЕНЕНИЕ МЕТОДОВ ТЕОРИИ ГРАФОВ И ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ПРОИЗВОДСТВЕННЫХ И ТЕХНОЛОГИЧЕСКИХ ЗАДАЧ

Методические указания к практическим занятиям по дисциплине "Основы математического моделирования производственных и технологических процессов" для студентов всех форм обучения специальности 1201 - Технология машиностроения

Ульяновск 2001

УДК 621.391.01(076) ББК34.5 я? В 39 Рецензент - канд. техн. наук, доцент А.Р. Гисметуллин Редактор - д-р техн. наук, профессор Л.В. Худобин Одобрено секцией методических пособий научно-методического совета университета Веткасов Н.И., Псигин Ю.В. В 39 Применение методов Теории графов и линейного программирования для решения производственных и технологических задач: Методические указания. Ульяновск: УлГТУ, 2001. 36 с. Методические указания составлены в соответствии с типовой программой учебной дисциплины «Основы математического моделирования», а также рабочей программой дисциплины «Основы математического моделирования производственных и технологических процессов» для студентов всех форм обучения специальности 1201 - Технология машиностроения. Изложены основные положения по применению теории графов и линейного программирования для решения технологических задач. Представлены варианты заданий для выполнения практических занятий. Дана методика решения задач линейного программирования с применением средств электронно-вычислительной техники. Методические указания предназначены для использования при проведении практических занятий и самостоятельной работе студентов.

УДК 621.391.01(076) * ББК 34.5 я7 Учебное издание ВЕТКАСОВ Николай Иванович ПСИГИН Юрий Витальевич Применение методов теории графов и линейного программирования для решения производственных и технологических задач Методические указания Редактор Н.А. Евдокимова Подписано в печать 20.07.2001. Формат 60x84/16. Бумага писчая. Усл.печ.л. 2,09. Уч.-изд.л. 2,00. Тираж 200 экз. Заказ Ульяновский государственный технический университет. 432027, Ульяновск, ул. Сев. Венец, 32. Типография УлГТУ, 432027, Ульяновск, Сев. Венец, 32.

© Ульяновский государственный технический университет, 2001

35 . Данные для постановки задачи 2 Вид заготовки

Количество заготовок при раскрое, шт № способа 1 2 ai a2 bi Ь2

1 2 3 Величина отходов, см3

Cl

C2

di

d2

12. Исходные данные для выполнения практического занятия № 2 (задача 2) № варианта 1 2 3 4 5 6 7 8 9 10

,Cl

С2

ai

а2

ь,

Ь2

16 4 8 6 4 6 7 12 3 10

18 5 9 12 5 8 6 14 4 12

12 5 12 12 7 8 5 8 4 14

10 10 14 3 2 1 11 14 13 14 8 6 9 9 3 10 13 8 6 4 3 6 7 5 6 5 7 16 10 .11

di

d2

8 7 10 4 5 6 2 10 4 10

10 6 11 6 9 8 3 12 6 12

№ вари анта 11 12 13 14 15 16 17 18 19 4

ai

а2

ь,

Ь2 ci

13 8 3 10 12 6 4 8 6

11 6 5 8 10 3 6 10 9 3

8 6 7 9 10 5 6 9 5 2

10 5 6 7* 8 4 .4 10 7 4

6

С2

5 10 10 9 9 10 14 12 8 10 5 8 12 14 8 6 4 6

di

d2

9 11 4 6 10 12 12 6 11 8

7 12 3 4 14 10 8 9 12 6

2.7.КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Приведите запись задачи линейного программирования в стандартной форме. 2. В чем заключается суть задачи линейного программирования? 3. Что такое "базисная" и "свободная" переменные? 4. Перечислите основные этапы решения задачи линейного программирования симплекс-методом.

4 ВВЕДЕНИЕ

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

1. ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ РАЗМЕРНОГО АНАЛИЗА ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА

. 1. ОБЩИЕ ПО Л ОЖЕНИЯ

При выполнении курсовой работы по технологии машиностроения каждый студент обязательно проводит анализ точности механической обработки заготовки - размерный анализ, позволяющий обоснованно назначать операционные размеры, определить минимально необходимые операционные и промежуточные припуски, установить предпочтительную последовательность выполнения переходов, установов и операций, провести сравнительную оценку различных вариантов технологического процесса. Существует много методов анализа технологических процессов механической обработки. Один из них - размерный анализ, выполненный по методике Челябинского технического университета [1, 2], с помощью которого решают прямые (проектные) и обратные (проверочные) задачи. В первом случае определяют номинальные значения промежуточных операционных размеров и размеров заготовки с учетом технических требований, предъяв-

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

1.2. ВЫЯВЛЕНИЕ ТЕХНОЛОГИЧЕСКИХ РАЗМЕРНЫХ ЦЕПЕЙ ПРИ ПОМОЩИ ТЕОРИИ ГРАФОВ

Деталь в процессе ее изготовления можно рассматривать как геометрическую структуру, состоящую из множества поверхностей и связей (размеров) между ними. Такую структуру целесообразно изучать при помощи графов. Если принять поверхности заготовки и детали за вершины, а связи между ними за ребра, то чертеж детали с конструкторским^ и технологическими размерами можно представить в виде двух деревьев [3]. Дерево с конструкторскими размерами (связями) и с размерами припусков на обработку называется исходным, а дерево с технологическими размерами - производным или технологическим. При совмещении исходного и производного деревьев получается совмещенный граф. В таком графе в закодированной форме представлена геометрическая структура технологического процесса обработки заготовки. Можно, не прибегая к помощи чертежа, а пользуясь информацией графа, производить все расчеты [4, 5]. Любой замкнутый контур на совмещенном графе образует технологическую размерную цепь. Ребро исходного дерева является замыкающим звеном, а ребра производного дерева - составляющими звеньями. В терминах теории графов [6] размерная цепь - это путь в производном дереве, заданный ребрами исходного дерева. При известных длинах ребер производного дерева в данной цепи можно найти длину пути, т.е. размер или допуск замыкающего звена. В каждой размерной цепи одно ребро должно быть ребром исходного дерева, а остальные - производного дерева. Для построения графа размерных цепей необходимо предварительно, на основе маршрутного технологического процесса, составить его размерную схему.

6 В представленном в табл. 1 примере рассматривается линейная размерная цепь, образующаяся при обработке торцов и буртиков вала (рис. 1, б) в крупносерийном производстве и включающая в качестве звеньев технологические размеры 84, размеры заготовки Зь конструкторские размеры AJ и размеры припусков Zj (рис. 2). При реализации технологического процесса изготовления детали заготовку неоднократно представляют в станочном приспособлении. Чтобы четко определять положение заготовки на конкретной операции, необходимо указать на эскизе характерные (обрабатываемые и базовые) поверхности заготовки. При этом нет необходимости указывать все поверхности. На эскизе заготовки (рис. 1, а) представлены размеры заготовки Зь 32 и Зз, а также размеры припусков Z2, Z^ Z5, Ze, Z7, Zg. Индекс размеру припуска присваивают по номеру той поверхности, которая образуется в результате его съема. Конструкторские (чертежные) размеры детали представлены на ее эскизе (рис. 1, б). На 5 операции фрезеруют торцы 2 и 9, при этом снимают припуски Z2, Zg и выдерживают линейный размер Ф (расстояние между торцами 2 и 3) и линейный размер ©('расстояние между торцами 2 и 9). Технологические раз меры Ф и ® обозначим Si и S2 (см. рис. 2) (табл. 1). Заготовку на 5 операции устанавливают в тиски самоцентрирующие с опорой на поверхность 3 заго товки. На 5 операции получают также центровые отверстия, которые будут использованы на последующих операциях в качестве двойной направляющей технологической базы. ^ На 10 операции протачивают поверхности 11 и 13, выдерживая размеры (D и (D и торец 7. Заготовку устанавливают в центрах с упором в торец 2 (технологическая опорная база). На этой операции снимают припуск Zj и выдерживают технологический размер Ф (расстояние между торцами 2 и 7), обозначенный 83. Здесь же протачивают окончательно торец 6, снимая припуск Z7 между поверхностью 6 и 7, и выдерживают технологический размер 0, связывающий торцы 2 и 6 и обозначенный 84. На 15 операции протачивают поверхность 16, выдерживая размер (D, и торец 4, снимая припуск Z$ и выдерживая технологический размер Ф, обозначенный S5 и связывающий торцы 6 и 4. На этой же операции протачивают окончательно поверхность 5. Снимают припуск Zs между поверхностями 4 и 5, выдерживают технологический размер Ф, связывающий торцы 6 и 5 и обозначенный 8бРазмеры заготовки и технологические размеры из таблицы маршрутного технологического процесса наносят на размерную схему (см. рис. 1), причем конец размерной линии, соответствующий базовой поверхности,помечают точкой, а конец, соответствующий обрабатываемой поверхности;-стрелкой. Затем приступают к построению графа размерной цепи, придерживаясь следующего порядка (рис. 3).

**г

Если же искомый является увеличивающим звеном, то

оазмео

Определив величину Ах тах или Ах min, на размер Ах устанавливают до-туск TAX в зависимости от назначения технологической операции (перехода) предварительная или окончательная обработка. В первом случае обычно 1азначают допуск по 12 - 14 квалитету, во втором - по 9 - 11 квалитету. Предельные отклонения назначают по h, JT/2 или Н (ГОСТ25347-82), ю величине установленного допуска TAX и по его расположению относи-гельно Ах (h, Н или JT/2) определяют номинальный размер Ах по одной из следующих формул: •Т'" у

(4)

' '• (5) ^де ESAX и Е1АХ - соответственно верхнее и нижнее предельные отклонения \\ данного размера. Далее определяют номинальный размер припуска 7Д и его наибольший тредельный размер 7д тах. Для этого составляют исходное уравнение размер-дой цепи относительно ZA с указанием для всех составляющих звеньев предельных отклонений. На основании этого уравнения суммируют номинальные размеры и предельные отклонения раздельно для увеличивающих и уменьшающих звеньев. По разности сумм номинальных размеров увеличивающих и уменьшающих звеньев определяют размер припуска

(6) 1 по разности суммы предельных отклонений предельные отклонения раз мера припуска

^ if

я, наконец, максимальное величины припуска 7Д тах,

значение

.4. 1РИМЕР РАСЧЕТА ТЕХНОЛОГИЧЕСКИХ РАЗМЕРНЫХ ЦЕПЕЙ

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

Маршрутный технологический процесс обработки заготовки вала Технологические эскизы

операции

Наименование и содержание операции

1

2 3 Фрезерно-центровальная 1. Фрезеровать поверхности 2 и 9, выдерживая размеры (7) и (J). 2. Центровать 2 отв. 17, выдерживая размеры (7)и(7).

5

10

Токарная автоматная 1 .Точить поверхности 1 1 и 13 окончательно, поверхность 7 предварительно, выдерживая размеры

2. Точить поверхность 6 окончательно, выдерживая размер (j\

15

Токарная автоматная 1 . Точить поверхность 1 6 окончательно, поверхность 4 предварительно, выдерживая размеры \J^) и \2j. -

1

2

3

2. Точить поверхность 5 окончательно, выдерживая размер (з)

^

-"'

10 Сначала строят производное, затем исходное дерево и затем совмещают их. При совмещении получается граф технологических размерных цепей. Вершины (поверхности) обозначают кружочками, внутри которых указывают их номер. Дуги производного дерева (рис. 3, а) изображают прямыми линиями со стрелками на конце, показывающими, в какую вершину они входят. В качестве корня производного дерева выбирают вершину, к которой по размерной схеме технологического процесса не подходит ни одна стрелка (см. рис. 2). Такую вершину следует вычертить в виде двойного кружка и провести из нее те дуги, которые касаются ее своими неориентированными концами. На ориентированных концах этих дуг необходимо указать кружками вершины (поверхности), в которые они упираются своими стрелками. Из этих вершин следует провести те дуги, которые касаются их неориентированными концами, а на концах со стрелками указать вершины, в которые они входят. Этот процесс продолжают до тех пор, пока все ветви дерева не упрутся в вершины (поверхности), из которых не входит ни одна стрелка. На этом построение производного дерева заканчивается. Аналогично строят исходное дерево (рис. 3, б). Начинают его построение с расположения вершин на бумаге в том же порядке, в каком они располагались при построении производного дерева. Исходное дерево состоит из ребер, поэтому при построении можно выбрать корнем любую вершину, т.е. поверхность на чертеже готовой детали. Конструкторские размеры обозначают кривыми, а размеры припусков - волнистыми линиями. Так как исходное дерево состоит из ребер, то оно лишь указывает на то, какие вершины (поверхности) связаны между собой конструкторскими размерами, а какие размерами припусков. После построения каждого дерева проверяют правильность их построения по следующим признакам: 1. Число вершин у каждого дерева должно быть равно числу поверхностей на размерной схеме технологического процесса. 2. Число ребер (дуг) у каждого дерева должно быть одинаковым, а по значению - на одно меньше, чем вершин. 3. К каждой вершине производного дерева, кроме корневой, должна подходить только одна стрелка дуги, а к корневой вершине-ни одной. 4. Деревья не должны иметь разрывов и замкнутых контуров. После проверки деревья совмещают так, чтобы одноименные вершины совпадали. Практически два дерева отдельно можно не строить, т.е. сначала строят производное дерево, а затем на нем же - исходное. Процесс разбиения графа на отдельные деревья осуществляют для упрощения корректировки положения вершин, так как последние надо располагать так, чтобы ребра

12 и дуги совмещенного графа не пересекались. Совмещенный граф и будет графом технологических размерных цепей (рис. 3, в). Граф размерных цепей не только облегчает выявление цепей, но и позволяет обнаруживать ошибки в технологии или чертеже. Например, если при составлении производного или исходного деревьев обнаружится разрыв между вершинами или появится замкнутый контур, то это указывает в первом случае на отсутствие нужных размеров в технологии или на чертеже, а во втором - на наличие лишних размеров. Любой замкнутый контур совмещенного графа образует размерную цепь, у которой ребро исходного дерева является замыкающим звеном, а составляющие звенья представлены дугами производного дерева. Например, на рис. 3, в звенья Зь Si и Z\ образуют замкнутый контур, т.е. размерную цепь, у которой дуги 3i и Si - составляющие звенья, а ребро Zi - замыкающее звено. Замкнутый контур из звеньев А2, 84 и 8б образует новую размерную цепь с замыкающим звеном - ребром А2 и составляющими звеньями - дугами 84 и

s6.

Так как в размерной цепи только одно звено может быть замыкающим (конструкторский размер или размер припуска), то при выявлении размерных цепей по графу необходимо выбирать такие контуры, в которых бы содержалось только по одному ребру исходного дерева, а остальные звенья (дуги) принадлежали бы к производному дереву. Например, на рис. 3, в звенья Z6, Z7, 32, 81 и 84 образуют замкнутый контур, но в нем ребра Z6 и Z7 принадлежат исходному дереву, поэтому такой контур не следует использовать в качестве размерной цепи. В данном случае следует рассмотреть два контура или две размерные цепи, а именно: замкнутый контур из звеньев Z7, 32, Si и 8з и контур из звеньев Z6, 83 и 84. Точно так же цепь, состоящую из звеньев Z4, 32, Z7, S3, S4 и 85, следует разбить на две цепи, у одной из которых замыкающим звеном будет Z7, а у другой Z4. Следует помнить, что общее число размерных цепей на графе должно быть равно числу технологических размеров по размерной схеме технологического процесса. Вместе с выявлением технологических размерных цепей необходимо по графу определить также знаки составляющих звеньев по следующему правилу. Замыкающему звену присваивают знак минус и, начиная от этого звена, обходят замкнутый контур в определенном направлении. Обход цепи начинают с меньшей из вершин, связанных замыкающим звеном, Если в направлении обхода следующее звено цепи будет соединять вершину меньшего порядкового номера с вершиной большего номера, то звену присваивают знак плюс; если звено соединяет вершину большего номера с вершиной меньшего номера, то ему присваивают знак минус. Одновременно с определением знаков звеньев размерной цепи составляют расчетные управления из условия, что алгебраическая сумма всех звеньев размерной цепи, включая и

3

замыкающее, равна нулю. Затем эти уравнения преобразуют в исходные, т.е. вставленные относительно замыкающего звена. В исходном уравнении (в правой части) звенья, имеющие знак плюс, являются увеличивающими, а имеющие знак минус - уменьшающими. • Рассмотрим простановку знаков звеньев цепи, составляющей из звень-гв А2, 84, 8б (рис. 3, в). Замыкающему звену А2д присвоим знак минус. Обход контура начинаем с вершины 2. Звено 84 соединяет вершину 2 с вершиной 6, значит оно имеет знак плюс (обход от меньшего к большему номеру). Звено 5б соединяет вершину 6 с вершиной 5, поэтому оно имеет знак минус (обход от большего к меньшему номеру). Следовательно, расчетное уравнение цепи имеет вид:

Исходное уравнение образом: >

запишем следующим

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

.3. МЕТОДИКА РАСЧЕТА ТЕХНОЛОГИЧЕСКИХ РАЗМЕРНЫХ ЦЕПЕЙ

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

определяемый для последующей операции (перехода), то сначала определяют его максимальную величину ZAmin по справочным таблицам или расчетноаналитическим методом [7, 8]. Минимально необходимый припуск на обра-

14 2. Уравнения для расчета технологических размерных цепей :

ботку складывается из высоты неровностей профиля и глубины дефектного слоя, сформировавшихся на предыдущем переходе (операции), суммарного отклонения расположения и формы поверхности заготовки и погрешности установки заготовки на выполняемом переходе (операции). Максимально возможный припуск Zj max при обработке поверхности определяется расчетом технологической размерной цепи, величиной Zj min и суммой допусков, входящих в размерную цепь размеров. Определив ZAmjn, составляют исходное уравнение размерной цепи от-

носительно ZAmjn:

>

где Ainiin- наименьший предельный размер 1-го увеличивающего звена размерной цепи; Aimax- наибольший предельный размер 1-го уменьшающего звена размерной цепи; m - число звеньев в цепи; к - число увеличивающих звеньев размерной цепи. Так как в каждой технологической размерной цепи имеется только одно неизвестное составляющее звено, то задача сводится к решению уравнения (1) с одним неизвестным. Обозначим определяемый размер через Ах. Если искомый размер является уменьшающим звеном [6], то

17 Т 3 2

= 2,7 мм; ES32 = 1,8 мм; Е132 = - 0,9 мм. Тзз = 3 мм; Е83з = 2 мм; Е13з = - 1 мм. Результаты расчетов технологических размеров и размеров заготовки сведены в табл. 3. 5. ЗАДАНИЕ К ГОАКТИЧЕСКОМУ ЗАНЯТИЮ № Разработать маршрутный технологический процесс изготовления представленных на рис. 4, 5 деталей и произвести расчет технологических размерных цепей методом теории графов и теории размерных цепей. Проверить возможность обеспечения заданных на чертеже конструкторских размеров, рассчитать межоперационные припуски и операционные размеры, указанные на технологических эскизах разработанного студентом маршрутного технологического процесса, используя методы теории графов и теории размерных цепей. Исходные данные для расчета поставлены в соответствие с номером варианта студента (табл. 4). Сравнить результаты расчетов размерных цепей методами теории графов и теории размерных цепей и дать заключение о возможностях применения каждого из рассмотренных методов. 1.6. КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Какую вершину (поверхность заготовки) и почему можно использовать в качестве корня при построении производного дерева? 2. Как проверяют правильность построения производного и исходного деревьев? 3. Для чего составляют размерную схему технологического процесса? 4. В какой последовательности производят выявление и расчет технологических размерных цепей? 5. На что указывают разрывы и замкнутые контуры в производном или исходном дереве? 6. По какой схеме определяют предельные отклонения размера припуска? (Привести расчетные формулы). 7. Что такое дуга, путь, контур? В чем их отличие .от ребра, цепи, цикла? 8. Что такое дерево? (Привести пример )„ 9. По каким правилам определяют по графу знаки составляющих звеньев технологических размерных цепей? (Привести пример). 10. Из каких условий составляют расчетные уравнения? (Привести пример

Продолжение таб

Рис. 4. Эскизы деталей для выполнения практического занятия №

Рис.5. Эскизы деталей для выполнения практического занятия №

22 4. Исходные данные к практическому занятию №

2. ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 2. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ТЕХНОЛОГИЧЕСКИЙ И ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

2.1. ОБЩИЕ ПОЛОЖЕНИЯ

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

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

Или, в так называемой канонической форме, к которой можно привести все три указанных случая: ,

Требуется найти такие неотрицательные числа хд! ,п\ которые минимизируют (или максимизируют) линейную формулу:

Неотрицательность искомых чисел записывают в виде Характерной особенностью данной задачи является^о, что число уравнений меньше числа неизвестных, т.е. m < п. Суть задачи линейного программирования состоит в том, чтобы из множества допустимых решений системы (10) выбрать только одно, которое обращает в минимум линейную функцию (11). При этом допустимым решением называют любое решение системы (10) с неотрицательными значениями переменных (xi > 0).

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

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

25 Решение системы уравнений (13), в которой число переменных п больше числа уравнений т, можно найти, если n-m каких-либо переменных положить равными нулю. Тогда полученную при этом систему m уравнений с п неизвестными можно решить обычными методами алгебры. Найденное при этом решение называют базисным. Базисом называют любой набор переменных т, таких, что определитель, составленный из коэффициентов при этих переменных, не равен нулю. Эти m переменных называют базисными переменными. Остальные n-m переменных называют свободными переменными. Если принять все свободные переменные равными нулю и решить полученную систему m уравнений с п неизвестными, то получим базисное решение. Однако среди базисных решений будут такие, которые дадут отрицательные значения некоторых базисных переменных, что противоречит условию задачи, поэтому такие решения недопустимы. При нахождении минимального значения целевой функции (11) необходимо из допустимых базисных решений выбрать такое которое обращает в минимум функцию (11). В настоящее время разработаны рациональные способы перебора базисных решений, которые позволяют рассматривать не все допустимые базисные решения, а их минимальное число. Наиболее распространенными методами такого перебора являются так называемый симплекс-метод и табличный метод. \ 2.2. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВ АНИЯ Суть симплекс-метода состоит в следующем: 1. Находят какое-либо допустимое базисное решение. Его можно найти, приняв какие-либо m-n переменные за свободные, приравняв их к нулю и решив получившуюся систему уравнений. Если при этом некоторые из базисных переменных окажутся отрицательными, то нужно выбрать другие свободные переменные, т.е. перейти к новому базису. 2. Проверяют, не достигнут ли уже максимум целевой функции при найденном допустимом базисном решении. 3. Если оптимальное решение не найдено, то ищут новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение целевой функции. Проверку того, достигнут ли при найденном допустимом решении максимум целевой функции, можно сделать путем поиска нового базисного решения. Для перехода к новому базисному решению одну из свободных переменных следует сделать базисной, при этом она будет отличаться от нуля,

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

2.3. ТАБЛИЧНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

при условии

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

z/ По виду коэффициентов матрицы (см. табл. 5) легко судить, является ли найденное базисное решение допустимым и, если оно допустимо, то будет ли оно оптимальным. Действительно, замечая, что столбец коэффициентов aio (i ^ 0) представляет собой базисное решение, соответствующее базису х\ 9 ... 9 х' т9 а строчка коэффициентов aqj G ^ 0) представляет собой взятые с обратным знаком коэффициенты при свободных переменных в выражении (14), приходим к выводу, что базисное решение, соответствующее базису xj,...,x'm, допустимо, если аю > 0. Если, кроме того, aqj > 0, то это базисное решение является оптимальным. Очевидно также, что при оптимальном базисном решении коэффициент аоо дает значение q^ax . Следовательно, решение задачи линейного программирования табличным методом заключается в нахождении на первом этапе какого-либо допустимого базисного решения, которое в общем случае не является оптимальным, и преобразовании первоначальной матрицы коэффициентов с целью перехода к лучшему базисному решению.

Пример решения задачи линейного программирования табличным методом рассмотрен ниже. 2.4.ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Максимизировать функцию прибыли от производства четырех продуктов q' = 60xi + 70x2 + 120хз + 130x4, если затраты ресурсов на их изготовление заданы следующими ограничениями: Xi + х2 + х3 + х4 < 6; 4xj + 6х2 + * 10х3 + 13x4 < 100; 6xi + 5х2 + 4х3 + Зх4 < 110. Математическая модель задачи имеет следующий вид:

(16)

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

28

Очевидно, что дополнительные переменные х$, которые равны разности между располагаемым ресурсом и требуемым, представляют собой резерв по данному ресурсу. Поскольку п - m = 4, то в качестве свободных переменных можно взять любые, например, Хь Х2, Хз, Х4. Положив их равными нулю, из уравнения (17) найдем базисное решение K J = 110, которое является допустимым и при котором (18) В выражение для целевой функции (18) все свободные переменные входят со знаком "+", что свидетельствует о том, что максимум целевой функции не достигнут. Поэтому любую свободную переменную Хь Х2, Хз, Х4 можно сделать базисной переменной. Примем в качестве новой базисной переменной Xi. Для определения новой свободной переменной выразим базисные переменные х5, Хб, Х7 через свободные, приведя уравнения (17) к виду (15):

(19) Из уравнений (19) следует, что при х2 = 0, х3 = 0; Х4 = 0. Увеличение Xi приводит к уменьшению х5, х6, х7 так, что при Xi = 16 получим х5 = О, Хб = 36 > 0; х7 = 14 > 0. Таким образом, переменную х5 следует сделать новой свободной переменной, что приводит к новому базису. Для продолжения решения разрешим систему (17) относительно новых базисных переменных, приведя ее к виду

Выразим целевую функцию через новые свободные переменные: (21) Из уравнений (21) видно, что максимум целевой функции не достигнут, т.к. переменные х2, Хз, Х4 входят в уравнение (21) со знаком "+". Следова тельно, одну из свободных переменных например Хз, необходимо перевести в базисную переменную, а базисную Хб - в свободную. Новый ба зис образуют при этом переменные Разрешим уравнения (20) относительно новых базисных переменных:

29 х, 1 Х-3 —О

—Хо

л

2

1

0 - х 2 +2 - х 4 3 2 1 3

—Хл т—Х<

з

3

х? +—Хс 7

3

2

2

2 xfi,

4

Хс5+ х66; 3 6 2 1

4

5

3 6 22 х 7 = 2 6 3

5

3

6

Хг !

6

Целевая функция при этом примет следующий вид: q' = 1320 - 10х2 - 20х4 -20х5 - 10х6. (23 ) Из уравнения (23) видно, что при увеличении свободных переменных Х2, Х4, х5, Хб значение q' уменьшается. Следовательно, при данном базисе достигается максимум целевой функции и решением данной задачи будет следующий набор переменных: х2 = х4 = х5 = х6 = 0; KI = 10; х3 = 6; х7 = 26/ При этом q' = 1320. Рассмотрим решение данной задачи табличным методом. Принимая хь х2, х3, Х4 за свободные переменные, приведем систему уравнений (16) к следующему виду: q' = 0 - ( 60х -70х 2 -120х 3 30х4), х5 =16-(xj + х2 + х 3 +х4), х6 = 100-(4xj +6х 2 + 10х3 + 13х4), х7 =110-(бх1 + 5х2 +4х3 +3х4). Матрицу коэффициентов представим в виде табл. 6 с клетками достаточно крупного размера, в верхнем левом углу которых запишем коэффициенты уравнений (24). 6. Исходная матрица коэффициентов

q' Х5 Х6

0 0 960

•xi -60 60

-х2 -70 60

-х3 -120 60

-Х4

16 16 100 -64

1

1 1 6 -4

1 1

1 1 13

4 -4

ю -4

-130 60

-4

х?

110 -96

6 -6

5 -6

4 -6

3 -6

7. Преобразованная матрица коэффициентов

Поскольку в таол. 7 коэффициенты аоа, аоз и ао4 < 0„ то оптимальное юшение не найдено. Следовательно, необходимо, согласно приведенным tbiine правилам, заполнить нижние левые углы табл. 7 и перейти к новой 'абл. 8, соответствующей базису хь х3, х7. В табл. 8 коэффициенты а$ положительны, и она дает оптимальное реиение задачи, которое найдем по столбцу свободных членов: X] = 10; х3 = 6; х7 = 26; х2 = Х4 = х5 = х$ = 0; qfmax = 1320. 8. Результаты оптимального решения

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

32 скольких переменных, соотношения между которыми заданы в виде неравенств, т.е. решать задачи линейного программирования. Кроме того, решение задачи на ЭВМ способствует закреплению навыков работы на компьютере и позволяет студенту проверить правильность решения задачи вручную табличным и симплекс-методом. Для этого воспользуемся пакетом "Эврика" фирмы Bor Land [5]. Для начала решения необходимо войти в NORTON COMMANDER, найти директорию EVRIKA и, подведя к ней курсор, войти в пакет, нажав клавишу ENTER. Для запуска пакета EVRIKA необходимо подвести курсор к файлу eureka exe и нажать клавишу ENTER. На экране компьютера появится изображение, соответствующее экрану начала работы с пакетом. В верхней части экрана появилось меню, состоящее из восьми разделов. Рассмотрим подробно лишь те, которые необходимы нам для работы (Edit, Solve, Report, File).

В режиме Edit осуществляется запись задачи, которую необходимо решать . Для начала ввода исходных данных для решения задачи необходимо подвести курсор на Edit и нажать клавишу ENTER. Курсор перемещается в окно Edit экрана, в которое заносятся исходные данные. Для окончания редактирования без записи необходимо нажать клавишу ESC, для записи и редактирования - клавишу F2, для создания нового файла клавишу F3. Курсор переместиться в главное меню, где необходимо переместить его на раздел Solve (решение задачи) и нажать клавишу^ ENTER. В процессе решения задачи на экране появится окно Progress, в котором высвечиваются текущие значения ошибки решения, искомых переменных и время решения задачи в секундах. После завершения задачи в окне Solution появляются значения переменных файла задачи и экстремальное (max или min) значение целевой функции. Если уравнение нельзя решить точно, высвечивается значение максимальной ошибки решения.

Возвратимся в главное меню, нажав клавишу ESC. _ На последнем этапе работы необходимо генерировать отчет. Для этого курсор переместим на раздел Report (отчет) и нажмем клавишу ENTER.

Появляется падающее меню, в котором курсор подводим к файлу output (вывод) и нажимаем клавишу ENTER. Появляется еще одно подменю, в котором выберем PRINTER и нажмем клавишу ENTER. В текущей строке файла output появляется надпись PRINTER. Курсор подведем к файлу GO (идти), нажмем клавишу ENTER (предварительно включив принтер и подготовив его к работе) и распечатаем отчет решения задачи линейного программирования.

33

Для завершения работы выйдем в главное меню, нажав клавишу ESC, юдведем курсор к разделу FILE и нажмем клавишу ENTER. Сеанс работы завершен. 2.6. ЗАДАНИЕ К ПРАКТИЧЕСКОМУ ЗАНЯТИЮ №> 2 Задача 1. Предприятие может выпустить три вида продукции: Пь П2, П3. Для выпуска продукции требуются ресурсы трех видов: трудовые, станочное оборудование и полуфабрикаты. Объемы и нормы расхода ресурсов приведены в условных обозначениях в табл. 9, цифровые значения, в соответствии с номером варианта студента, даны в табл. 10, Задача 2. На машиностроительном предприятии из стандартных листов металла необходимо вырезать заготовки трех видов в количествах, соответственно равных 24, 31 и 18 штук. Каждый лист может быть разрезан на заготовки двумя способами. Количество получаемых заготовок при данном способе раскроя и величина отходов, которые при этом получаются, приведены в условных обозначениях в табл. 11, цифровые значения, в соответствии с номером варианта студента, - в табл. 12. Определить, сколько листов металла и по какому способу следует раскроить так, чтобы было получено не меньше нужного количества заготовок при минимальных затратах. 9. Данные для постановки задачи 1

34

10. Исходные данные для выполнения практического занятия № 2 (задача )

1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

2 8 15 3 6 2 2 15 10 8 8 2 3 2 3 12 14 12 16 15 4 6 13 9 2 7

3 5 18 3 8 5 4 8 12 5 5 4 1 2 7 9 12 13 8 25 •3 14 12 15 4 9

4 7 12 2 9 6 2 6 6 2 2 3 2 1 7 7 12 15 12 10 1 16 7 18 4 12

5 280 420 360 360 240 120 420 200 120 120 180 60 120 420 240 420 250 240 400 60 420 300 270 220 150

6 6 6 2 1 3 6 12 4 2 7 6 4 2 2 6 10 10 4 10 1 1 1 6 1 5

7 7 4 4 3 7 5 7 8 4 2 9 3 6 2 12 7 15 1 15 5 20 20 3 1 1

8 4 4 3 2 7 1 9 14 7 4 8 2 5 1 10 15 12 8 10 2 12 10 9 1 10

9 480 360 240 240 420 280 120 200 150 180 240 90 420 120 120 240 300 120 350 50 360 350 180 100 200

10 9 4 6 3 4 7 6 15 4 4 1 9 7 2 8 9 8 6 5 6 4 7 12 6 4

11 6 5 9 2 4 7 12 8 3 3 3 8 3 4 4 8 7 18 15 2 4 14 15 2 6

12 5 8 8 3 2 4 10 6 8 9 2 3 7 2 14 8 9, 12 15' 8 4 15 6 8 8

13 360 540 180 180 300 30 240 420 180 150 180 150 240 120 200 120 350 180 300 100 160 250 390 180 240

14 8 120 24 18 12 16 12 20 3 12 12 45 18 20 18 16 12 24 30 10 20 16 24 20 12

15 7 80 25 12 18 12 18 12 6 16 15 75 16 10 20 20 15 18 20 12 8 24 30 18 16

16 5 160 18 15 16 18 20 18 7 20 25 60 12 15 12 24 18 30 25 18 16 20 15 16 8

35

11. Данные для постановки задачи 2

12. Исходные данные для выполнения практического занятия № 2 (задача 2)

2.7.КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Приведите запись задачи линейного программирования в стандартной форме. 2. В чем заключается суть задачи линейного программирования? 3. Что такое "базисная" и "свободная" переменные? 4. Перечислите основные этапы решения задачи линейного программирования симплекс-методом.

36 5. Приведите форму представления задачи линейного программирования при ее решении табличным методом. 6. По каким критериям судят о допустимости и оптимальности решения задачи линейного программирования табличным методом? 7. Каким образом можно перейти от записи задачи-линейного программирования в стандартной форме к ее записи в канонической форме? 8. Перечислите основные правила заполнения таблиц при решении задачи линейного программирования табличным методом. 9. Приведите примеры задач линейного программирования. 10. В чем отличие двойственной задачи линейного программирования от основной?

СПИСОК ЛИТЕРАТУРЫ 1. Худобин Л.В., Берзин В.Р., Гурьянихин В.Ф. Разработка технологических процессов изготовления деталей в курсовых и дипломных проектах: Учебное пособие. Ульяновск: УлГТУ, 1996. 148 с. 2. Белов М.А., Унянин А.Н. Размерный анализ технологических процессов обработки заготовок: Учебное пособие / Под общ. ред. Л.В. Худобина. Ульяновск: УлГТУ, 1997. 148 с. . . 3. Руденко П.А. Проектирование технологических процессов в машиностроении. Киев: Вища школа, 1985. 255 с. 4. Булыжев Е.М. Размерный анализ технологического процесса механической обработки заготовок: Методические указания. Ульяновск: УлПИ, 1988.24с. 5. Веткасов Н.И., Богданов В.В. Математическое моделирование производственных и технологических процесов: Методические указания. Ульяновск: УлПИ, 1994.56с.

6. Коршунов Ю.М. Математические основы кибернетики: Учебное пособие. М.: Энергия, 1972. 376 с. 7. Справочник технолога-машиностроителя. Т. 1 / Под ред. А.Г. Косиловой и Р.К. Мещерякова. М.: Машиностроение, 1985. 656 с. 8. Маталин А.А. Технология машиностроения. Л.: Машиностроение. Ленингр. отд-ние, 1985. 496 с.