Автор работы: Пользователь скрыл имя, 09 Октября 2012 в 11:09, курсовая работа
Небольшое производственное коммерческое предприятие ООО «Вектор»*, расположенное в городе Москва, занимается изготовлением различной фурнитуры для елочных украшений. Специализацией предприятия является производство изделий из цветных недрагоценных металлов, производимых посредством холодной штамповки.
1. Постановка задачи 3
2. Теоретическая часть 6
3. Практическая часть (решение) 10
4. Вывод 16
Список литературы 18
минимизировать z = х1 + х2 + х3 + х4 + х5 + х6 + х7 +х8 + х9 + 0 х10 + 0 х11 + 0 х12
при 3х1 + 2х3 + 2х4 + х5 + х8 + х9 - х10 = 18
3х2 + х3 + 2х5 + 2х6 + х7 + х9 - х11 = 13
х4 + х6 + 2х7 + 2х8 + х9 - х12 = 12
х1, х2, х3, х4, х5, х6, х7,х8, х9, х10, х11, х12 0.
В полученной задаче введенные избыточные переменные не позволяют сформировать базисное решение. Поэтому применим М-метод и введем в уравнения системы искусственные переменные R1, R2 и R3, а в целевую функцию добавим штраф MR1 + MR2 + MR3. В результате получим следующую задачу ЛП: минимизировать
z = х1 + х2 + х3 + х4 + х5 + х6 + х7 +х8 + х9 + 0х10 + 0х11 + 0х12 + MR1 + MR2 + MR3
при выполнении условий 3х1 + 2х3 + 2х4 + х5 + х8 + х9 - х10 + R1 = 18
3х2 + х3 + 2х5 + 2х6 + х7 + х9 - х11 + R2 = 13
х4 + х6 + 2х7 + 2х8 + х9 - х12 + R3 = 12
х1, х2, х3, х4, х5, х6, х7,х8, х9, х10, х11, х12, R1, R2, R3 0.
В этой модифицированной задаче переменные R1, R2 и R3 можно использовать в качестве начального допустимого базисного решения. Ранг матрицы, образуемой из коэффициентов при переменных, равен 3, количество свободных переменных – 3, количество базисных переменных (15 - 3 = 12). Функцию переписываем в виде
z - х1 - х2 - х3 - х4 - х5 - х6 - х7 - х8 - х9 - 0х10 - 0х11 - 0х12 - MR1 - MR2 - MR3 = 0.
В результате получим следующую симплекс - таблицу:
Базис |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
х11 |
х12 |
R1 |
R2 |
R3 |
Ответ |
z |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
-М |
-М |
-М |
0 |
R1 |
3 |
0 |
2 |
2 |
1 |
0 |
0 |
1 |
1 |
-1 |
0 |
0 |
1 |
0 |
0 |
18 |
R2 |
0 |
3 |
1 |
0 |
2 |
2 |
1 |
0 |
1 |
0 |
-1 |
0 |
0 |
1 |
0 |
13 |
R3 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
1 |
0 |
0 |
-1 |
0 |
0 |
1 |
12 |
Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с остальной частью таблицы. Значение функции z, соответствующее начальному базисному решению R1=18, R2=13, R3=12, должно равняться 18М + 13М + 12М = 43М, а не 0, как показано в таблице. Это противоречие связано с тем, что переменным R1, R2 и R3 соответствуют ненулевые коэффициенты (-М, -М, -М) в z-строке. Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк R1, R2 и R3 на величину М.
Базис |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
х11 |
х12 |
R1 |
R2 |
R3 |
Ответ |
z-стар |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
-М |
-М |
-М |
0 |
МхR1 |
3М |
0 |
2М |
2М |
М |
0 |
0 |
М |
М |
-М |
0 |
0 |
М |
0 |
0 |
18М |
МхR2 |
0 |
3М |
М |
0 |
2М |
2М |
М |
0 |
М |
0 |
-М |
0 |
0 |
М |
0 |
13М |
МхR3 |
0 |
0 |
0 |
М |
0 |
М |
2М |
2М |
М |
0 |
0 |
-М |
0 |
0 |
М |
12М |
Затем сложить эти строки со старой z-строкой по формуле:
Новая z-строка = старая z-строка + МхR1–строка + МхR2–строка + МхR3–строка Измененная симплекс – таблица примет следующий вид:
Базис |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
х11 |
х12 |
R1 |
R2 |
R3 |
Ответ |
z-нов |
3М-1 |
3М-1 |
3М-1 |
3М-1 |
3М-1 |
3М-1 |
3М-1 |
3М-1 |
3М-1 |
-М |
-М |
-М |
0 |
0 |
0 |
43М |
R1 |
3 |
0 |
2 |
2 |
1 |
0 |
0 |
1 |
1 |
-1 |
0 |
0 |
1 |
0 |
0 |
18 |
R2 |
0 |
3 |
1 |
0 |
2 |
2 |
1 |
0 |
1 |
0 |
-1 |
0 |
0 |
1 |
0 |
13 |
R3 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
1 |
0 |
0 |
-1 |
0 |
0 |
1 |
12 |
Эта таблица готова к применению симплекс – метода с использованием условий оптимальности и допустимости. Поскольку необходимо минимизировать целевую функцию, находим наибольший положительный коэффициент в z-строке. Коэффициенты при переменных с х1 по х9 одинаковые и равны (3М-1), выбор переменной делаем произвольно и выбираем х1, это будет вводимая в базис переменная и ведущий столбец. Исключаемой из базиса переменной является R1 (только для нее выполняется условие допустимости – отношение решения к положительному элементу ведущего столбца), это ведущая строка. Ведущий элемент находится на пересечении ведущей строки и ведущего столбца. Новую симплекс - таблицу определяем с помощью метода Жордана – Гаусса.
Новая ведущая строка = текущая ведущая строка / ведущий элемент.
х1 = (3 0 2 2 1 0 0 1 1 -1 0 0 1 0 0 18) / 3 = (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0 6)
Новая строка = текущая строка – (ее коэффициент в ведущем столбце х новую ведущую строку).
z-строка: (3М-1 3М-1 3М-1 3М-1 3М-1 3М-1 3М-1 3М-1 3М-1 -М -М -М 0 0 0 43М) –
- (3М-1) х (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0 6) =
= ( 0 3М-1 М-1/3 М-1/3 2М-2/3 3М-1 3М-1 2М-2/3 2М-2/3 -1/3 -М -М 1/3-М 0 0 25М+6)
R2 = (0 3 1 0 2 2 1 0 1 0 -1 0 0 1 0 13) – 0 х (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0 6) =
= (0 3 1 0 2 2 1 0 1 0 -1 0 0 1 0 13)
R3 = (0 0 0 1 0 1 2 2 1 0 0 -1 0 0 1 12) – 0 х (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0 6) =
= (0 0 0 1 0 1 2 2 1 0 0 -1 0 0 1 12)
Базис |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
х11 |
х12 |
R1 |
R2 |
R3 |
Ответ |
z |
0 |
3М-1 |
М-1/3 |
М-1/3 |
2М-2/3 |
3М-1 |
3М-1 |
2М-2/3 |
2М-2/3 |
-1/3 |
-М |
-М |
1/3-М |
0 |
0 |
25М+6 |
х1 |
1 |
0 |
2/3 |
2/3 |
1/3 |
0 |
0 |
1/3 |
1/3 |
-1/3 |
0 |
0 |
1/3 |
0 |
0 |
6 |
R2 |
0 |
3 |
1 |
0 |
2 |
2 |
1 |
0 |
1 |
0 |
-1 |
0 |
0 |
1 |
0 |
13 |
R3 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
1 |
0 |
0 |
-1 |
0 |
0 |
1 |
12 |
Далее порядок действий повторяется. Находим наибольший положительный коэффициент в z-строке. Коэффициенты при переменных х2, х6, х7 одинаковые и равны (3М-1), выбор переменной делаем произвольно и выбираем х2, это будет вводимая в базис переменная и ведущий столбец. Исключаемой из базиса переменной является R2 (только для нее выполняется условие допустимости – отношение решения к положительному элементу ведущего столбца), это ведущая строка.
Новая ведущая строка = текущая ведущая строка / ведущий элемент.
х2 = (0 3 1 0 2 2 1 0 1 0 -1 0 0 1 0 13) / 3 = (0 1 1/3 0 2/3 2/3 1/3 0 1/3 0 -1/3 0 0 1/3 0 13/3)
Новая строка = текущая строка – (ее коэффициент в ведущем столбце х новую ведущую строку).
z-строка:(0 3М-1 М-1/3 М-1/3 2М-2/3 3М-1 3М-1 2М-2/3 2М-2/3 -1/3 -М -М 1/3-М 0 0 25М+6)
– (3М-1) х (0 1 1/3 0 2/3 2/3 1/3 0 1/3 0 -1/3 0 0 1/3 0 13/3) =
= (0 0 0 М-1/3 0 М-1/3 2М-2/3 2М-2/3 М-1/3 -1/3 -1/3 -М 1/3-М 1/3-М 0 12М+31/3)
х1 = (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0 6) – 0 х (0 1 1/3 0 2/3 2/3 1/3 0 1/3 0 -1/3 0 0 1/3 0 13/3) = (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0 6)
R3 = (0 0 0 1 0 1 2 2 1 0 0 -1 0 0 1 12) – 0 х (0 1 1/3 0 2/3 2/3 1/3 0 1/3 0 -1/3 0 0 1/3 0 13/3) =
= (0 0 0 1 0 1 2 2 1 0 0 -1 0 0 1 12)
Строим новую симплекс - таблицу.
Базис |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
х11 |
х12 |
R1 |
R2 |
R3 |
Ответ |
z |
0 |
0 |
0 |
М-1/3 |
0 |
М-1/3 |
2М-2/3 |
2М-2/3 |
М-1/3 |
-1/3 |
-1/3 |
-М |
1/3-М |
1/3-М |
0 |
12М+31/3 |
х1 |
1 |
0 |
2/3 |
2/3 |
1/3 |
0 |
0 |
1/3 |
1/3 |
-1/3 |
0 |
0 |
1/3 |
0 |
0 |
6 |
х2 |
0 |
1 |
1/3 |
0 |
2/3 |
2/3 |
1/3 |
0 |
1/3 |
0 |
-1/3 |
0 |
0 |
1/3 |
0 |
13/3 |
R3 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
1 |
0 |
0 |
-1 |
0 |
0 |
1 |
12 |
Информация о работе Решение задачи линейного программирования с использованием симплекс - метода