Начало инженерного творчества
Сущность изобретения и отличительные от прототипа признаки. Одномерная и безусловная градиентная оптимизация. Решение транспортной задачи методом Фогеля и симплекс-методом. Решение методом Фогеля и переход от неоптимального опорного плана к лучшему.
| Рубрика | Производство и технологии |
| Вид | отчет по практике |
| Язык | русский |
| Дата добавления | 04.04.2015 |
| Размер файла | 384,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное агентство по образованию РФ
Пермский национальный исследовательский политехнический университет
ФАКУЛЬТЕТ «АЭРОКОСМИЧЕСКИЙ»
КАФЕДРА «ТЕХНОЛОГИЯ, КОНСТРУИРОВАНИЕ И АВТОМАТИЗАЦИЯ»
ОТЧЕТ ПО ДИСЦИПЛИНЕ
«Начало инженерного творчества»
Руководитель дисциплины,
доцент (Б.Ф. Потапов)
Исполнитель отчета,
студент группы ТКА-13-1бзу (А.С. Азанов)
Пермь 2015
1. Описание изобретения
Сверло с устройствами регулировки диаметра резания.
Код по международной патентной классификации: B23B51.
Автор(ы):
Огоньков Константин Эдуардович (RU)
Патентообладатель(и):
Огоньков Константин Эдуардович (RU)
Дата публикации: 27 мая 2012 года.
Дата начала действия патента: 22 июня 2010 года.
изобретение фогель симплекс транспортный
1.1 Область использования:
Изобретение относится к обработке материалов резанием. Более конкретно - к сверлам, и может использоваться для сверления отверстий в прокате, в поковках из стали, обработке отливок из цветных металлов. Также может использоваться в обработке заготовок из пластмасс.
1.2 Цель изобретения
Цель данного изобретения в том чтобы уменьшить номенклатуру режущего инструмента данного типа, путем изменения диаметров обрабатываемого отверстия, тем самым уменьшить затраты на покупку или изготовление отдельного сверла на каждое отверстие.
1.3 Сущность изобретения и отличительные от прототипа признаки
Указанный технический результат достигается тем, что данное сверло содержит корпус, в котором размещен регулируемый элемент, регулировочную пластину, которая взаимодействует с регулируемым элементом через регулировочный винт. Также имеются фиксирующие винты, для закрепления данных регулировочных элементов. От прототипа отличает то, что данное сверло позволяет настраивать диаметр сверления в определенном диапазоне (в зависимости от того, с каким базовым диаметром выполнен корпус).
1.4 Пример конкретного выполнения (рисунок 1)
Рисунок 1 - пример конкретного выполнения сверла
Сверло содержит корпус (1), регулируемый элемент (2), регулировочную пластину (4), имеющую боковую поверхность для взаимодействия с регулируемым элементом, регулировочный винт (8) и фиксирующие винты (5; 9) для регулируемого элемента и регулировочной пластины. Для повышения точности регулирования регулировочная пластина расположена с возможностью определения своей толщиной смещения регулируемого элемента, фиксирующий винт размещен в направляющем пазу, выполненном в регулировочной пластине. При этом регулировочный винт выполнен с буртиками и установлен в паз, выполненный в регулировочной пластине, а регулируемый элемент установлен с возможностью смещения относительно фиксирующего его винта.
2. Одномерная оптимизация
Дана функция: R(x)=1,5sin (x-1)
Найти максимум на интервале: [-2,2].
Строим график данной функции (рисунок 2).
Рисунок 2 - график функции R(x)=1,5sin (x-1).
По форме графика определяем что он имеет 1 экстремум, применяем метод деления отрезка пополам. Ошибка задается по х: =0,05.
Находим середину отрезка (точка 0), в каждой из половинок (в левой и правой) находим значения функции с учетом погрешности и, сравниваем их. Определяем, в какой из половинок находится экстремум (уравнение (1) и (2)).
x1:=0,05
1.5·sin·(x1-1)= - 1.22
R(x1) = -1.22 (1)
x2:= -0,05
1.5·sin·(x2 - 1) = -1.301
R(x2) = -1.301 (2)
В правой части находится экстремум, так как значение функции больше чем в левой.
В качестве следующего отрезка выбираем отрезок [0, 2]. Находим середину отрезка (точка 1), в каждой из половинок (в левой и правой) находим значения функции с учетом погрешности и, сравниваем их. В зависимости от сравнения значений функции в точках выбирают новый отрезок, решение производится аналогично решению в уравнениях (1) и (2).
x3:= 1.05
1.5·sin·(x3 - 1) = 0.075
R(x3) = 0.075
x4:= 0.95
1.5·sin·(x4 - 1) = - 0.075
R(x4) = - 0.075
Далее следуем аналогично. Выполняем еще 3 шага.
x5:= 1.55
1.5·sin·(x5-1) = 0.784
R(x5) = 0.784
x6:= 1.45
1.5·sin·(x6 - 1) = 0.652
R(x6) = 0.652
x7:= 1.8
1.5·sin·(x7 - 1) = 1.076
R(x7):= 1.076
x8:=1.7
1.5·sin·(x8 - 1) = 0.966
R(x8) = 0.966
x9:= 1.925
1.5·sin·(x9 - 1) = 1.198
R(x9) = 1.198
x10:= 1.822
1.5·sin·(x10 - 1) = 1.099
R(x10) = 1.099
Максимум функции находится в точке х9: 1.198
3. Многомерная безусловная градиентная оптимизация
3.1 Метод градиента
Дана функция R(x1, x2) = (x1)2 + 2·(x2 - 1.3)2
Требуется найти минимум функции.
Начальная точка: x1 = -0.5; x2 = 0.
Параметры поиска: коэффициент шага h = 0,1, пробный g = 0,02, погрешность Е = 0,01.
Алгоритм метода: алгоритм 1 (хi+1 =хi - hgrad R(xi)) (3).
Алгоритм коррекции шага: без коррекции коэффициента пропорциональности шага (h = const).
Способ вычисления производной: вычисление gradR с парными пробами.
h:= 0.1; g:= 0.02; E:=0.01
R(x1, x2):= (x1)2 + 2·(x2 - 1.3)2
В начальной точке вычисляем градиент функции:
x1:= - 0.5 x2:= 0
R(x1 + g, x2) = 3.61
R(x1 - g, x2) = 3.65
R(x1, x2 + g) = 3.527
R(x1, x2 - g) = 3.735
Значение критерия:
R(x1, x2) = 3.63
Делаем рабочий шаг №1 , получаем
x1 = -0.4
x2 = 0.52
В новой точке опять вычисляем производные:
x1:= - 0.4 x2:= 0.52
R(x1 + g, x2) = 1.361
R(x1 - g, x2) = 1.393
R(x1, x2 + g) = 1.315
R(x1, x2 - g) = 1.44
Значение критерия
R(x1, x2) = 1.377
Делаем рабочий шаг №2, получаем
x1 = -0.32
x2 = 0.832
Далее вновь вычисляем производные и продолжаем расчет путем повторения шагов. В общем выполняем n кол-во шагов для нахождения оптимального значения.
x1:= - 0.32 x2:= 0.832
R(x1 + g, x2) = 0.528
R(x1 - g, x2) = 0.554
R(x1, x2 + g) = 0.504
R(x1, x2 - g) = 0.579
Рабочий шаг № 3
x1 = -0.256
x2 = 1.019
Вычисление производных
x1:= - 0.256 x2:= 1.019
R(x1 + g, x2) = 0.213
R(x1 - g, x2) = 0.234
R(x1, x2 + g) = 0.202
R(x1, x2 - g) = 0.246
R(x1,x2)=0.223
Рабочий шаг №4
x1 = -0.205
x2 = 1.132
Вычисление производных
x1:= - 0.205 x2:= 1.132
R(x1 + g, x2) = 0.091
R(x1 - g, x2) = 0.107
R(x1, x2 + g) = 0.086
R(x1, x2 - g) = 0.113
R(x1,x2)=0.099
Рабочий шаг № 5
x1 = -0.164
x2 = 1.264
Вычисление производных
x1:= - 0.164 x2:= 1.264
R(x1 + g, x2) = 9.85·103
R(x1 - g, x2) = 0.018
R(x1, x2 + g) = 0.012
R(x1, x2 - g) = 0.017
R(x1,x2)=0.014
Рабочий шаг № 6.
x1 = -0.084
x2 = 1.278
Вычисление производных
x1:= - 0.084 x2:= 1.278
R(x1 + g, x2) = 5.035·10-3
R(x1 - g, x2) = 0.012
R(x1, x2 + g) = 7.044·10-3
R(x1, x2 - g) = 0.011
R(x1,x2)=7.99 ·10-3
Рабочий шаг № 7.
x1 = -0.067
x2 = 1.278
Вычисление производных
x1:= - 0.067 x2:= 1.278
R(x1 + g, x2) = 2.563·10-3
R(x1 - g, x2) = 7.931·10-3
R(x1, x2 + g) = 4.599·10-3
R(x1, x2 - g) = 6.695·10-3
R(x1,x2)=4.847 ·10-3
Рабочий шаг №8
x1 = -0.054
x2 = 1.292
Вычисление производных
x1:= - 0.054 x2:= 1.292
R(x1 + g, x2) = 1.258·10-3
R(x1 - g, x2) = 5.553·10-3
R(x1, x2 + g) = 3.177·10-3
R(x1, x2 - g) = 4.435·10-3
R(x1,x2)=3.006 ·10-3
Рабочий шаг № 9
x1 = -0.043
x2 = 1.295
Вычисление производных
x1:= - 0.043 x2:= 1.295
R(x1 + g, x2) = 5.712·10-4
R(x1 - g, x2) = 4.007·10-3
R(x1, x2 + g) = 2.312·10-3
R(x1, x2 - g) = 3.066·10-3
R(x1,x2)=1.889 ·10-3
Рабочий шаг № 10
x1 = -0.034
x2 = 1.297
Вычисление производных
x1:= - 0.034 x2:= 1.297
R(x1 + g, x2) = 2.222·10-4
R(x1 - g, x2) = 2.971·10-3
R(x1, x2 + g) = 1.77·10-3
R(x1, x2 - g) = 2.223·10-3
R(x1,x2)=1.197 ·10-3
Рабочий шаг № 11
x1 = -0.027
x2 = 1.298
Вычисление производных
x1:= - 0.027 x2:= 1.298
R(x1 + g, x2) = 6.183·10-5
R(x1 - g, x2) = 2.261·10-3
R(x1, x2 + g) = 1.426·10-3
R(x1, x2 - g) = 1.697·10-3
R(x1,x2)=7.613 ·10-4
Рабочий шаг № 12
x1 = -0.022
x2 = 1.299
Вычисление производных
x1:= - 0.022 x2:= 1.299
R(x1 + g, x2) = 6.037·10-6
R(x1 - g, x2) = 1.765·10-3
R(x1, x2 + g) = 1.204·10-3
R(x1, x2 - g) = 1.367·10-3
R(x1,x2)=4.856 ·10-4
После 12 шагов сводим значения расчетов в таблицу 1 и проверяем.
Таблица 1 - результаты расчетов после 12 шагов.
|
n |
x1 |
х2 |
dR/dx1 |
dR/dx2 |
|gradR| |
R |
|
|
1 |
-0.5 |
0 |
-1 |
-5.2 |
5.295 |
3.63 |
|
|
2 |
-0.4 |
0.52 |
-0.8 |
-3.12 |
3.221 |
1.377 |
|
|
3 |
-0.32 |
0.832 |
-0.64 |
-1.872 |
1.978 |
0.54 |
|
|
4 |
-0.256 |
1.019 |
-0.512 |
-1.123 |
1.234 |
0.223 |
|
|
5 |
-0.205 |
1.132 |
-0.41 |
-0.674 |
0.789 |
0.099 |
|
|
6 |
-0.164 |
1.199 |
-0.328 |
-0.404 |
0.52 |
0.047 |
|
|
7 |
-0.131 |
1.239 |
-0.262 |
-0.243 |
0.357 |
0.025 |
|
|
8 |
-0.105 |
1.264 |
-0.21 |
-0.146 |
0.256 |
0.014 |
|
|
9 |
-0.084 |
1.278 |
-0.168 |
-0.087 |
0.189 |
0.00799 |
|
|
10 |
-0.067 |
1.287 |
-0.134 |
-0.052 |
0.144 |
0.004847 |
|
|
11 |
-0.054 |
1.292 |
-0.107 |
-0.031 |
0.111 |
0.003006 |
|
|
12 |
-0.043 |
1.295 |
-0.086 |
-0.019 |
0.088 |
0.001889 |
|
|
13 |
-0.034 |
1.297 |
-0.069 |
-0.011 |
0.07 |
0.001197 |
|
|
14 |
-0.027 |
1.298 |
-0.055 |
-0.00679 |
0.055 |
0.0007613 |
|
|
15 |
-0.022 |
1.299 |
-0.044 |
-0.004075 |
0.044 |
0.0004856 |
В последней точке модуль градиента практически равен заданной погрешности (0,044 ? 0,01), поэтому поиск прекращается.
Строим график градиента (рисунок 3)
Рисунок 3 - построение графика
3.2 Метод Гаусса-Зайделя
Для той же самой задачи найти минимум функции методом Гаусса - Зайделя выполнив 4-8 шагов.
Дана функция R(x1, x2) = (x1)2 + 2·(x2 - 1.3)2 (4)
Требуется найти минимум функции.
Начальная точка: x1 = -0.5; x2 = 0.
Интервал поиска: x1нач = -3, х1кон = 2, х2нач = -3, х2кон = 2.
Параметры поиска: коэффициент шага h = 0,1, погрешность Е = 0,01
Из начальной точки x1 = -0.5; x2 = 0 вычисляем критерий.
x1 := -0.5
x2 := 0
R(x1, x2) = (x1)2 + 2·(x2 - 1.3)2 = 3.63
Ищем минимум критерия оптимальности по переменной x1. Используем прием последовательного сканирования, т.е. «шагаем» до первого лучшего значения критерия применяя алгоритм x1i+1 = x1i ±h. Нижний индекс - номер переменной, верхний - номер шага. Знак «+» или «-» выбирается в зависимости от направления изменения критерия: нужно взять такой знак, при котором критерий уменьшается. Выбираем знак «+».
Наилучшей в этом направлении оказывается точка с координатами:
x1 := 0
x2 := 0
R(x1, x2) = (x1)2 + 2·(x2 - 1.3)2 = 3.38
полученная после шести шагов.
Из этой точки ищем минимум критерия по переменной x2 тем же методом.
Наилучшей в этом направлении оказывается точка с координатами:
x1 := 0
x2 := 0.6
R(x1, x2) = (x1)2 + 2·(x2 - 1.3)2 = 0.98
Полученная после 6 шагов.
На этом первый цикл заканчивается и начинается следующий, заключающийся опять в поиске minR по переменной x1 и x2.
После 4 шагов получаем координаты:
x1 := 0.4
x2 := 1
R(x1, x2) = (x1)2 + 2·(x2 - 1.3)2 = 0.34
Отобразим координаты на графике (рисунок 4)
Рисунок 4 - траектории полученные методом Гаусса - Зайделя
4. Решение транспортной задачи методом Фогеля и симплекс - методом
4.1 Решение методом Фогеля
По теории известно что решение транспортной задачи методом Фогеля, позволяет найти приближенное значение оптимального плана. Проверим это на практике. Решим одну и ту же задачу методом Фогеля и распределительным методом, который является одним из вариантов симплексного метода.
Сначало решим задачу методом Фогеля.
Определим колонки штрафов.
Таблица 2 - определение колонок штрафов.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3 |
6 |
5 |
35 |
6-3=3 |
|
|
2 |
4 |
10 |
11 |
8 |
70 |
8-4=4 |
|
|
3 |
2 |
2 |
3 |
9 |
65 |
3-2=1 |
|
|
4 |
3 |
4 |
9 |
12 |
30 |
4-3=1 |
|
|
Потребности |
40 |
85 |
25 |
50 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
8-5=3 |
Выделяем клетку с максимальным штрафом. Находим в ряду минимальную цену, добавляем максимальное значение потребностей. Исправляем значение штрафа.
Таблица 3 - исправление значения штрафа.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3 |
6 |
5 |
35 |
6-3=3 |
|
|
2 |
4(40) |
10 |
11 |
8 |
70-40=30 |
(8-4=4) 10-8=2 |
|
|
3 |
2 |
2 |
3 |
9 |
65 |
3-2=1 |
|
|
4 |
3 |
4 |
9 |
12 |
30 |
4-3=1 |
|
|
Потребности |
0 |
85 |
25 |
50 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
8-5=3 |
Таблица 4 - повторение шага.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3(35) |
6 |
5 |
0 |
6-5=1 |
|
|
2 |
4(40) |
10 |
11 |
8 |
70-40=30 |
(8-4=4)10-8=2 |
|
|
3 |
2 |
2 |
3 |
9 |
65 |
3-2=1 |
|
|
4 |
3 |
4 |
9 |
12 |
30 |
4-3=1 |
|
|
Потребности |
0 |
85-35=50 |
25 |
50 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
8-5=3 |
Строку 1 больше не используем. Продолжаем поиск.
Таблица 5 - продолжение шага.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3(35) |
6 |
5 |
0 |
6-5=1 |
|
|
2 |
4(40) |
10 |
11 |
8 |
70-40=30 |
(8-4=4)10-8=2 |
|
|
3 |
2 |
2 |
3(25) |
9 |
65-25=40 |
3-2=1 |
|
|
4 |
3 |
4 |
9 |
12 |
30 |
4-3=1 |
|
|
Потребности |
0 |
85-35=50 |
0 |
50 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
9-8=1 |
Столбец 3 больше не используем. Продолжаем поиск.
Таблица 6 - повторение шага, продолжение поиска.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3(35) |
6 |
5 |
0 |
6-5=1 |
|
|
2 |
4(40) |
10 |
11 |
8(30) |
0 |
(8-4=4)10-8=2 |
|
|
3 |
2 |
2 |
3(25) |
9 |
65-25=40 |
3-2=1 |
|
|
4 |
3 |
4 |
9 |
12 |
30 |
4-3=1 |
|
|
Потребности |
0 |
85-35=50 |
0 |
50-30=20 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
9-8=1 |
Строку 2 больше не используем. Продолжаем поиск.
Таблица 7 - повторение пред. шага, продолжение поиска.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3(35) |
6 |
5 |
0 |
6-5=1 |
|
|
2 |
4(40) |
10 |
11 |
8(30) |
0 |
(8-4=4)10-8=2 |
|
|
3 |
2 |
2(40) |
3(25) |
9 |
40-40=0 |
3-2=1 |
|
|
4 |
3 |
4 |
9 |
12 |
30 |
4-3=1 |
|
|
Потребности |
0 |
50-40=10 |
0 |
50-30=20 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
9-8=1 |
Строку 3 больше не используем. Продолжаем поиск.
Таблица 8 - повторение пред. шага, продолжение поиска.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3(35) |
6 |
5 |
0 |
6-5=1 |
|
|
2 |
4(40) |
10 |
11 |
8(30) |
0 |
(8-4=4)10-8=2 |
|
|
3 |
2 |
2(40) |
3(25) |
9 |
0 |
3-2=1 |
|
|
4 |
3 |
4(10) |
9 |
12 |
30-10=20 |
4-3=1 |
|
|
Потребности |
0 |
10-10=0 |
0 |
50-30=20 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
9-8=1 |
Столбец № 2 больше не используем. Продолжаем поиск.
Таблица 9 - повторение пред. шага, продолжение поиска.
|
1 |
2 |
3 |
4 |
Запасы |
Штраф |
||
|
1 |
9 |
3(35) |
6 |
5 |
0 |
6-5=1 |
|
|
2 |
4(40) |
10 |
11 |
8(30) |
0 |
(8-4=4)10-8=2 |
|
|
3 |
2 |
2(40) |
3(25) |
9 |
0 |
3-2=1 |
|
|
4 |
3 |
4(10) |
9 |
12(20) |
20-20=0 |
4-3=1 |
|
|
Потребности |
0 |
0 |
0 |
20-20=0 |
|||
|
Штраф |
3-2=1 |
3-2=1 |
6-3=3 |
9-8=1 |
Оптимальный план найден.
Рассчитываем стоимость затрат (5).
Z= 3(35)+4(40)+8(30)+2(40)+3(25)+4(10)+12(20)= 940 (5).
Решим ту же самую задачу распределительным методом, и сравним насколько полученный опорный план методом Фогеля приближен к оптимальному.
4.2 Поиск первого опорного плана
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 2. Для этого элемента запасы равны 65, потребности 40. Поскольку минимальным является 40, то вычитаем его. x31 = min(65,40) = 40.
|
x |
3 |
6 |
5 |
35 |
|
|
x |
10 |
11 |
8 |
70 |
|
|
2 |
2 |
3 |
9 |
65 - 40 = 25 |
|
|
x |
4 |
9 |
12 |
30 |
|
|
40 - 40 = 0 |
85 |
25 |
50 |
0 |
Искомый элемент снова равен 2. Для этого элемента запасы равны 25, потребности 85. Поскольку минимальным является 25, то вычитаем его. x32 = min(25,85) = 25.
|
x |
3 |
6 |
5 |
35 |
|
|
x |
10 |
11 |
8 |
70 |
|
|
2 |
2 |
x |
x |
25 - 25 = 0 |
|
|
x |
4 |
9 |
12 |
30 |
|
|
0 |
85 - 25 = 60 |
25 |
50 |
0 |
Искомый элемент равен 3. Для этого элемента запасы равны 35, потребности 60. Поскольку минимальным является 35, то вычитаем его. x12 = min(35,60) = 35.
|
x |
3 |
x |
x |
35 - 35 = 0 |
|
|
x |
10 |
11 |
8 |
70 |
|
|
2 |
2 |
x |
x |
0 |
|
|
x |
4 |
9 |
12 |
30 |
|
|
0 |
60 - 35 = 25 |
25 |
50 |
0 |
Искомый элемент равен 4. Для этого элемента запасы равны 30, потребности 25. Поскольку минимальным является 25, то вычитаем его. x42 = min(30,25) = 25.
|
x |
3 |
x |
x |
0 |
|
|
x |
x |
11 |
8 |
70 |
|
|
2 |
2 |
x |
x |
0 |
|
|
x |
4 |
9 |
12 |
30 - 25 = 5 |
|
|
0 |
25 - 25 = 0 |
25 |
50 |
0 |
Искомый элемент равен 8. Для этого элемента запасы равны 70, потребности 50. Поскольку минимальным является 50, то вычитаем его. x24 = min(70,50) = 50.
|
x |
3 |
x |
x |
0 |
|
|
x |
x |
11 |
8 |
70 - 50 = 20 |
|
|
2 |
2 |
x |
x |
0 |
|
|
x |
4 |
9 |
x |
5 |
|
|
0 |
0 |
25 |
50 - 50 = 0 |
0 |
Искомый элемент равен 9. Для этого элемента запасы равны 5, потребности 25. Поскольку минимальным является 5, то вычитаем его. x43 = min(5,25) = 5.
|
x |
3 |
x |
x |
0 |
|
|
x |
x |
11 |
8 |
20 |
|
|
2 |
2 |
x |
x |
0 |
|
|
x |
4 |
9 |
x |
5 - 5 = 0 |
|
|
0 |
0 |
25 - 5 = 20 |
0 |
0 |
Искомый элемент равен 11. Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его. x23 = min(20,20) = 20.
|
x |
3 |
x |
x |
0 |
|
|
x |
x |
11 |
8 |
20 - 20 = 0 |
|
|
2 |
2 |
x |
x |
0 |
|
|
x |
4 |
9 |
x |
0 |
|
|
0 |
0 |
20 - 20 = 0 |
0 |
0 |
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20] |
8[50] |
70 |
|
|
3 |
2[40] |
2[25] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25] |
9[5] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*35 + 11*20 + 8*50 + 2*40 + 2*25 + 4*25 + 9*5 = 1000
4.3 Улучшение опорного плана
Проверка опорного плана на оптимальность. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение поставок. План распределения поставок будет оптимальным лишь в том случае, когда целевая функция имеет минимальное значение, т.е. когда дальнейшее уменьшение затрат на поставку будет невозможно. Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Дij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки хij=1 от поставщика Аi к потребителю Вj.
При этом должно быть произведено такое изменение остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса спроса и поставок транспортной задачи. Величина Дij называется оценкой свободной клетки (или характеристика).
В исходном решении задачи имеются клетки свободные от поставок.
Необходимо вычислить значение оценок Дij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).
Под циклом пересчета (цепью) понимается замкнутая ломаная линия. Вершинами цикла (цепи) являются клетки таблицы, проще - вершины лежат в клетках таблицы.
Причем одна из вершин находится в свободной от поставки клетке, в той, для которой определяется оценка Дij. Все другие вершины находятся в базисных клетках, т.е. клетках, занятых поставками.
Вершины, в которых поставки при перераспределении увеличиваются, отмечаются плюсом и называются положительными вершинами и, наоборот, вершины, в которых поставки при перераспределении уменьшаются отмечаются минусом и называются отрицательными вершинами.
В цикле знаки по вершинам расставляют начиная с вершины, лежащей в свободной клетке, для которой определяется Дij. В нее записывают знак плюс, затем знаки по вершинам чередуются: минус, плюс , минус, плюс и т. д., независимо от того, расставляют ли их по часовой стрелке или в обратном направлении. Таким образом, в цикле всегда насчитывается одинаковое число положительных и отрицательных вершин.
Следующий этап решения транспортной задачи заключается в улучшении опорного плана.
Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Дij, то за один переход к лучшему плану можно занять поставкой только одну клетку - ту, которая обеспечивает наибольшее снижение целевой функции.
Шаг 1. Определяем оценку для каждой свободной клетки.
(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9[+] |
3[35][-] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20] |
8[50] |
70 |
|
|
3 |
2[40][-] |
2[25][+] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25] |
9[5] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (1,1 > 1,2 > 3,2 > 3,1).
Оценка свободной клетки равна Д11 = (9) - (3) + (2) - (2) = 6.
(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35][-] |
6[+] |
5 |
35 |
|
|
2 |
4 |
10 |
11[20] |
8[50] |
70 |
|
|
3 |
2[40] |
2[25] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25][+] |
9[5][-] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (1,3 > 1,2 > 4,2 > 4,3).
Оценка свободной клетки равна Д13 = (6) - (3) + (4) - (9) = -2.
(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35][-] |
6 |
5[+] |
35 |
|
|
2 |
4 |
10 |
11[20][+] |
8[50][-] |
70 |
|
|
3 |
2[40] |
2[25] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25][+] |
9[5][-] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (1,4 > 1,2 > 4,2 > 4,3 > 2,3 > 2,4).
Оценка свободной клетки равна Д14 = (5) - (3) + (4) - (9) + (11) - (8) = 0.
(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4[+] |
10 |
11[20][-] |
8[50] |
70 |
|
|
3 |
2[40][-] |
2[25][+] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25][-] |
9[5][+] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (2,1 > 2,3 > 4,3 > 4,2 > 3,2 > 3,1).
Оценка свободной клетки равна Д21 = (4) - (11) + (9) - (4) + (2) - (2) = -2.
(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10[+] |
11[20][-] |
8[50] |
70 |
|
|
3 |
2[40] |
2[25] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25][-] |
9[5][+] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (2,2 > 2,3 > 4,3 > 4,2).
Оценка свободной клетки равна Д22 = (10) - (11) + (9) - (4) = 4.
(3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20] |
8[50] |
70 |
|
|
3 |
2[40] |
2[25][-] |
3[+] |
9 |
65 |
|
|
4 |
3 |
4[25][+] |
9[5][-] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (3,3 > 3,2 > 4,2 > 4,3).
Оценка свободной клетки равна Д33 = (3) - (2) + (4) - (9) = -4.
(3;4): В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20][+] |
8[50][-] |
70 |
|
|
3 |
2[40] |
2[25][-] |
3 |
9[+] |
65 |
|
|
4 |
3 |
4[25][+] |
9[5][-] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (3,4 > 3,2 > 4,2 > 4,3 > 2,3 > 2,4).
Оценка свободной клетки равна Д34 = (9) - (2) + (4) - (9) + (11) - (8) = 5.
(4;1): В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20] |
8[50] |
70 |
|
|
3 |
2[40][-] |
2[25][+] |
3 |
9 |
65 |
|
|
4 |
3[+] |
4[25][-] |
9[5] |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (4,1 > 4,2 > 3,2 > 3,1).
Оценка свободной клетки равна Д41 = (3) - (4) + (2) - (2) = -1.
(4;4): В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20][+] |
8[50][-] |
70 |
|
|
3 |
2[40] |
2[25] |
3 |
9 |
65 |
|
|
4 |
3 |
4[25] |
9[5][-] |
12[+] |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Цикл приведен в таблице (4,4 > 4,3 > 2,3 > 2,4).
Оценка свободной клетки равна Д44 = (12) - (9) + (11) - (8) = 6.
Опорный план является неоптимальным, поскольку имеются отрицательные оценки клеток (3,3;) равные: (-4).
4.4 Переход от неоптимального опорного плана к лучшему
Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (3;3) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
|
1 |
2 |
3 |
4 |
Запасы |
||
|
1 |
9 |
3[35] |
6 |
5 |
35 |
|
|
2 |
4 |
10 |
11[20] |
8[50] |
70 |
|
|
3 |
2[40] |
2[20] |
3[5] |
9 |
65 |
|
|
4 |
3 |
4[30] |
9 |
12 |
30 |
|
|
Потребности |
40 |
85 |
25 |
50 |
Подобные документы
Расчет сборочной размерной цепи методом полной взаимозаменяемости и вероятностным методом. Решение размерной цепи методом максимума-минимума и вероятностным методом. Допуски составляющих размеров при вероятностном методе и по методу максимума-минимума.
задача [242,3 K], добавлен 22.04.2009Схемы расположения полей допусков стандартных сопряжений. Соединение подшипника качения с валом и корпусом. Расчет размерных цепей. Решение задачи методом максимума - минимума. Решение задачи теоретико-вероятностным методом (способ равных квалитетов).
курсовая работа [441,6 K], добавлен 26.01.2010Оптимизация решения на моделях нелинейного программирования. Решение задачи линейного программирования графическим методом. Разработка раскроя древесно-стружечных плит на заготовки. Затраты времени на обработку деталей. Обоснование решений на моделях СПУ.
курсовая работа [2,8 M], добавлен 17.05.2012Характеристика, эскизы узлов и безмаcштабные схемы размерных цепей. Определение координаты середины поля допуска замыкающего звена. Предельные отклонения для всех составляющих цепи. Вид уравнения критерия правильности и решение обратной задачи.
курсовая работа [614,8 K], добавлен 15.01.2010Методика расчета размерных цепей методом регулирования. Выявление числа неподвижных компенсаторов. Основные детали сборочного узла. Точность замыкающего звена размерной цепи. Изменение размера компенсирующего звена без удаления материала компенсатора.
методичка [76,3 K], добавлен 21.01.2011Выбор посадок гладких цилиндрических соединений, для шлицевых соединений с прямым профилем зуба. Расчет и выбор посадок с натягом. Расчет размерной цепи методом полной взаимозаменяемости и вероятностным методом. Решение линейных размерных цепей.
курсовая работа [208,2 K], добавлен 09.04.2011Выбор посадок для гладких цилиндрических соединений, расположенных на тихоходном валу, обоснование выбора системы и квалитетов. Расчет и выбор посадок с натягом. Решение линейных размерных цепей методом полной взаимозаменяемости и вероятностным методом.
курсовая работа [139,8 K], добавлен 10.03.2011Расчёт размеров контрольно-измерительного калибра для скобы (контркалибра). Расчет посадки с натягом для соединения вала и втулки. Расчет размерных цепей методом максимума-минимума (методом полной взаимозаменяемости) и теоретико-вероятностным методом.
курсовая работа [145,0 K], добавлен 14.07.2012Методика и основные этапы решения размерных цепей методом полной взаимозаменяемости, порядок проведения прямых и обратных расчетов. Определение координаты середины поля допуска замыкающего звена, допуска замыкающего звена по известной зависимости.
контрольная работа [380,7 K], добавлен 20.01.2010Перенос нагрузки в узлы. Переход к общей системе координат. Поворот координатных осей с помощью матрицы преобразования координат. Объединение конечных элементов. Суммирование рассылаемого блока с имеющимся блоком в матрице методом сложения жесткостей.
презентация [772,0 K], добавлен 24.05.2014Определение положений, скоростей и ускорений звеньев рычажного механизма и их различных точек. Исследование движения звеньев методом диаграмм, методом планов или координат. Расчет усилий, действующих на звенья методом планов сил и рычага Жуковского.
курсовая работа [2,8 M], добавлен 28.09.2011Кинематический анализ рычажного механизма в перманентном движении методом планов и методом диаграмм. Определение линейных скоростей точек и угловых скоростей звеньев механизма, его силовой анализ методом кинетостатики. План зацепления зубчатых колес.
курсовая работа [454,1 K], добавлен 10.09.2012Кинематическое и кинетостатическое исследование механизма рабочей машины. Расчет скоростей методом планов. Силовой расчет структурной группы и ведущего звена методом планов. Определение уравновешивающей силы методом "жесткого рычага" Н.Е. Жуковского.
курсовая работа [1,3 M], добавлен 04.05.2016Решение технической задачи упрощения изготовления инструмента для пластического сверления за счет применения быстрорежущей стали с твердосплавным покрытием, нанесенным детонационным методом. Влияние режимов напыления на стойкость твердосплавных покрытий.
автореферат [801,1 K], добавлен 21.09.2014Основные понятия и определения по допускам и посадкам. Зависимость единиц допуска от номера квалитета. Образование и обозначение полей допусков и посадок. Расчёт размерной цепи методом максимума-минимума и вероятностным методом подшипников качения.
контрольная работа [100,3 K], добавлен 07.08.2013Усилие, прикладываемое к ножу в течение всего процесса резания. Расчёт сопротивлений пускового реостата. Построение кривых скорости, тока и момента двигателя в функции времени при пуске и торможении методом конечных приращений и методом Савинкова.
курсовая работа [2,9 M], добавлен 16.12.2013Метод формальной замены производной конечно-разностными отношениями. Преимущества и недостатки численных методов. Вычисление температур в узлах ограждающей конструкции и нахождение сопротивления теплопередачи. Влияние электромагнитного излучения.
дипломная работа [854,0 K], добавлен 10.07.2017Химическая формула и вид молекулы полиэтилена. Характеристика материала и изделия по назначению. Толщина пленки различных марок. Усадка и предельные отклонения. Технологическая схема установки для производства пленки рукавным методом с приемкой вверх.
реферат [847,2 K], добавлен 10.02.2014Особенности выбора посадок для гладких цилиндрических и шпоночных соединений редуктора, применяемого для понижения оборотов двигателя и повышения крутящего момента. Методика расчета размерной цепи методом полной взаимозаменяемости и вероятностным методом.
курсовая работа [124,9 K], добавлен 13.09.2010Расчет годовой программы запуска и определение типа производства табличным методом. Анализ технических условий на изготовление детали и технологичности конструкции детали. Расчет припусков на механическую обработку расчетно-аналитическим методом.
курсовая работа [331,3 K], добавлен 18.02.2009
