Размещено на http://www.allbest.ru/

Тольяттинский государственный университет

Кафедра «Технология машиностроения»

Основы оптимизации

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

Составил: Бобровский А.В.

1. Теория графов

«Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос это, хотя и банальный, показался мне достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, при помощи которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может».

Из письма Л. Эйлера от 13 марта 1736 г.

Город Кенигсберг (ныне Калининград) располагался на обоих берегах реки Прегель и на двух островах, которые соединялись семью мостами. План расположения мостов приведен на рис.1.1. Задача, о которой говорится в письме, состоит в том, чтобы во время прогулки пройти каждый мост по одному разу и вернуться в исходную точку.

Так как нас интересуют только переходы по мостам, то план города можно заменить схемой, представленной на рис. 1.2. На этой схеме земельные участки, разделенные рукавами реки, как бы сжаты в точки A, B, C, D (вершины), а мосты вытянуты в линии a, b, c, d, e, f, g (ребра). Нетрудно проверить (например, перебрав все возможные варианты), что изображенную фигуру нельзя обвести острием пера, не отрывая его от бумаги и проходя по каждой дуге ровно один раз.



Рис. 1.1 Рис. 1.2

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

Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом (рис. 1.3). Маршрутом, или путем, соединяющим вершины A и B графа, называется такая последовательность его ребер, в которой каждые два ребра имеют общую концевую точку, причем первое ребро выходит из вершины А, а последнее входит в вершину В (рис. 1.4). В этом случае вершины А и В называются связанными. Граф называется связным, если любая пара вершин его связана (рис. 1.5). Граф, изображенный на рис.6, несвязен.

Рис. 1.3 Рис. 1.4

Рис. 1.5 Рис. 1.6

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

Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно. Вершина А четна - в ней сходится 6 ребер, а вершина В - нечетна - в ней сходятся 5 ребер. Число ребер, сходящихся в вершине графа, называется степенью (порядком) этой вершины.

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

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

Так как число пунктов конечно, то в принципе задача может быть решена простым перебором.

Пример. Компания, находящаяся в городе А, должна поставить комплектующие в города В, С и D, расстояния между которыми ей известны:

АВ = 11, АС = 13, AD = 17, ВС = 6, BD = 9, CD = 10

(рис. 1.7). Требуется указать кратчайший циклический маршрут из города А, проходящий через три других города.

Рис. 1.7

Возможных циклических маршрутов шесть:

ABCDA, ACDBA, ADBCA, ACBDA, ABDCA, ADCBA.

Однако для решения задачи достаточно сравнить длины только первых трех:

ABCDA, ACDBA, ADBCA.

Эти длины равны соответственно

11+6+10+17=44, 13+10+9+11=43, 17+9+6+13=45.

Тем самым, кратчайшим является любой из маршрутов длиной 43 -- ACDBA или ABDCA.

Важный класс графов составляют так называемые деревья. Деревом называется связный граф, который не имеет циклов (рис. 1.8).

Рис. 1.8

Число В вершин дерева и число Р его ребер различаются на единицу:

В=Р+1

Если каждому ребру графа поставить в соответствие какое-то выражение, то такой граф называют взвешенным.

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

1.2 Дерево решений

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

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

Одной из прикладных задач в теории графов применительно к промышленности является «Задача о двух станках»

1.3 Задача о двух станках

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

Задача: построить орграф, учитывая, что вершины - «детали», определить Гамильтонов путь и временные циклы на станках 1^ой и 2^ой деталей, определить последовательность изготовления деталей с целью минимизации затрат.

Исходные данные:

№ ст.	Номер детали
	1	2	3	4	5
	Трудоемкость, мин.
1	6	7	3	5	8
2	8	4	2	6	12

Строим орграф:

Рис. 1.10

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

Рис. 1.11

Вывод: анализ графиков (рис. 1.11) показал, что целесообразно обрабатывать сначала первую деталь, а потом вторую:Т_{1график}=18 мин., Т_{2график}=21 мин.

Пусть время обработки i-ой детали есть (a_ib_i), а (a_jb_j) - время обработки j-ой детали. При сравнении i-ой и j-ой деталей направление дуги принимается в сторону большего значения в выражении:

min (a_ib_i) или min (a_jb_j).

а₂=7, b₂=4

