Мегаобучалка Главная | О нас | Обратная связь

Характеристика симплекс-метода




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

Общий вид задачи, решаемой симплекс-методом, следующий:

при ограничениях, которые могут быть представлены в виде равенств:

………………………...

и неравенств:

.

Основная идея симплекс-метода состоит в следующем:

1 принимается за базу одна из возможных программ – отправная (опорный план);

2 осуществляется её пошаговое улучшение, пока не будет получен оптимум по заданной критериальной функции.

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

Решение задач симплекс-методом предусматривает выполнение следующих процедур:

1 Формирование целевой функции;

2 Определение ограничительных условий – функциональных ограничений, которые могут иметь вид неравенств,

3 Преобразование ограничений из неравенств в систему равенств путём ввода вспомогательных, свободных переменных;

4 Построение исходной симплексной таблицы-матрицы, в которой в формируемый план входят только свободные переменные;

5 Ввод в исходный вариант плана реальных переменных и прежде всего тех, которые в наибольшей степени реализуют целевую функцию;



6 Определение числового значения вводимой переменной – величины программы.

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

Пересчёт строки ведётся по генеральному или базовому элементу, находящемуся на пересечении вводимой и выводимой переменных. Каждый элемент вводимой строки необходимо разделить на генеральный элемент. Все остальные элементы матрицы пересчитываются по столбцам по следующим правилам:

1 Значения столбцов, в которых в строке генерального элемента стоит ноль, переносятся без изменения;

2 При пересчёте остальных столбцов необходимо из первоначального значения соответствующих элементов вычесть произведение элемента вводимой строки этого столбца на соответствующий коэффициент в столбце генерального элемента.

Непосредственно в курсовой работе применяется двойственный симплекс-метод, придуманный в 1954 г. Этот метод даёт преимущество в тех случаях, когда ограничения имеют вид – меньше или равно. В этом случае не требуются искусственные переменные, уменьшается размер симплексной таблицы, упрощается и ускоряется решение. Суть метода такова: вводят дополнительные переменные для придания системе канонического вида, затем для получения недопустимого базисного решения все элементы ограничений умножаются на -1. Строится симплексная таблица (обычным образом). Находится допустимое и оптимальное решение.

При построении второй и последующей симплексных таблиц при поиске ключевой строки находится минимум отношения элементов b – столбца к элементам ключевого столбца, если эти элементы одного знака. Для поиска ключевого столбца находится минимальное отношение элемента z – строки к отрицательным элементам ключевой строки.

Обозначаем через xij количество единиц j-го материала, раскраиваемых по i-му способу (всего таких переменных будет p * s). Переменные xij , очевидно, должны удовлетворять ограничениям:

Xij ≥0 (i=1, 2, … , p и j=1, 2, … , s),

Где x – число комплектов изготавливаемых изделий.

Задача заключается в максимизации z = x при условиях первых двух формул.

Дальнейшее решение задачи проводится симплексным методом. В частном случае, когда на обработку поступает материал только одного образца (т.е. s=1), в количестве a единиц, модель принимает более простой вид: максимизировать z=j при условиях:

xi≥0 (i=1, 2, … , p),

 





Читайте также:





Читайте также:
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной...

©2015 megaobuchalka.ru Все права защищены авторами материалов.

Почему 3458 студентов выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.004 сек.)