М о с к о в с к и й
радиоаппаратостроительный
т е х н и к у м
PК У Р С О В О Й П Р О Е К Т
на тему:
@'ОПТИМАЛТНЫЙ РАСКРОЙ ПРОМЫШЛЕННЫХ МАТЕРИАЛОВ'
по предмету:
@'МОДЕЛИРОВАНИЕ ПРОИЗВОДСТВЕННЫХ И ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ'
Работу выполнил: Работу проверил:
ученик группы П-406 преподаватель
Горбатов Р.С. Капустина Р.Н.
1995 г.
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 1 -
СОДЕРЖАНИЕ:
@СОДЕРЖАНИЕ @СТРАНИЦА
ВВЕДЕНИЕ................................................... 2
1. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ......................... 3
2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ........................ 4
3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ.
ОБОСНОВАНИЕ ВЫБОРА...................................... 5
4. СХЕМА АЛГОРИТМА И ЕЕ ОПИСАНИЕ........................... 6 - 10
5. КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ... 11
6. КРАТКАЯ ХАРАКТЕРИСТИКА ВЫБРАННГО ЯЗЫКА ПРОГРАММИРОВАНИЯ. 12
7. РЕШЕНИЕ ЗАДАЧИ-ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРАММЫ..13 - 14
8. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ........................... 15
9. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ.................................16 - 17
СПИСОК ЛИТЕРАТУРЫ.......................................... 18
ЗАКЛЮЧЕНИЕ.ВЫВОДЫ ПО РАБОТЕ................................ 19
ПРОГРАММА.ОПИСАНИЕ ПРОГРАММЫ............................... 20
ПРИЛОЖЕНИЕ 1...............................................21 - 26
ПРИЛОЖЕНИЕ 2...............................................27 - 30
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 2 -
ВВЕДЕНИЕ.
В настоящее время новейшие достижения математики и современной
вычислительной техники находят все более широкое применение в эко-
номических исследованиях в планировании. Накоплен достаточный опыт
постановки и решения экономических задач с помощью математических
методов. Особенно успешно развиваются методы оптимального планиро-
вания.
В промышленном производстве применяется большое количество мате-
риалов,которые подвергаются разрезке на штучные заготовки.В про-
цессе раскроя неизбежны отходы из-за некратности размеров заготовки
размерам исходного материала.На промышленных предприятиях исполь-
зуются различные методы борьбы с потерями из-за отходов.Наиболее
рациональным считается метод проведения совместных раскроев.@Сов-
@местный раскроя означает разрезку единицы материала на комплект
разных деталей.
Идея совместного раскроя состоит в следующем.Известны размеры
заготовок и размер исходного материала.На основании этого разра-
батываются варианты раскроя единицы исходного материала с различ-
ным составом заготовок и различной величиной отходов.Поскольк у
варианты раскроя разрабатываются для единицы исходного материала,
в них не учитывается требуемое количество заготовок.Поэтому на
основании этих вариантов строится модель линейного программирова-
ния,где в качестве переменных берется количество исходного матери-
ала,раскраиваемого по каждому варианту.Так как модель строится
на основании вариантов раскроя,она названа @вариантная модель
@оптимального раскроя.С помощью данной модели можно определить ,
какое количество исходного материала и по каким вариантам нужно
раскраивать,чтобы получить требуемое количество заготовок с мини-
мальными отходами.Этот набор вариантов будет оптимальным.
В данном курсовом проекте будет рассмотрено решение экономичес-
кой задачи на оптимальный раскроя материалов универсальным методом
линейного программирования @Симплекс-методом.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 3 -
1.ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ.
ОПТИМАЛЬНЫЙ РАСКРОЙ МАТЕРИАЛОВ.
В соответствии с производственными заданиями заготовительный
цех должен нарезать из стальных прутков длиною 11,0 м следующее
количество заготовок:
Длиною по: 1,6 м - 480 штук.
1,3 м - 760 штук.
3,6 м - 180 штук.
Требуется: 1) Составить план раскроя прутков , обеспечивающий
минимальное количество отходов.
2) Определить абсолютную величину отходов и коэф -
фициент использования металла.
Предварительно , перед решением задачи , необходимо составить
таблицу возможных вариантов раскроя поступающих прутков данной
партии. После решения задачи сделать проверку полученных резуль-
татов.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 4 -
2.МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.
Для решения данной задачи введем следующие обозначения:
m ( i=1,2,...,m ) - виды заготовок.
n ( j=1,2,...,n ) - способы раскроя.
Bi - план по заготовкам "i"-того вида.
bij - количество заготовок "i"-того вида ,
полученные "j"-тым способом раскроя.
Xj - количество единиц (штук) исходного материала,
которое следует раскраивать по "j"-тому способу.
Cj - количество отходов при "j"-том способе раскроя.
При решении задачи надо учитывать следующие формулы:
СИСТЕМА ОГРАНИЧЕНИЙ:
n
1) / bij * Xj т Bj i=(1,2,...,m)
j=1
2) Xj т 0
ЦЕЛЕВАЯ ФУНКЦИЯ:
n
3) F = / Cj * Xj ^#& min
j=1
Составим таблицу возможных вариантов раскроя прутков:
Таблица 1.
ЪДДДДДДДВДДДДДДДДДДДДДДДДДДДДДДДВДДДДДД
Заготов Способы раскроя План
ки ГДДДВДДДВДДДВДДДВДДДВДДД
1 2 3 4 5 6
ГДДДДДДДЕДДДЕДДДЕДДДЕДДДЕДДДЕДДДЕДДДДДД
1,6 6 5 2 - 2 2 480
1,3 1 2 6 5 3 - 760
3,6 - - - 1 1 2 180
ГДДДДДДДЕДДДЕДДДЕДДДЕДДДЕДДДЕДДДЕДДДДДД
Отходы 0,10,4 0 0,90,30,6
АДДДДДДДБДДДБДДДБДДДБДДДБДДДБДДДБДДДДДДЩ
Система уравнений будет строится по данной таблице.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 5 -
3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ.
ОБОСНОВАНИЕ ВЫБОРА.
Данная задача была решена @Симплекс-методом, т.к. указанный метод
является универсальным методом для решения задач линейного програм-
мирования.
Известно, что оптимальные решения задачи линейного программирования
связаны с угловыми точками многогранника решений. Угловых точек может
быть много, если есть много ограничений. Количество угловых точек
соответствует количеству базисных решений. Для каждого базисного ре-
шения однозначно определяется значение целевой функции. Найти опти-
мальное решение (оптимальный план), беспорядочно перебирая все базис-
ные решения, в поисках такого, которое приносит целевой функции экс-
тремальное значение, весьма затруднительно.
В связи с этим необходим такой переход от одного базисного решения
к другому, в результате которого новое решение приносило бы, в невы-
рожденной задачи на максимум, большее значение целевой функции, а в
невырожденной задаче на минимум - меньшее. Такой процесс решения
задачи реализует Симплекс-метод. Процесс решения задачи продолжается
до получения оптимального плана либо до установления факта отсутст-
вия решения задачи. Переход от одного базисного решения к другому
называется @итерацией Симплекс-метода.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 6 -
4.СХЕМА АЛГОРИТМА И ЕЕ ОПИСАНИЕ.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 7 -
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 8 -
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 9 -
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 10 -
В данной блок-схеме блоки означают следующее:
1: Начало алгоритма.
2,3,4,5: Ввод данных о системе уравнений.
6: Определение общего размера матрицы.
7: Ввод коэффициентов при Х, стоящих в целевой функции.
8: Ввод свободных членов для каждого уравнения
9: Ввод коэффициентов при Х и Y, стоящие в каждом уравнении.
10: YV- отключить признак конца подсчета,
itr - счетчик количества итераций.
11: Если YV=True (признак конца подсчета), то выполнить вывод
конечного результата (Блок 31), иначе продолжить решение.
12: Сделать копию индексной строки.
13: Вызов функции testY (эта функция проверяет наличие искуственных
переменных в массиве).
14: Если testY=True (массив содержит искуственные переменные),
вызвать процедуру indY (Блок 15), иначе вызвать процедуру indX.
15: Вызов процедуры indY. Эта процедура ведет подсчет индексной
строки с учетом искуственных переменных.
16: Вызов процедуры indX. Эта процедура ведет подсчет индексной строки
в том случае, если искуственные переменные выведены из матрицы.
17: Вызов функции test0. Эта функция проверяет наличие положительных
элементов в индексной строке.
18: Если test0=false (в индексной строке содержатся положительные
элементы), выдать промежуточные результаты на экран (Блок 19),
иначе завершить решение задачи (Блок 30).
19: Вывод промежуточного результата на экран.
20: Процедура MaxSt выделяет ключевой столбец.
21: Процедура Str выделяет ключевую строку и находит разрешающий
элемент в матрице.
22: Выводится базис ключевой строки и ключевого столбца.
23: Сделать копию основного массива (a) и столбца (H).
24: Заполняется строка введеного базиса путем деления соответствующих
элементов выведенной строки на разрешающий элемент.
25: Заполнить новую матрицу по заданной формуле.
26: Вычисление столбца H.
27: Отключить признак конца подсчета.
28: Получение новой матрицы, столбца Н и индексной строки.
29: Определение следующей итерации.
30: Определение завершения решения задачи. (Конец подсчета итерации)
31: Вывод конечного результата решения задачи на экран.
32: Конец алгоритма.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 11 -
5. КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И
ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.
Слово 'компьютер' означает 'вычислитель', т.е. устройство для
вычисления. В 1981г. фирмой 'IBM Corporation' был выпущен первый
персональный компьютер IBM PC, на базе 16-разрядного процессора
Intel-8088. Персональный компьютер состоит из нескольких основных
частей: устройства ввода (клавиатура), устройство вывода (монитор),
центральный процессор, выполняющий функции управления и счетный
процесс, внутреняя память ОЗУ и ПЗУ, различные устройства для работы
с внешней памятью и шины данных, соединяющей все устройства воедино
и служащей для передачи данных между устройствами. Персональный ком-
пьютер типа IBM собирается по принципу открытой архитектуры, т.е.
владелец компьютера может постепенно докупать дополнительные устрой-
ства (модем, сканер, CD-ROM) и без проблем устанавливать их.
Есть много параметров, которыми характеризуется персональный
компьютер (тип монитора, количество оперативной памяти, емкость винт-
честера), но главные параметры - тип процессора и тактовая частота.
Данная программа не требует высоких характеристик вычислительной
системы, она писалась на компьютере типа IBM PC со следующими харак-
теристиками: процессор Intel-80286, тактовая частота 16 Мгц, опера-
тивная память 1 Мб, монитор типа VGA, свободное место на винтчестере
для программы 14 Кб. Эту программу так же можно запустить и на дру-
гой вычислительной системе, с более низкими характеристиками.
Операционная система - программа, которая загружается сразу после
включения компьютера. Она осуществляет диалог с пользователем, управ-
ление компьютером, его ресурсами, запускает другие программы на вы-
полнение. ОС обеспечивает пользователю и прикладным программам удоб-
ный способ общения с устройствами компьютера. Для данной программы
не требуется специального программного обеспечения. Программный мини-
мум: Операционная система MS-DOS 3.0 или выше и резидентная програм-
ма 'экранный руссификатор', которая позволяет выводить на экран
буквы русского алфавита.
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
- 12 -
6. КРАТКАЯ ХАРАКТЕРИСТИКА
ЯЗЫКА ПРОГРАММИРОВАНИЯ.
Программы для первых компьютеров приходилось писать на машинном
языке, т.е. в кодах, непосредственно воспринимаемых компьютером.
Это было очень тяжелой и кропотливой работой, поэтому в начале 50-х
годов были разработаны так называемые @языки низкого уровня, которые
позволяли писать программы не в машинных кодах, а с использованием
мнемонических обозначений. К таким языкам относится язык ASSEMBLER,
однако и этот язык слишком сложен: программист должен очень хорошо
знать архитектуру вычислительной машины. С развитием вычислительной
техники появились @языки высокого уровня. Программа на таком языке
состоит из последовательности команд и операторов, понятных пользова-
телю. К таким языкам относится язык программирования @Turbo PASCAL.
Язык Паскаль впервые появился на машинах III поколения. В середине