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