a₃=3, b₃=2

min (a₂b₃) или min (a₃b₃)

min (7,2)=2 min(3,4)=3 принимаем след. направление дуги: 23.

а₁=1, b₁=6

a₃=5, b₃=2

min (1,6)=1 min(5,2)=2 принимаем след. направление дуги: 13.

Для решения данной задачи необходимо построить Гамильтонов путь.

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

Определим Гамильтонов путь: 41523.

ТЕОРЕМА: если в орграфе любые две вершины соединены хотя бы одной дугой, то в таком орграфе существует Гамильтонов путь.

Для наглядности результаты последовательности отражают в виде карт Ганта (Гант-карта) (рис. 1.12).

Рис. 1.12 Гант-карта

1.4 Максимальный поток

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

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

Рис. 1.13 Рис. 1.14

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

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

Пример 4. Рассмотрим сеть, заданную на рис. 1.15. Требуется найти максимально возможный поток из узла 1 в узел 7.

Рис. 1.15

Вычислим пропускную способность ключевых сечений. Имеем:

пропускная способность сечения {(1,2), (1,3)} равна 4,

пропускная способность сечения {(2,4), (3,5)} равна 3,

пропускная способность сечения {(1,3), (2,3), (6,7)} равна 5,

пропускная способность сечения {(5,7), (6,7)} равна 2.

Сравнивая пропускные способности сечений, получаем, что максимальный поток от вершины 1 к вершине 7 равен 2.

2. Оптимизация параметров процесса резания

Описывают закономерности и связи. Позволяют решать размерные задачи в машиностроении (рис. 2.1).

Рис. 2.1

(2.1)

(2.2)

Или, например, процесс стружкообразования (рис. 2.2).

Рис. 2.2

где q_д - теплота деформирования;

q_тп - теплота трения по передней поверхности;

q_тз - теплота от трения по задней поверхности;

q₁, q₂ - результирующие тепловые потоки в инструмент.

Q_c=C₁q_д^''+C₂q_тп-Cq₁ (2.3)

Q₃=C₄q_д^'+C₅q_тз-C₆q₂ (2.4)

Q₄=C₇q₁^'+C₈q₂ (2.5)

Или многие другие прикладные инженерные задачи.

2.1 Оптимизация режимов резания

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

а₁₁х₁+а₁₂х₂+…+а_1nx_n <или>b₁

а₂₁х₁+а₂₂х₂+…+а_2nx_n <или>b₂ (2.6)

………………………………..

а_m1х₁+а_m2х₂+…+а_mnx_n <или>b_m

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

2.1.1 Ограничения по мощности привода главного движения станка

N_эN (2.7)

N_эР_zV - эффективная мощность (2.8)

N - номинальная мощность привода;

- КПД привода;

P=C_pzt^XpzS^YpzV^-Zpz (2.9)

Тогда подставим соотношение (2.7) в (2.9):

N>C_pzt^XpzS^YpzV^1-Zpz (2.10)

Все постоянные соберем в коэффициент А₁:

(2.11)

Прологарифмируем (2.11):

lgVB₁-lgS (2.12)

x lgA₁ a₁ x₁

x₂B₁-a₁x₁ (2.13)

a₁x₁+ x₂B₁ (2.14)

Графически (2.14) выглядит:

₁=arctga₁

Рис. 2.3

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

Следующие ограничения:

2.1.2 Ограничения по кинематике оборудования

S_{min оборуд} SS_{max оборуд} (2.15)

(2.16)

где [D], мм.

[n], об/мин.

[V], м/мин.

Правую и левую части (2.15) и (2.16) прологарифмируем и сведем в (2.17):

х₁В₂

х₁В₃ (2.17)

х₂В₄

х₂В₅

Графически данные ограничения выглядят (рис. 2.4.):

Рис. 2.4

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

2.1.3 Ограничения по прочности инструмента (токарного резца). Для схемы консольного закрепления (рис. 2.5) определим допустимые значения по прочности поперечного сечения державки сечением ВхН.

Рис. 2.5

[] (2.18)

(2.19)

k=const

где

тогда: kC_pzt^XpzS^YpzV^Zpz[] (2.20)

Объединив в А₂ все постоянные, получим:

(2.21)

х₁-а₆х₂b₆

b₆=lgA₂

