Оптимальный раскрой промышленных материалов

б б а а вбвавмл в е г P вг авг вг л Работу проверил ученик группы П-406 преподаватель Горбатов Р.С. Капустина Р.Н. 1995 г. - 1 - ВВЕДЕНИЕ 1. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ 2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ 3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ. ОБОСНОВАНИЕ

ВЫБОРА 4. СХЕМА АЛГОРИТМА И ЕЕ ОПИСАНИЕ 6 - 5. КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 6. КРАТКАЯ ХАРАКТЕРИСТИКА ВЫБРАННГО ЯЗЫКА ПРОГРАММИРОВАНИЯ. 7. РЕШЕНИЕ ЗАДАЧИ-ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРАММЫ 13 - 8. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ 15 9.

ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ 16 - 17 СПИСОК ЛИТЕРАТУРЫ 18 ВЫВОДЫ ПО РАБОТЕ 19 ОПИСАНИЕ ПРОГРАММЫ 20 ПРИЛОЖЕНИЕ 1 21 - 26 ПРИЛОЖЕНИЕ 2 27 - 30 L - 2 бвпй ап и бвп в в ба вычислительной техники находят все более широкое применение в эко- номических исследованиях в планировании. Накоплен достаточный опыт постановки и решения экономических задач с помощью математических методов.

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

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

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

кой задачи на оптимальный раскроя материалов универсальным методом линейного программирования б-в. АДЩ ЪД - 3 - 1 ИАЛОВ. В соответствии с производственными заданиями заготовительный цех должен нарезать из стальных прутков длиною 11,0 м следующее количество заготовок Длиною по 1,6 м - 480 штук. 1,3 м - 760 штук. 3,6 м - 180 штук. Требуется 1 Составить план раскроя прутков , обеспечивающий минимальное количество отходов.

2 Определить абсолютную величину отходов и коэф - фициент использования металла. Предварительно , перед решением задачи , необходимо составить таблицу возможных вариантов раскроя поступающих прутков данной партии. После решения задачи сделать проверку полученных резуль- татов. L - 4 - 2 п аип з бгой зп m i1,2 m - виды заготовок. n j1,2 n - способы раскроя. Bi - план по заготовкам i-того вида. bij - количество заготовок i-того вида , полученные j-тым способом

раскроя. Xj - количество единиц штук исходного материала, которое следует раскраивать по j-тому способу. Cj - количество отходов при j-том способе раскроя. При решении задачи надо учитывать следующие формулы СИСТЕМА ОГРАНИЧЕНИЙ n 1 bij Xj т Bj i1,2 m j1 2 Xj 0 ЦЕЛЕВАЯ ФУНКЦИЯ n 3 F Cj Xj min j1 Составим таблицу возможных вариантов раскроя прутков

Таблица 1. T T Заготов Способы раскроя План ки T T T T T 1 2 3 4 5 6 1,6 6 5 2 - 2 2 480 1,3 1 2 6 5 3 - 760 3,180 Отходы 0,10,4 0 0,90,30,6 L Система уравнений будет строится по данной таблице. L - 5 - 3 п з л аи б-в, в указанный метод является универсальным методом для решения задач линейного програм- мирования. Известно, что оптимальные решения задачи линейного программирования связаны с угловыми

точками многогранника решений. Угловых точек может быть много, если есть много ограничений. Количество угловых точек соответствует количеству базисных решений. Для каждого базисного ре- шения однозначно определяется значение целевой функции. Найти опти- мальное решение оптимальный план, беспорядочно перебирая все базис- ные решения, в поисках такого, которое приносит целевой функции экс- тремальное значение, весьма затруднительно.

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

. L - 6 - 4 L - 7 - L - 8 - L - 9 - L - 10 - В данной блок-схеме блоки означают следующее 1 Начало алгоритма. 2,3,4,5 Ввод данных о системе уравнений. 6 Определение общего размера матрицы. 7 Ввод коэффициентов при Х, стоящих в целевой функции. 8 Ввод свободных членов для каждого уравнения 9 Ввод коэффициентов при Х и Y, стоящие в каждом уравнении.

