Решение задачи линейного программирования с использованием симплекс - метода

Департамент образования  города Москвы

 

Московский государственный  институт

делового администрирования

 

 

 

 

 

 

 

Дисциплина: «Прикладная математика»

 

 

Курсовая работа

 

 

 

Решение задачи линейного  программирования

 

с использованием симплекс - метода

 

 

 

 

 

 

Выполнила:

студентка группы 21МЭ

Гусаковская Татьяна

Александровна

 

 

Проверила:

доцент

Платонова Ирина

Вячеславовна

 

 

 

 

Москва, 2007 г.

ОГЛАВЛЕНИЕ

 

1. Постановка задачи                                                                                3

2. Теоретическая часть                                                                              6

3. Практическая часть (решение)                                                            10

4. Вывод                                                                                                     16

Список литературы                                                                                  18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Постановка  задачи.

Небольшое производственное коммерческое предприятие ООО «Вектор»*, расположенное в городе Москва, занимается изготовлением различной фурнитуры для елочных украшений. Специализацией предприятия является производство изделий из цветных недрагоценных металлов, производимых посредством холодной штамповки.

Предприятие получило заказ на изготовление партии колпачков для елочных шаров. Для выполнения заказа применяется материал – алюминий в рулонах стандартизированной шириной 100 миллиметров. Длина рулона составляет около 1500 метров.

Заказ составлен из трех изделий, соответствующего количества:

• колпачок №1 – 900 тыс.шт.,
• колпачок №2 – 600 тыс.шт.,
• колпачок №3 – 500 тыс.шт.

Для вырубки одного изделия  используется квадратная заготовка размером 30 х 30мм, 32 х 32мм, 34 х 34мм соответственно.

Таким образом, для выполнения полученного  заказа ООО «Вектор» должно произвести раскрой стандартных рулонов шириной 100мм на соответствующие полосы. Раскрой производится ножами гильотинного типа без перемотки ленты (сразу всего рулона). Потребность в рулонах заданной ширины представлена в таблице 1.1.

 

^{____________________________________________________________________________________________________________________________________________________}

^* Наименование организации изменено.

Таблица 1.1.

Изделие	Заказ	Ширина рулона	Потребность в рулонах
Колпачок №1	900 тыс.шт.	30мм	18 рулонов
Колпачок №2	600 тыс.шт.	32мм	13 рулонов
Колпачок №3	500 тыс.шт.	34мм	12 рулонов

 

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

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

Математическая постановка задачи.

Найдем комбинацию вариантов  разрезки рулонов (переменные), с помощью  которой можно было бы выполнить  заказ (ограничения) с минимальными отходами материала (целевая функция).

Определим переменные как  количество стандартных рулонов х_i, разрезанных с помощью конкретных вариантов (таблица 1.2), где i=1,2,…,9.

Таблица 1.2.

Вариант/ размер	№1	№2	№3	№4	№5	№6	№7	№8	№9	Кол-во рулонов
30	3	-	2	2	1	-	-	1	1	18
32	-	3	1	-	2	2	1	-	1	13
34	-	-	-	1	-	1	2	2	1	12
Остаток, мм	10	4	8	6	6	2	-	2	4

 

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

3х₁ + 2х₃ + 2х₄ + х₅ + х₈ + х₉ 18

3х₂ + х₃ + 2х₅ + 2х₆ + х₇ + х₉ 13

х₄ + х₆ + 2х₇ + 2 х₈ + х₉ 12

Также количество рулонов  х_i - число неотрицательное, х_i 0

Для удобства вычисления примем площадь поперечного сечения  рулона алюминия = L (мм²).

Отходы при раскрое  металла рассчитываются как разность между всеми использованными рулонами 100 L(х₁ + х₂ + х₃ + х₄ + х₅ + х₆ + х₇ +х₈ + х₉) и объемом заказанных рулонов L(18 х 30 + 13 х 32 + 12 х 34) = 1364L. Поскольку площадь поперечного сечения рулона L и объем заказанных рулонов – постоянные величины, целевую функцию можно записать:

z = х₁ + х₂ + х₃ + х₄ + х₅ + х₆ + х₇ +х₈ + х₉

Таким образом, формулируем  задачу линейного программирования:

минимизировать функцию  z = х₁ + х₂ + х₃ + х₄ + х₅ + х₆ + х₇ +х₈ + х₉,

при ограничениях        3х₁ + 2х₃ + 2х₄ + х₅ + х₈ + х₉ 18

3х₂ + х₃ + 2х₅ + 2х₆ + х₇ + х₉ 13

х₄ + х₆ + 2х₇ + 2х₈ + х₉ 12