a₆=

₆=arctga₆

Рис. 2.6

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

2.1.4 Ограничения по точности обработки. Согласно схемы закрепления и обработки, максимальный прогиб заготовки f, как правило, находится в точке приложения силы резания.

f[f] (2.22)

f - прогиб заготовки, мм.

[f] - требуемая точность обработки, мм.



Рис. 2.7

[f]=T; принять =1/3 (2.23)

Совершим преобразования аналогично предыдущим ограничениям.

;

T;

;

C_pyt^XpyS^YpzV^ZpyА₃;

х₁+а₇х₂b₇; (2.24)

₇=arctga₇

Рис. 2.8

Сведем полученные линейные неравенства в систему линейных ограничений:

а₁х₁+ х₂b₁

х₁ b₂

х₁ b₃

х₂b₄ (2.25)

х₂b₅

х₁- а₆х₂b₆

х₁+а₇х₂b₇

Для дальнейшего решения системы (2.25) необходимо знаки неравенства свести к единому виду (либо «», либо «»)

а₁х₁+ х₂b₁

х₁ b₂

-х₁ -b₃

х₂b₄ (2.26)

-х₂-b₅

х₁- а₆х₂b₆

х₁+а₇х₂b₇

Матричная форма выражения 2.26: , (2.27) где для нашего примера:

m>n (7>2); ; .

В векторном виде 2.26 выглядит:

,

(2.28)

2.2 Целевая функция

(2.29)

выражение (2.29) читается:

необходимо найти такое значение х_i, при которых многочлен С₁х₁+С₂х₂+…+ С_nх_nmax, при этом х_i должен лежать в области допустимых значений, описываемых выражением (2.28).

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

Пример.

Для нахождения оптимальных режимов резания:

Производительность имеет линейную зависимость от S и V:

П=kSV, (2.30)

где k - коэффициент пропорциональности.

Задача: Пmax

Логарифмируем (2.30):

Z=lgП=lgk+x₁+x₂max - целевая функция (2.31)

lgk = const.

Для выполнения (2.31) достаточно: х₁+х₂ max

Или в общем виде Z=C₁x₁+C₂x₂max, где C₁=1, C₂=1.

Переведём 2.29 в матричный вид:

(2.32)

Запись (2.33) совместно с (2.27)

(2.33)

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

Всё множество Q удовлетворяющих x_i0, называется допустимым множеством решений.

Если при этом выполняется:

для x_iQ

то - оптимальное решение.

2.3 Графическая оптимизация

Найти maxZ=2_x1+5x₂ при следующих технических ограничениях.

х₁4

х₂3

х₁+х₂5

х_1,20

Z_max=19 при x₁=2, x₂=3.

Для примера по V и S (рассмотрен ранее) приведена графическая интерпретация (рис. 2.9).

Рис. 2.9

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

Для предыдущего примера допустим, что maxZ=x₁+x₂. Получим, что целевая функция совпадает с одним из ограничений.

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

Рис. 2.10

2.4 Расширенная форма задачи линейного программирования.

Для перехода от системы неравенств вводят системы уравнений со свободными переменными. В противном случае выполнение решения системы вызовет затруднение.

Система (2.6) примет вид:

а₁₁х₁+а₁₂х₂+…+а_1nx_n+1х_n+1+0x_n+2+…+0x_n+m=b₁

а₂₁х₁+а₂₂х₂+…+а_2nx_n+0х_n+1+1x_n+2+…+0x_n+m=b₂ (2.34)

……………………………………………………..

а_m1х₁+а_m2х₂+…+а_mnx_n+0х_n+1+0x_n+2+…+1x_n+m=b_m

Получим расширенную форму системы технических ограничений. Необходимо добавить расширенную форму целевой функции.

С₁х₁+С₂х₂+…+С_nх_n+0х_n+1+0x_n+2+…+0х_n+mmax (2.35)

В матричной форме задача выглядит:

(2.36)

; , ,

где

Размерность: mхn

mхm

Векторная форма записи системы уравнений:

₁х₁+₂х₂+…+_nх_n+_n+1х_n+1+_n+2x_n+2+…+_n+mх_n+m=B (2.37)

₁, ₂…_n - рассмотрены ранее в (2.27), (2.28). С расширением задачи добавилась единичная матрица Е и, соответственно, столбцы:

