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


	Загрузить архив:
	Файл: 240-0061.zip (19kb [zip], Скачиваний: 123) скачать

М о с к о в с к и й

радиоаппаратостроительный

т е х н и к у м

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] │

│ │

│1) [1]/ bij * Xj Є Bj i=(1,2,...,m) │

│ │

│ j=1 │

│ │

│ 2) Xj Є 0 │

│ │

│ ЦЕЛЕВАЯ ФУНКЦИЯ: │

│ n │

│ [1] │

│ │

│3)F = [1]/ 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,1│0,4│ 0 │0,9│0,3│0,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 поколения. В середине │

│ │

│ 80-х годов фирма Borland выпустила язык Turbo PASCAL для персональных│

│ │

│ компьютеров, который обладал удобной интерактивной оболочкой. Язык │

│ │

│ сразу же завоевал огромную популярность. Объясняется это сочетанием│

│ │

│ двух безусловных его достоинств: исключительной простотой и естест-│

│ │

│ венностью языка и великолепными сервисными возможностями диалоговой│

│ │

│ среды программирования. Последняя версия Турбо Паскаля 7.0 представ- │

│ │

│ ляет собой мощную, гибкую, удобную и почти универсальную систему │

│ │

│ программирования с удобной интерактивной оболочкой, с большим коли-│

│ │

│ чеством сервисных возможностей. Сам язык программирования сильно │

│ │

│ изменен и доработан, по сравнению с первой версией. │

│ │

│ С помощью Турбо Паскаля можно создавать любые программы - от про-│

│ │

│ грамм, предназначенных для решения простейших вычислительных задач,│

│ │

│ до сложных современных систем управления базами данных и операционных│

│ │

│ систем. │

│ │

│- 13 - │

│ │

│ 7.РЕШЕНИЕ ЗАДАЧИ-ТЕСТА │

│ │

│ По таблице 1 строим систему линейных уравнений : │

│ │

│┌─ 6X1 + 5X2 + 2X3 + 2X5 + 2X6 Є 480 │

││ │

│ < X1 + 2X2 + 6X3 + 5X4 + 3X5 Є 760 Xj Є 0 │

││ │

│└─ 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) │

│ │

│- 14 - │

│ │

│ Таблица 2.│

│┌───┬────┬─────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬──┬──┬──┐│

││ │ │ │ 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 │Y1│Y2│Y3││

│├───┼────┼─────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼──┼──┼──┤│

││ 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 ││

││ ! │Fmin│1420 │ 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│││ ││

│└───┴────┴─────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴──┴──┴──┘│

│ │

│ 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 │

│ │

│- 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 │

│ │

│Действительно, план по всем заготовкам выполняется. Решение верное. │

│ │

│- 16 - │

│ │

│ 9. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ. │

│ │

│ Данная программа очень проста в управлении, и не требует специ- │

│ │

│альных знаний от пользователя. │

│ │

│ После включения ПЭВМ и начальной загрузки операционной системы │

│ │

│MS-DOS, следует загрузить экранный руссификатор (если он еще не │

│ │

│загружен), иначе пользователь не сможет прочесть подсказки при │

│ │

│вводе данных, просмотре промежуточных и конечного результатов. │

│ │

│Запустить на выполнение файл KURS.EXE . │

│ │

│ На экране появится табличка с информацией о программе, об авто- │

│ │

│рах и название метода. Следует нажать любую клавишу. Дальше про- │

│ │

│грамма попросит пользователя ввести количество уравнений в системе, │

│ │

│количество основных, дополнительных и искуственных переменных. │

│ │

│Следует ввести последовательно ЦЕЛЫЕ числа, заканчивая ввод клави-│

│ │

│шей Enter ( ─┘ ). Дальше, по запросу программы, следует ввести по- │

│ │

│следовательно коэффициенты, стоящие при Х в целевой функции. Дальше │

│ │

│программа попросит ввести свободные члены ко всем уравнениям и коэф-│

│ │

│фициенты при X и Y, стоящие в каждом уравнении. Ввод производить │

│ │

│последовательно, заканчивать ввод следует клавишей Enter. │

│ │

│ После ввода данных программа начнет оптимизировать функцию, вве-│

│ │

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

│ │

│итерации промежуточные данные. На экран будет выдаватся следующее:│

│ │

│номер итерации, значение функции, индексная строка для всех Х, пре- │

│ │

│дупреждение "Функция НЕ минимизирована" и запрос "Продолжим (Y/N)?".│

│ │

│Если данные введены правильно и промежуточные результаты схожи с │

│ │

│теоретическими, следует ответить клавишами 'Y' + '─┘'. Если поль- │

│ │

│зователь хочет прервать вычислительный процесс, следует ответить │

│ │