х₁ 0              х₄ 0                х₇ 0

х₂ 0              х₅ 0                х₈ 0

х₃ 0              х₆ 0                х₉ 0

2. Теоретическая  часть.

Для нахождения оптимальных (экстремальных) решений, связанных  с нахождением максимумов и минимумов  функции, применяются методы линейного программирования (далее ЛП). Поскольку в нашей задаче содержится n-переменных, ее целесообразно решать с использованием симплекс – метода. Оптимальное решение задачи ЛП всегда заключается в нахождении крайней точки множества, это положено в основу алгебраического симплекс – метода.

Основное свойство симплекс – метода заключается в том, что решение задачи ЛП осуществляется итерационно, т.е. на каждом этапе (итерации) алгоритм решения переходит к новой угловой точке пространства, которая потенциально может улучшить значение целевой функции. Этот процесс заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.

Сущность симплекс –  метода заключается в следующем:

1. Целевая функция максимизируется или минимизируется;
2. Все переменные величины неотрицательны (х_i);
3. Ограничения записываются в форме равенств с неотрицательной правой частью;
4. Находится ранг расширенной матрицы системы ограничений, при помощи которого определяется количество свободных и базисных переменных;
5. Переход от начального решения к следующему осуществляется строго о ребрам (только по смежным точкам), пропуск точек и возврат недопустимы. Решение осуществляется посредством составления симплекс – таблиц, в которые заносятся базисные и свободные переменные, а также решение, соответствующее данной интерации.

Для построения симплекс – таблицы необходимо выполнение целевой оптимальности и допустимости, применяется метод последовательных исключений Жордана-Гаусса.

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

Процесс вычисления нового базисного решения (по методу Жордана-Гаусса) состоит из двух этапов.

1. Вычисление элементов новой ведущей строки:

Новая ведущая строка = текущая ведущая строка / ведущий  элемент.

2. Вычисление элементов остальных строк, включая z-уравнение:

Новая строка = текущая  строка – (ее коэффициент в ведущем столбце х новую ведущую строку).

Если в z-уравнении все коэффициенты примут неотрицательные (не- положительные) значения, такое решение и будет являться оптимальным.

Алгоритм  решения.

1. Преобразование неравенств  в равенства, введение неотрицательных остаточных или избыточных переменных (для максимизации и минимизации соответственно). Задание пространства решений посредством системы из m линейных уравнений с n неотрицательными переменными, причем m < n.

2. Нахождение начального допустимого базисного решения.

3. На основе условия оптимальности определяется вводимая в базис переменная. Если вводимых переменных нет, вычисление заканчивается.

4. На основе условия допустимости  выбирается исключаемая из базиса переменная.

5. Методом последовательных  исключений Жордана-Гаусса вычисляется  новое базисное решение.

6. Целевая функция используется для определения оптимального решения среди множества допустимых решений. Если решение не оптимально – переход к пункту 3.

Для задач ЛП с системой ограничений в виде равенств и  неравенств типа для построения начального допустимого базисного решения вводятся искус-

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

Суть М-метода заключается  в следующем: для любого i равенства, в котором не содержится дополнительная остаточная переменная, вводится искусственная переменная Ri, которая войдет в начальное базисное решение. Так как переменная Ri искусственная и не содержит «физического» смысла, то для дальнейшего обращения ее в нуль в выражение целевой функции вводится штраф. Искусственная переменная Ri с помощью достаточно большого положительного числа М штрафуется путем ввода в целевую функцию выражения «- М Ri» (в задаче максимизации) или «+ М Ri» (в задаче минимизации). Теоретически величина М бесконечно большое число, на практике величина М должна быть достаточно большой, чтобы выполнять роль штрафа, но не слишком большой, чтобы не уменьшить точность вычислений.

Далее надо согласовать  значения в z-строке с остальной частью таблицы, поскольку переменным Ri соответствуют ненулевые коэффициенты возникает противоречие в значении функции z. Необходимо выполнить следующие вычисления:

Новая z-строка = старая z-строка + М х Ri – строку.

Далее применяется симплекс-метод.

 

3. Практическая  часть (решение).

Наша задача на минимизацию целевой функции (заданы нижние границы необходимых материалов), поэтому для преобразования неравенств в равенства вводим избыточные переменные, определяющие превышение значения левой части неравенства над заданной нижней границей. Для трех неравенств это будут три дополнительные переменные: х₁₀, х₁₁ и х₁₂. Надо заметить, что дополнительные переменные всегда неотрицательные (х₁₀ 0; х₁₁ 0; х₁₂ 0). Таким образом,