10 YV- отключить признак конца подсчета, itr - счетчик количества итераций. 11 Если YVTrue признак конца подсчета, то выполнить вывод конечного результата Блок 31, иначе продолжить решение. 12 Сделать копию индексной строки. 13 Вызов функции testY эта функция проверяет наличие искуственных переменных в массиве. 14 Если testYTrue массив содержит искуственные переменные, вызвать процедуру indY

Блок 15, иначе вызвать процедуру indX. 15 Вызов процедуры indY. Эта процедура ведет подсчет индексной строки с учетом искуственных переменных. 16 Вызов процедуры indX. Эта процедура ведет подсчет индексной строки в том случае, если искуственные переменные выведены из матрицы. 17 Вызов функции test0. Эта функция проверяет наличие положительных элементов в индексной строке.

18 Если test0false в индексной строке содержатся положительные элементы, выдать промежуточные результаты на экран Блок 19, иначе завершить решение задачи Блок 30. 19 Вывод промежуточного результата на экран. 20 Процедура MaxSt выделяет ключевой столбец. 21 Процедура Str выделяет ключевую строку и находит разрешающий элемент в матрице. 22 Выводится базис ключевой строки и ключевого столбца.

23 Сделать копию основного массива a и столбца H. 24 Заполняется строка введеного базиса путем деления соответствующих элементов выведенной строки на разрешающий элемент. 25 Заполнить новую матрицу по заданной формуле. 26 Вычисление столбца H. 27 Отключить признак конца подсчета. 28 Получение новой матрицы, столбца Н и индексной строки.

29 Определение следующей итерации. 30 Определение завершения решения задачи. Конец подсчета итерации 31 Вывод конечного результата решения задачи на экран. 32 Конец алгоритма. L - 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 или выше и резидентная програм- ма экранный руссификатор, которая позволяет выводить на экран буквы русского алфавита. L - 12 - 6 Программы для первых компьютеров приходилось писать на машинном языке, т.е. в кодах, непосредственно

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

Turbo PASCAL. л б м ал пбп и е III п. ба 80-х годов фирма Borland выпустила язык Turbo PASCAL для персональных компьютеров, который обладал удобной интерактивной оболочкой. Язык сразу же завоевал огромную популярность. Объясняется это сочетанием двух безусловных его достоинств исключительной простотой и естест- венностью языка и великолепными сервисными возможностями диалоговой среды программирования.

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

систем. L - 13 - 7 По таблице 1 строим систему линейных уравнений 6X1 5X2 2X3 2X5 2X6 т 480 X1 2X2 6X3 5X4 3X5 т 760 Xj т 0 L- X4 X5 2X6 т 180 гжп, ваго г бб вм г, в Fmin 0,1X1 0,4X2 0X3 0,9X4 0,3X6 Приведем систему уравнений к кононическому виду 6X1 5X2 2X3 2X5 2X6 - X7 Y1 480 X1 2X2 6X3 5X4 3X5 - X8 Y2 760 АД X4 X5 2X6 - X9 Y3 180 гжп ав бгой Fmin 0,1X1 0,4X2 0X3 0,9X4 0,3X6 0X7 0X8 0X9

MY1 MY2 MY3 и нвг ббвг га габ мл б-в. Решение смотри в таблице 2. На 5-й итерации получено оптимальное решение, т.к. в индексной строке отсутствуют положительные элементы. Чтобы получить 480 заго- товок по 1,6 м, 760 по 1,3 м, 180 по 3,6 м нужно разрезать 150 пру- тков по 11 м на 2 по 1,6 м и 6 по 1,3 м каждый и 90 прутков на 2 по 1,6 м и 2 по 3,6 м каждый. При этом получается перевыполнение плана по изготовлению заготовок по 1,3