, ,

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

х₁+х₂5 - исходная задача х₁+х₂+х₃=5 - расширенная задача

2.5 Базисное решение

Матрица расширенной задачи

mхm (2.38)

Выберем m строк и m столбцов.

Каждая матрица, состоящая из столбцов m и строк m называется базисной матрицей.

(mхm) - квадратная матрица, базисные значения.

(mхn) - прямоугольная матрица (из оставшихся столбцов) оставшиеся значения.

(,)

Выражение (2.34) в матричной форме принимает вид:

+=B (2.39)

, - матрицы-векторы, содержащие переменные вошедшие в базис () и не вошедшие в базис .

Пример.

Исходная задача линейного программирования:

х₁+х₂5

3х₁+2х₂12

х_1,20

m=2, n=2.

Задача расширенная может выглядеть:

1х₁+1х₂+1x₃+0x₄=5

3х₁+2х₂+0x₃+1x₄=12

Матрица коэффициентов расширенной задачи:

, , возьмем базис, , , .

Обратимся к уравнению (2.39): умножим правую часть на (обратную матрицу), получаем:

+ (2.40)

Которая показывает, что придавая различные значения мы получаем различные значения .

(2.41)

Выражение (2.41) называется базисным решением системы из m уравнений с m+n неизвестными.

Если полученное значение (2.41) содержит только положительные элементы не равные 0 и неотрицательные, его называют базисным допустимым решением.

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

Поиск базисных решений (продолжение задачи)

,

1.Найдём определитель:

=2-3=-1

2.Необходимо найти алгебраические дополнения для каждого элемента матрицы а_ij.

Алгебраическое дополнение - есть определитель (вычёркиваем из исходной матрицы i-го столбца j-той строки и умножаем этот определитель на (-1)^i+j).

,

₁₁=2; ₁₂=-3; ₂₁=-1; ₂₂=1

3.Составляется матрица алгебраических дополнений:

Находим транспонированную матрицу от исходной:

Матрица дополнений:

4. Поиск обратной матрицы:

,

- матрица обратная исходной матрице.

По формуле (4.4) найдём базисное решение.

Базисное решение допустимое.

,

3. Симплекс - метод. Поиск оптимального решения

3.1 Общая идея симплекс - метода

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

3.2 Графическая интерпретация

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

Нульмерный симплекс (точка)

Одномерный симплекс (отрезок)

Двумерный симплекс (треугольник)

Трёхмерный симплекс (тетраэдр)

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

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

Перемещают симплекс:

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

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

Типичные траектории движения симплекса:

1.Прямолинейная траектория с наивысшей возможной скоростью.

2.Движение с образованием зигзагов.

3.Движения с колебаниями.

4.Круговая траектория (циклическая).

1-ая и 2-ая траектории - нормальные траектории движения симплекса внутри ОДЗ.

1-ая траектория присутствует, когда ОДЗ однородна (одно оборудование, инструменты и т.д.).

2-ая траектория - ОДЗ неоднородна.

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

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

4-ая круговая означает, что симплекс достиг точки оптимума.

Координаты вершины, вокруг которой вращается симплекс, есть оптимальное решение.

Симплекс - один из базисов задачи линейного программирования.

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

3.3 Линейный алгоритм симплекс - метода

Аналитически выглядит:

₁х₁+₂х₂+₃х₃+…+_nх_n…_n+mх_m+n= (3.1)

₁, ₂,…,_n,…,_n+m - векторы-столбцы.

Выберем из (3.1) m независимых векторов и образуем из них базис.

++…+= (3.2)

Решение , ,…,

Переменные - базисные переменные.

Рассмотрим некоторый вектор не входящий в исходный базис. Вектор может быть выражен через векторы исходного базиса.

=К_1r1+ К_2r2+…+ К_mrm (3.3)

К_ir=К_1r, К_2r, К_3r - численные значения;

i- номер базисного вектора, на который умножаются данные коэффициенты;

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

Добавим вектор r к базису (3.2).

++…++= (3.4)

Переменные , ,…, x_i

Найдём связь между x_i и . Для этого умножим (3.3) на x_r и подставим в (3.4), полученное выражение приравняем к (3.2).

++…++К_1r1+К_2r2+…+К_mrm=++…+ (3.5)

