Оптимальный раскрой промышленных материалов
М о с к о в с к и й
радиоаппаратостроительный
т е х н и к у м
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 содержатся подробные коммента- │
│ │
│ рии, которые описывают практически все действия, производимые прог- │
│ │
│ раммой. │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
└──────────────────────────────────────────────────────────────────────┘