м на 140 шт. Для проверки подставим полученные Х в таблицу 1. 2 150 300 по 1,6 2 90 180 по 1,6 6 150 900 по 1,3 2 90 180 по 3,6 Действительно, план по всем заготовкам выполняется. Решение верное. Wобщ общий объем раскраиваемого материала. Wзат общий объем затраченного материала. Ки.м коэффициент использования материала. Решение смотри на следующей странице, ниже таблицы 2

L - 14 - Таблица 2. T T T T T T T T T T T T T T 0,1 0,4 0 0,9 0,3 0,6 0 0 0 M M M C B Н X1 X2 X3 X4 X5 X6 X7 X8 X9 Y1Y2Y3 ГДДДЕДДДДЕДЕДДДДЕДДДДЕДДДДЕДДДДЕДДДДЕДДД ДЕДДДДЕДДДДЕДДДДЕДДЕДДЕДД M Y1 480 6 5 2 0 2 2 -1 0 0 1 0 0 M Y2 760 1 2 6 5 3 0 0 -1 0 0 1 0 M Y3 180 0 0 0 1 1 2 0 0 -1 0 0 1 ГДДДЕДДДДЕДЕДДДДЕДДДДЕДДДДЕ Fmin1420 7 7 8 6 6 4 -1 -1 -1 0 0 0

M Y1 0 1 2 -1 0 1 0 0 X3 1 0,5 0 0 0 0 0 M Y3 180 0 0 0 1 1 2 0 0 -1 0 1 ГДДДЕДДДДЕДЕДДДДЕДДДДЕДДДДЕДДДДЕДДДДЕДДД Д Fmin 0 2 4 -1 -1 0 0 0,1 X1 1 0 0 0 0 X3 0 1 0 0 M Y3 180 0 0 0 1 1 2 0 0 -1 1 ГДДДЕДДДДЕДЕДДДДЕДДДДЕДДДДЕДДДДЕДДДДЕДДД ДЕДДДДЕДДДДЕДДД Fmin 180 0 0 0 1 1 2 0 0 -1 0 0,1 X1 1 0 0 0 X3 0 1 0 0,6

X6 90 0 0 0 0,5 0,5 1 0 0 -0,5 ГДДДЕДДДДЕДЕДДДДЕДДДДЕДДДДЕДДДДЕДДДДЕДДД ДЕДДДДЕДДДДЕДДДДЕДДЕДДЕДД Fmin 0 0 0 X8 0 0 1 3 0 X3 3 1 -0,5 0 0 0,6 X6 90 0 0 0 0,5 0,5 1 0 0 -0,5 ГДДДЕДДДДЕДЕДДДДЕДДДДЕДДДДЕДДДДЕДДДДЕДДД ДЕДДДДЕДДДДЕДДДДЕДДЕДДЕДД Fmin 54 -0,1-0,4 0 -0,6 0 0 0 0 -0,3 L Wобщ. 11 149,981 11 90 2639,791 Wзат. 2 149,981 2 90 1,6 6 149,981 1,3 2 90 3,6 2585,791

Ки.м. Wзат. Wобщ. 0,9795 0,98 L - 15 - 8 а гмв в аип з-вбв а аа л л г- чены следующие результаты Значение базиса Fmin 54 X3 ч 150 Д збв бе Г материала для 3 и 6 X8 ч 140 - ал X6 90 ДЩ бб а бап з б бва X1 -0,1 X6 0 X2 -0,4 X7 0 X3 0 X8 0 X4 -0,6 X9 -0,3 X5 0 а а л а гмв вл гз бгой нзб б з зб б з. 5-в ва ж гз в м аи, в б бва вбгвбвгов вмл нвл. вл гзвм 480 - в 1,6 ,