++…+=-К_1r+-К_2r+…+-К_mr (3.6)

из (3.6) получим:

х₁=-К_1r; х₂=-К_2r;…; х_m=-К_mr.

х₁=-К_1r

х₂=-К_2r

………………. (3.7)

х_m=-К_mr

х_r

В обобщённом виде:

х_i=-К_ir (3.8)

Связь нового решения со старым при введении в старое (в базис) переменную x_r.

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

Чтобы новое решение было допустимым x_r можно выбрать таким образом, чтобы -К_ir0

(3.9)

Удаляем . Удаляют вектор, для которого применимо

(3.10)

, ,…, - решение.

Целевая функция:

Z=C₁+C₂+…+C_m+C_r=C₁-К_1r+C₂-К_2r+…+C_m-К_mr+C_rx_r=

Z подставим в 3.8 и получим:

 =С₁+С₂+…+С_m+(C_r-С₁К_1r -С₂К_2r -…-С_mК_mr) (3.11)

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

(3.12)

(3.12) - формула симплекс-разности.

Вместо выведенной переменной в исходный базис вводят переменную с максимальной симплекс-разностью S_r.

Итак, выше приведенные преобразования сведем в алгоритм Симплекс-метода:

1.Выбирают исходный базис и находят его решение.

, ,…,

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

2.Вычисляют симплекс-разности для всех переменных не вошедших в базис. S_r по формуле (3.12).

3.Вводят в базис переменную х_r, имеющую max симплекс-разность х_r с S_rmax, причём её значение определяют из условия (3.9)

для всех К_ir>0

4. Вводят переменную x_i, для которой выполняется условие 3.10.

5. Эти этапы повторяют до тех пор, пока симплекс разности всех переменных не вошедших в базис не станут отрицательными - признак оптимального решения.

3.4 Примеры решений

Пример 1.

maxZ=2х₁+5х₂.

х₁4

х₂3

х₁+х₂5

х_1,20

Решение:

Расширенная форма.

1х₁+0х₂+1x₃+0x₄+0х₅=4

0х₁+1х₂+0x₃+1x₄+0х₅=3

1х₁+1х₂+0x₃+0x₄+1х₅=5

maxZ=2х₁+5х₂+0х₃+0х₄+0х₅

, ,

1. В качестве базисных возьмем переменные x₃, х₄, х₅.

, ==

2. ₁=К₃₁₃+К₄₁₄+К₅₁₅

₂=К₃₂₃+К₄₂₄+К₅₂₅

Отсюда К₃₁=К₅₁=К₄₂=К₅₂=1; К₄₁=К₃₂=0

Симплекс-разности:

S₁=C₁-K₃₁C₃-K₄₁C₄-K₅₁C₅ S₁=2-10-00-10=2

S₂=C₂-K₃₂C₃-K₄₂C₄-K₅₂C₅ S₂=5-0-0-0=5

в базис вводим переменную х₂ т.к. S₂>S₁.

3.

; ; .

Вводим в базис =3 и выводим из базиса . В базис вводится переменная с тем же значением, как и у выводимой переменной.

2.; =3

по формуле (5.8):

=_старое-К₃₂=4-03=4

=_старое-К₅₂=5-13=2

₁=К₂₁₂+К₃₁₃+К₅₁₅

₄=К₂₄₂+К₃₄₃+К₅₄₅

S₁=C₁-K₂₁C₂-K₃₁C₃-K₅₁C₅ S₁=2-05=2

S₄=C₄-K₂₄C₂-K₃₄C₃-K₅₄C₅ S₄=0-15-0-0=-5

В базис вводится переменная с наибольшей S-разностью, т.е. х₁.

; ; .

выводим из базиса .

С каким значением выводим с таким значением вводим =2.

3. ; =2 !

=3-К₂₁=3 !

=4-К₃₁=2 !

₄=К₁₄₁+К₂₄₂+К₃₄₃

₅=К₁₅₁+К₂₅₂+К₃₅₃

S₄=C₄-K₁₄C₁-K₂₄C₂-K₃₄C₃ S₄=0-(-1)2-15-0=-3

S₅=C₅-K₁₅C₁-K₂₅C₂-K₃₅C₃ S₅=0-12-0-0=-2

Оптимальное решение:

х₁=2 см. значения выше

х₂=3 под знаком «!»

х₃=2

Пример 2.

1. х₂1

2х₂-х₁6

х₁+х₂5

maxZ=x₁-x₂

Решаем графическим методом:

, , ,

Решаем с использованием симплекс-метода:

х₂1 -х₂-1

2х₂-х₁6 -х₁+2х₂6

х₁+х₂5 х₁+х₂5

maxZ=x₁-x₂

0х₁-1х₂+1x₃+0x₄+0х₅=-1

-1х₁+2х₂+0x₃+1x₄+0х₅=6

1х₁+1х₂+0x₃+0x₄+1х₅=5

Z=1х₁-1х₂+0х₃+0х₄+0х₅

, ,

, , ,

₁₁=1 ₁₂=2 ₁₃=-1

₂₁=0 ₂₂=-1 ₂₃=

₃₁=0 ₃₂=0 ₃₃=-1

, =-1;

===

=1; =8; =4

S₁=C₁-K₂₁C₂-K₄₁C₄-K₅₁C₅ S₁=1-0=1

S₅=0+1(-1)=-1

В базис вводится переменная с наибольшей S-разностью, т.е. х₁.

; ; .

выводим из базиса .

=4. !

х₂=1-04=1 !

х₄=1+18=9

S₃=C₃-K₁₃C₁-K₂₃C₂-K₄₃C₄ S₄=0-11-(-1)(-1)=-2

S₅=C₅-K₁₅C₁-K₂₅C₂-K₄₅C₄ S₅=0-11-0=-1

Оптимальное решение:

х₁=4 см. значения выше

х₂=1 под знаком «!»

х₄=9

4. Симплекс - таблицы

4.1 Метод полного исключения

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

Создадим матрицу .

Такая матрица называется полной матрицей задачи.

Матрица R состоит из ^(mхn) и матрицы ^(mx1).

Следовательно ^(m,n+1).

Выделим квадратную матрицу F(mxm) - базис.

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

Пример.

2х₁+х₂+x₃=8

х₁+x₄=3

6х₁+2х₅=5

, ,

Алгоритм метода полного исключения:

1.Среди элементов матрицы выбирают любой не равный 0. Ему присваивают название - направляющий элемент шага.

А₁₁

Строка в называется направляющей строкой.

Присвоим индекс «р».

Направляющему столбцу присваивается индекс «q»

A_pq=a₁₁=2

p=1

q=1

2. Все элементы направляющей строки делят на направляющий элемент.

Получим новую направляющую строку.

3.Преобразуем остальные строки матрицы .

Пусть преобразованию подлежит строка i. Умножим в п.2 преобразованную строку на элемент а_iq

Пусть i=3.

6

a₃₁=[6360024]

После чего строка вычитается из строки [600025].

Получим строку:

_6 0 0 0 2 5

6 3 6 0 0 24

[0-3-6 0 2-19]

i=2, a₂₁=0.

Получили матрицу:

(1) - 1-ая итерация.

2-ой шаг.

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

Главная часть

Среди ненулевых элементов выбираем направляющий: p=q=2.

1.а₂₂=1.

2…4. Повторяем все действия предыдущего шага.

2.[010103] - направляющая строка.

i=1.

а_iq =a₁₂=1/2

1 1 0 0 4

0 0 0

1 0 1 - 0

i=3.

а_iq=a₃₂=-3

_ 0 -3 -6 0 2 -19

0 -3 0 -3 0 -9

0 0 -6 3 2 -10

3-ий шаг.

Главная часть -6 3 2

a₃₃=-6.

Строку делим на -6.

Получим

Преобразуем строку: i=1.

а_iq=a₁₃=1

[1 0 1 - 0 ]

[0 0 1 - - ]

1 0 0 0

для i=2.

а_iq=a₂₃=0 строка преобразованию не подлежит.

Общий признак окончания преобразований:

1. После очередного шага главная часть не содержит элементы.

2. Главная часть содержит только 0.

Главная часть отсутствует.

В этом случае числа в столбце свободны элементов одно из базисов.

х₁=5/6, х₂=3, х₃=5/3, х₄ и х₅ отсутствуют.

4.2 Полные симплекс - таблицы

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

Таблица 4.1

С			С1	С2	…	Сn
	ХF	B	A1	A2	…	An