│так: 'N' + '─┘'. (Вообще программу можно прервать в любом месте │

│ │

│комбинацией клавиш 'Ctrl' + 'Break'). Вычислительный процесс будет│

│ │

│продолжатся до тех пор, пока не будет получено оптимальное решение. │

│ │

│В этом случае будет подан звуковой сигнал и на экране отобразится │

│ │

│информация: на какой итерации получено оптимальное решение, значение│

│ │

│функции, значение индексной строки и приглашение "Нажмите любую │

│ │

│- 17 - │

│ │

│клавишу!". После нажатия любой клавиши программа закончит свою │

│ │

│работу и вернет пользователя в MS-DOS. │

│ │

│ Данная программа не является универсальной. Программа оптимизиру- │

│ │

│ет функции только на минимум. Функция и система уравнений должны │

│ │

│быть приведены к кононическому виду. │

│ │

│ Данные для решения задачи удобнее всего вводить прямо с таблицы,│

│ │

│которую используют при решении системы уравнений Симплекс-методом │

│ │

│ручным способом. │

│ │

│- 18 - │

│ │

│ СПИСОК ЛИТЕРАТУРЫ: │

│ │

│ Малик Г.С. Основы экономики и математические методы│

│ │

│ в планировании. │

│ │

│ Москва ; "Высшая школа" ; 1988г. │

│ │

│ Кузнецов Ю.Н. │

│ Математическое программирование │

│ Кузубов В.И. │

│ Москва ; "Высшая школа" ; 1980г. │

│ Волощенко А.Б. │

│ │

│ Фигурнов В.Э. IBM PC для пользователя │

│ │

│ Москва ; "Финансы и статистика" ; 1994г. │

│ │

│ Фаронов В.В. Основы Турбо Паскаля6.0 │

│ │

│ Москва ; "МВТУ-ФЕСТО ДИДАКТИК" ; 1992г. │

│ │

│- 19 - │

│ │

│ ЗАКЛЮЧЕНИЕ. ВЫВОДЫ ПО РАБОТЕ. │

│ │

│ Для решения данной задачи линейного программирования на тему │

│ │

│ "оптимальный раскрой промышленных материалов" был использован │

│ │

│ Симплекс-метод. Решение задачи помогло более глубоко и основательно│

│ │

│ изучить и укрепить на практике все тонкости и моменты этого метода.│

│ │

│ Симплекс-метод действительно является универсальным методом для │

│ │

│ решения любой задачи линейного программирования. При ходе решения │

│ │

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

│ │

│ любой задачи при определении оптимального плана на минимум. │

│ │

│ Разработка программы помогла более подробно изучить работу опера- │

│ │

│ торов алгоритмического языка Turbo-Pascal и особенности Симплекс- │

│ │

│ метода. │

│ │

│ В результате прогона программы и решения задачи-теста получены │

│ │

│ эдентичные результаты, следовательно программа составлена и отлажена │

│ │

│ правильно. │

│ │

│- 20 - │

│ │

│ ОПИСАНИЕ ПРОГРАММЫ. │

│ │

│ Данная программа предназначена для решения задач линейного прог-│

│ │

│ раммирования на минимум универсальным Симплекс-методом и состоит │

│ │

│ из следующих основных частей: │

│ │

│ @Основная программа. Обеспечивает ввод данных о системе уравнений│

│ │

│ и ввод самой системы, оптимизация функции Симплекс-методом, вывод │

│ │

│ промежуточного и конечного результатов. │

│ │

│ @Функция test0. Проверяет наличие положительных элементов в индекс-│

│ │

│ ной строке. Если такие элементы есть, возвращает в программу логиче- │

│ │

│ скую 'ЛОЖЬ', иначе 'ПРАВДА'. │

│ │

│ @Функция testY. Проверяет наличие искуственных переменных в рабочем│

│ │

│ массиве. Если такие есть, возвращает 'ЛОЖЬ', иначе 'ПРАВДА'. │

│ │

│ @Процедура indxY. Производит подсчет индексной строки в том случае,│

│ │

│ если искуственные переменные не выведены из базиса. │

│ │

│ @Процедура indxX. Производит подсчет индексной строки в том случае,│

│ │

│ если искуственные переменные выведены из базиса. │

│ │

│ @Процедура maxSt. Ищет в общем рабочем массиве максимальный (клю-│

│ │

│ чевой) столбец и возвращает в основную программу его местоположение. │

│ │

│ @Процедура Str. Ищет в общем рабочем массиве ключевую строку и │

│ │

│ возвращает в основную программу местоположение разрешающего элемента.│

│ │

│ В листинге программы на языке PASCAL содержатся подробные коммента-│

│ │

│ рии, которые описывают практически все действия, производимые прог-│

│ │

│ раммой. │

│ │