760 1,3 м, 180 по 3,6 м нужно разрезать 150 пру- тков 11 м на 2 по 1,6 м и 6 по 1,3 м каждый и 90 прутков на 2 по 1,6 м и 2 по 3,6 м каждый. При этом получается перевыполнение плана по изготовлению заготовок по 1,3 м на 140 штук. Для проверки подставим полученные результаты в таблицу 1. 2 150 по 1,6 2 90 1,6 480 6 150 1,3 900 - ал 140 ивг 2 90 по 3,6 180 Действительно, план по всем заготовкам выполняется. Решение верное. L - 16 - 9 п аа зм абв гаавлении, и не требует специ- альных знаний от пользователя.

После включения ПЭВМ и начальной загрузки операционной системы MS-DOS, следует загрузить экранный руссификатор если он еще не загружен, иначе пользователь не сможет прочесть подсказки при вводе данных, просмотре промежуточных и конечного результатов. Запустить на выполнение файл KURS.EXE . На экране появится табличка с информацией о программе, об авто- рах и название метода. Следует нажать любую клавишу.

Дальше про- грамма попросит пользователя ввести количество уравнений в системе, количество основных, дополнительных и искуственных переменных. Следует ввести последовательно ЦЕЛЫЕ числа, заканчивая ввод клави- шей Enter . Дальше, по запросу программы, следует ввести по- следовательно коэффициенты, стоящие при Х в целевой функции. Дальше программа попросит ввести свободные члены ко всем уравнениям и коэф- фициенты при X и Y, стоящие в каждом уравнении.

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

Продолжим YN. Если данные введены правильно и промежуточные результаты схожи с теоретическими, следует ответить клавишами Y Если поль- зователь хочет прервать вычислительный процесс, следует ответить так N Вообще программу можно прервать в любом месте комбинацией клавиш Ctrl Break. Вычислительный процесс будет продолжатся до тех пор, пока не будет получено оптимальное решение. В этом случае будет подан звуковой сигнал и на экране отобразится информация на какой итерации

получено оптимальное решение, значение функции, значение индексной строки и приглашение Нажмите любую L - 17 - клавишу. После нажатия любой клавиши программа закончит свою работу и вернет пользователя в MS-DOS. Данная программа не является универсальной. Программа оптимизиру- ет функции только на минимум. Функция и система уравнений должны быть приведены к кононическому виду.

Данные для решения задачи удобнее всего вводить прямо с таблицы, которую используют при решении системы уравнений Симплекс-методом ручным способом. L - 18 - Малик Г.С. Основы экономики и математические методы в планировании. Москва Высшая школа 1988г. Кузнецов Ю.Н. Математическое программирование Кузубов В.И. Москва Высшая школа 1980г. Волощенко А.

Б. Фигурнов В.Э. IBM PC для пользователя Москва Финансы и статистика 1994г. Фаронов В.В. Основы Турбо Паскаля 6.0 Москва МВТУ-ФЕСТО ДИДАКТИК 1992г. L - 19 Для решения данной задачи линейного программирования на тему оптимальный раскрой промышленных материалов был использован Симплекс-метод. Решение задачи помогло более глубоко и основательно изучить и укрепить на практике все тонкости и моменты

этого метода. Симплекс-метод действительно является универсальным методом для решения любой задачи линейного программирования. При ходе решения заданной задачи была разработана универсальная программа для решения любой задачи при определении оптимального плана на минимум. Разработка программы помогла более подробно изучить работу опера- торов алгоритмического языка Turbo-Pascal и особенности Симплекс- метода. В результате прогона программы и решения задачи-теста получены

эдентичные результаты, следовательно программа составлена и отлажена правильно. L - 20 Данная программа предназначена для решения задач линейного прог- раммирования на минимум универсальным Симплекс-методом и состоит из следующих основных частей б п аа . бз в ле ббв га б ббвл, в жп дгж б-в, л агвз з а гмв в. гжп test0. аапв з вмле нв б- бва. б в нвл бвм, а й в аа г з- бго , з . гжп testY. аапв з бгбвле але а з бб. б в бвм, а й в , з . ажга indxY. а в бзв б бва в бгз , б бгбвл ал выведены