С1	x1	b1	a11		…	a1n
С2	x2	b2	a21		…	a2n
…	…	…	…	…	…	…
Сm	xm	bm	am1	am2	…	amn
		Z	1	2	…	n

С - коэффициент целевой функции.

X_F - базисные переменные.

В - свободные члены.

А₁, А₂, …А_n - векторы-столбцы коэффициентов при переменных.

_i - оценки (величина обратная c симплекс - разности со знаком «-»).

Когда _j0.

Перед первым шагом Z⁽⁰⁾ = 0. Затем Z постоянно возрастает.

=С_j

На последующих этапах значения Z и пересчитываются:

(4.1)

(4.2)

Метод рассмотрим на примере 1:

max Z=2x₁+5x₂.

х₁+х₂5

х₁4

х₂3

, ,

С			2	5	0	0	0
	ХF	B	A1	A2	A3	A4	A5
0	x3	5	1	1	1	0	0
0	x4	4	1	0	0	1	0
0	x5	3	0	1	0	0	1
		0	-2	-5	0	0	0

Р

направляющая строка

q - направляющий

В исходной q направляющий

Направляющим выберем столбец с наименьшей оценкой.

_q=maх{|_j|, _j<0}

С			2	5	0	0	0
	ХF	B	A1	A2	A3	A4	A5
0	x3	2	1	0	1	0	-1
0	x4	4	1	0	0	1	0
5	x2	3	0	1	0	0	1
		15	-2	0	0	0	5

q

Р

Направляющая строка:

_5 1 1 1 0 0

3 0 1 0 0 1

2 1 0 1 0 -1

С			2	5	0	0	0
	ХF	B	A1	A2	A3	A4	A5
2	х1	2	1	0	1	0	-1
0	x4	2	0	0	-1	1	1
5	x2	3	0	1	0	0	1
		19	0	0	2	0	3

_4 1 0 0 1 0

2 1 0 1 0 -1

2 0 0 -1 1 1

Получаем: х₁=2, х₂=3, х₄=2. Z_max=19.

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

Выбирают строку с В<0.

Направляющим выбирают столбец таким образом, чтобы направляющий элемент был отрицателен.

При этом значение Z может уменьшаться.

Пример 2.

Найти:

maxZ=3x₁-2x₂.

х₁4

х₂5

х₁+х₂6

, ,

1.

С			3	-2	0	0	0
	ХF	B	A1	A2	A3	A4	A5
0	х3	4	1	0	1	0	0
0	x4	5	0	1	0	1	0
0	x5	-6	-1	-1	0	0	1
		0	-3	2	0	0	0

Р

q q

q

2. q

С			3	-2	0	0	0
	ХF	B	A1	A2	A3	A4	A5
3	х1	4	1	0	1	0	0
0	x4	5	0	0	0	1	0
0	x5	-2	0	-1	1	0	1
		12	0	2	3	0	0

Р

С			3	-2	0	0	0
	ХF	B	A1	A2	A3	A4	A5
3	х1	4	1	0	1	0	0
0	x4	3	0	0	1	1	1
-2	x2	2	0	1	-1	0	-1
		8	0	0	5	0	2

3. q

Р

_-6 -1 -1 0 0 1

-4 -1 0 -1 0 0

-2 0 -1 1 0 1

Получаем: х₁=4, х₂=2, х₄=3.

Пример 3.

maxZ=x₁-x₂.

х₂1

2х₂-х₁6

х₁+х₂5

, ,

1. q

С			1	-1	0	0	0
	ХF	B	A1	A2	A3	A4	A5
0	х3	-1	0	-1	1	0	0
0	x4	6	-1	2	0	1	0
0	x5	5	1	1	0	0	1
		0	-1	1	0	0	0

Р

С			1	-1	0	0	0
	ХF	B	A1	A2	A3	A4	A5
0	х3	-1	0	-1	1	0	0
0	x4	11	0	3	0	1	1
1	x1	5	1	1	0	0	1
		5	0	2	0	0	1

q

2.

Р

С			1	-1	0	0	0
	ХF	B	A1	A2	A3	A4	A5
-1	х2	1	0	1	-1	0	0
0	x4	8	0	0	3	1	1
1	x1	4	1	0	1	0	1
		3	0	0	2	0	1