из базиса. ажга indxX. а в бзв б бва в бгз , б бгбвл ал лл б . ажга maxSt. йв й а з бб максимальный клю- чевой столбец и возвращает в основную программу его местоположение. ажга Str. йв й а з бб озго бваг а й в бго аа г бв а аи ой нв . В листинге программы на языке PASCAL содержатся подробные коммента- рии, которые описывают практически все действия, производимые прог- раммой. L DDA.FRM.

MACFя - 27 - P 2 - 28 - ЪД На тему оптимизация экономических задач, приведенных к кононическому виду, Симплекс - методом. По предмету Математическое моделирование Авторы Горбатов Р.С. и Николаева А.А. С М Р А С Т 1995г. Нажмите любую клавишу L Введите к-во УРАВНЕНИЙ в Вашей системе 3 Введите к-во ОСНОВНЫХ переменных в уравнении 6 Введите к-во

ДОПОЛНИТЕЛЬНЫХ переменных в уравнении3 Введите к-во ИСКУССТВЕНЫХ переменных в уравнении 3 Вводим коэффициенты X ,стоящие в целевой функции X1 .1 X2 .4 X3 0 X4 .9 X5 .3 X6 .6 X7 0 X8 0 X9 0 Вводим свободный член в 1 уравнении 480 Вводим свободный член в 2 уравнении 760 Вводим свободный член в 3 уравнении 180

Вводим коэффициенты при Х и Y,стоящие в уравнении N1 X16 X25 X32 X40 X52 X62 X7-1 X80 X90 Y11 Y20 Y30 - 29 - Вводим коэффициенты при Х и Y,стоящие в уравнении N2 X11 X22 X36 X45 X53 X60 X70 X8-1 X90 Y10 Y21 Y30 Вводим коэффициенты при Х и Y,стоящие в уравнении N3

X10 X20 X30 X41 X51 X62 X70 X80 X9-1 Y10 Y20 Y31 Итерация N1 Значение индексной строки Fmin 1.420E03 X1 7.0E00 X2 7.0E00 X3 8.0E00 X4 6.0E00 X5 6.0E00 X6 4.0E00 X7-1.0E00 X8-1.0E00 X9-1.0E00 Функция НЕ минимизирована Продолжим YNy Итерация N2 Значение индексной строки Fmin 4.067E02

X1 5.67E00 X2 4.3E00 X3 0.0E00 X4-6.67E-01 X5 2.0E00 X6 4.0E00 X7-1.0E00 X8 3.3E-01 X9-1.0E00 Функция НЕ минимизирована Продолжим YN - 30 - Итерация N3 Значение индексной строки Fmin 1.80E02 X1 0.0E00 X2 0.0E00 X3 0.0E00 X4 1.0E00 X5 1.0E00 X6 2.0E00 X7 0.0E00 X8 0.0E00 X9-1.0E00 Функция

НЕ минимизирована Продолжим YNy Итерация N4 Значение индексной строки Fmin 5.4823529412E01 X1 0.0E00 X2-3.2352941177E-01 X3 0.0E00 X4-6.4705882353E-01 X5 0.0E00 X6 0.0E00 X7-1.7647058824E-02 X8 5.8823529412E-03 X9-2.8235294118E-01 Функция НЕ минимизирована Продолжим YN УРА ПОЛУЧИЛОСЬ На 5-й итерации получено оптимальное решение

Значение базиса X8 1.40E02 X3 1.50E02 X6 9.0E01 Fmin 5.40E01 Значение индексной строки X1-1.0E-01 X2-4.0E-01 X3 0.0E00 X4-6.0E-01 X5 0.0E00 X6 0.0E00 X7 0.0E00 X8 0.0E00 X9-3.0E-01 Нажмите любую клавишу FяFA.FRM.MACFA.FRMя - 1 - L O0A.FRM.MACFя