3.

_ 6 -1 2 0 1 0 -5 -1 -1 0 0 -1 11 0 3 0 1 1	_-11 0 3 0 1 1 3 0 3 -3 0 0 8 0 0 3 1 1 _ 5 1 1 0 0 1 1 0 1 -1 0 0 4 1 0 1 0 1

4.3 Упрощённые симплекс - таблицы

Рассмотрим систему ограничений и линейную форму вида:

а₁₁х₁+а₁₂х₂+…+а_1nx_n = b₁

а₂₁х₁+а₂₂х₂+…+а_2nx_n = b₂ (4.3)

………………………………..

а_m1х₁+а_m2х₂+…+а_mnx_n = b_m

Z_min=c₀+c₁x₁+c₂x₂+…+c_nx_n (4.4)

х_i0, i= (4.5)

Используя метод Жордана--Гаусса, приведем записанную систему к виду, где выделены базисные переменные.

Введем условные обозначения:

x₁, х₂, ... х_r - базисные переменные;

x_r+1, х_r+2, ... х_n - свободные переменные.

x₁=₁-(_1r+1x_r+1+_1r+2x_r+2+…+_1nx_n)

x₂=₂-(_2r+1x_r+1+_2r+2x_r+2+…+_2nx_n)

…………………………….……… (4.6)

x_r=_r-(_rr+1x_r+1+_rr+2x_r+2+…+_rnx_n)

Z_min=₀-(_r+1x_r+1+_r+2x_r+2+…+_nx_n) (4.7)

По последней системе ограничений и целевой функции Z построим табл. 4.2.

Таблица 4.2 - Симплекс-таблица

Свободные неизвестные Базис- ные неизвестные	Свободный член	xr+1	xr+2	…	xn
x1 x2 … xr Zmin	1 2 … r 0	1r+1 2r+1 … rr+1 r+1	1r+2 2r+2 … rr+1 r+2	… … … … …	1n 2n … rn n

Данная таблица называется упрощённой симплекс - таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм упрощённого симплекс-метода:

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

4. Если имеется несколько одинаковых по величине симплекс - отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы.

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 7.4):

Таблица 4.3 - Преобразование симплекс-таблицы

Свободные неизвестные Базис- ные неизвестные	Свободный член	xr+1	x1	…	xn
xr+2				…
x2				…
…	…	…	…	…	…
xr				…
Zmin				…

6. Элемент табл. 4.3, соответствующий разрешающему элементу табл. 4.2, равен обратной величине разрешающего элемента.

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

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

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 4.2, одна вершина которого совпадает с разрешающим элементом, а другая -- с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 4.3 будет равен соответствующему элементу табл. 4.2 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе -- произведение элементов из двух неиспользованных вершин прямоугольника.

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

11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Пример 4Решение задачи упрощённым симплекс-методом:

-x₁+x₂+x₃=1

x₁-x₂+x₄=1

x₁+x₂+x₅=2

Z_max=2x₁-x₂+3x₃-2x₄+x₅

Приведем задачу к виду, допускающему применение симплекс-алгоритма:

x₃=1-(-x₁+x₂);

x₄=1-(x₁-x₂);

x₅=2-( x₁+x₂).

Подставим в выражение Z_max величины х₃, х₄, х₅:

Z_max=6x₁-7x₂+3.

По алгоритму целевая функция должна стремиться к минимуму:

Z_min=-Z_max=-6x₁+7x₂-3=-3-(6x₁-7x₂).

Составим симплекс-таблицу:

Свободные неизвест-ные Базис- ные неизвестные	Свободный член	x1	x2
x3 x4 x5 Zmin	1 1 2 -3	-1 1 1 6	1 -1 1 -7

Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен +6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной x₄ и столбца - х₁.

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

Свободные неизвестные Базис- ные неизвестные	Свободный член	x1	x2
x3 x4 x5 Zmin	2 1 1 -9	1 1 -1 -6	0 -1 2 -1

В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Z_min= -9; Х=(0; 0; 2; 1; 1); Z_max=-Z_min=9.

5. Логические модели

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

(Да - Нет).

⁺ - температура в зоне резания;

_п - теплота подогрева;

_р⁺ - теплота резания.

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

симплекс граф дерево решение

Размещено на Allbest.ru