Автор работы: Пользователь скрыл имя, 13 Ноября 2013 в 12:18, курсовая работа
Актуальность данной темы заключается в том, что в процессе производственной деятельности все предприятия сталкиваются с проблемой нехватки сырья, а также с тем, что выпускаемая продукция должна быть адекватна с экономической точки зрения, другими словами, чтобы её можно было выгодно продать, и чтобы она соответствовала запросам покупателя. Учитывая всевозрастающую ограниченность ресурсов, очень важно добиваться их максимально эффективного использования. План должен быть разработан настолько умело, чтобы использование ограниченных ресурсов было оптимальным.
Получаем решение:
X2 = (4, 0, 2, 0, 5, 2) L( X2) = 12
В индексной строке Δj имеются две отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить.
В качестве ключевого столбца следует принять столбец базисной переменной х2, а за ключевую строку взять строку переменной x3, где min (2/(3/2),4/(1/2), 5/(3/2), 2/1) = min (4/3, 8, 10/3, 2 ) = 4/3.
Ключевым элементом является (3/2). Вводим в столбец базисной переменной х2, выводим х3. Составляем симплексную таблицу 3-го шага:
ci |
БП |
3 |
2 |
0 |
0 |
0 |
0 |
L(x) |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
bi | ||
|
2 |
x2 |
0 |
1 |
2/3 |
- 1/3 |
0 |
0 |
4/3 |
3 |
x1 |
1 |
0 |
-1/3 |
2/3 |
0 |
0 |
10/3 |
0 |
x5 |
0 |
0 |
-1 |
1 |
1 |
0 |
3 |
0 |
x6 |
0 |
0 |
-2/3 |
1/3 |
0 |
1 |
2/3 |
Δj |
0 |
0 |
1/3 |
4/3 |
0 |
0 |
38/3 | |
Все оценки свободных переменных Δj ≥ 0, следовательно, найденное опорное решение является оптимальным:
Xопт = (10/3, 4/3, 0, 0, 3, 2/3) L( Xопт) = 38/3
Ответ: Xопт = (10/3, 4/3, 0, 0, 3, 2/3) L( Xопт) = 38/3
При ограничениях:
x1 + 4x2 + 4x3 + x4 = 5
x1 + 7x2 + 8x3 + 2x4 = 9
xj ≥ 0 ( j = 1,2,3,4 )
Определимся с начальным опорным решением.
Наличие единичного базиса в системе ограничений позволяе
В уравнении 1 нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную x5. Очевидно, переменная x5 будет являться базисной переменной, т.к. входит в первое уравнение с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.
Во втором уравнении нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную x6. Очевидно, переменная x6 будет являться базисной переменной, т.к. входит во второе уравнение с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.
x1 + 4x2 + 4x3 + x4 + x5 = 5
x1 + 7x2 + 8x3 + 2x4 + x6 = 9
xj ≥ 0 ( j = 1,2,3,4,5,6 )
Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное решение: Xнач = ( 0 , 0 , 0 , 0 , 5 , 9 ).
Для нахождения начального опорного решения функции L, сначала придется решить вспомогательную задачу.
Введем в рассмотрение вспомогательную функцию W :
W = - x5 - x6
Если максимальное значение вспомогательной функции W равно нулю, т.е. все искусственные переменные обращаются в нуль - это будет свидетельствовать о том, что мы нашли начальное опорное решение функции L.
Функция L и вспомогательная функция W не должны содержать базисных переменных.
Из первого уравнения системы выразим x5 и подставим в выражение функции W, получим:
W = -5 + x1 + 4x2 + 4x3 + x4 - x6
Из второго уравнения системы выразим x6 и подставим в выражение функции W, получим:
W = -14 + 2x1 + 11x2 + 12x3 + 3x4
Значение функции W для начального решения: W (Xнач) = -14
При составлении исходной симплекс таблицы, коэффициенты при переменных функции L записываются с противоположными знаками, а свободный член со своим знаком. Для функции W правило аналогичное.
Составляем симплексную таблицу 1-го шага:
ci |
БП |
1 |
-3 |
-5 |
-1 |
0 |
0 |
L(x) |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
bi | ||
|
0 |
x5 |
1 |
4 |
4 |
1 |
1 |
0 |
5 |
0 |
x6 |
1 |
7 |
8 |
2 |
0 |
1 |
9 |
Δj |
-1 |
3 |
5 |
1 |
0 |
0 |
0 | |
W |
-2 |
-11 |
-12 |
-3 |
0 |
0 |
-14 | |
В качестве ключевого столбца следует принять столбец базисной переменной х3, а за ключевую строку взять строку переменной x6, где min (5/4,9/8) = 9/8.
Ключевым элементом является (8). Вводим в столбец базисной переменной х3, выводим х6. Элементы столбца х6 можно не пересчитывать, так как переменная х6 больше не является базисной. Составляем симплексную таблицу 2-го шага:
ci |
БП |
1 |
-3 |
-5 |
-1 |
0 |
L(x) |
x1 |
x2 |
x3 |
x4 |
x5 |
bi | ||
|
0 |
x5 |
1/2 |
1/2 |
0 |
0 |
1 |
1/2 |
-5 |
x3 |
1/8 |
7/8 |
1 |
1/4 |
0 |
9/8 |
Δj |
-13/8 |
-11/8 |
0 |
-1/4 |
0 |
-45/8 | |
W |
-1/2 |
-1/2 |
0 |
0 |
0 |
-1/2 | |
Получаем:
X1 = ( 0, 0, 9/8, 0, 1/2 ) W( X1) = -1/2
Так как максимальное значение функции W не равно нулю, значит мы пока не нашли опорного решения функции L.
В качестве ключевого столбца следует принять столбец базисной переменной х1, а за ключевую строку взять строку переменной x5, где min ((1/2)/(1/2),(9/8)/(1/8)) = min ( 1, 9) = 1.
Ключевым элементом является (1/2). Вводим в столбец базисной переменной х1, выводим х5. Элементы столбца х5 можно не пересчитывать, так как переменная х5 больше не является базисной. Составляем симплексную таблицу 3-го шага:
ci |
БП |
1 |
-3 |
-5 |
-1 |
L(x) |
x1 |
x2 |
x3 |
x4 |
bi | ||
|
1 |
x1 |
1 |
1 |
0 |
0 |
1 |
-5 |
x3 |
0 |
3/4 |
1 |
1/4 |
1 |
Δj |
0 |
1/4 |
0 |
-1/4 |
-4 | |
W |
0 |
0 |
0 |
0 |
0 | |
Максимальное значение вспомогательной функции W равно нулю, т.е. все искусственные переменные обращаются в нуль - это будет свидетельствовать о том, что мы нашли начальное опорное решение функции L.
Значение функции W для данного решения: W (X2) = 0. Строка W нам больше не нужна.
Получаем:
Xнач = (1, 0, 1, 0) L( Xнач) = -4
В качестве ключевого столбца следует принять столбец базисной переменной х4, а за ключевую строку взять строку переменной x3, где min (1/(1/4)) = 4.
Ключевым элементом является (1/4). Вводим в столбец базисной переменной х4, выводим х3. Составляем симплексную таблицу 4-го шага:
ci |
БП |
1 |
-3 |
-5 |
-1 |
L(x) |
x1 |
x2 |
x3 |
x4 |
bi | ||
|
1 |
x1 |
1 |
1 |
0 |
0 |
1 |
-1 |
x4 |
0 |
3 |
4 |
1 |
4 |
Δj |
0 |
1 |
1 |
0 |
-3 | |
Все оценки свободных переменных Δj ≥ 0, следовательно, найденное опорное решение является оптимальным:
Xопт = (1, 0, 0, 4) L( Xопт) = -3
Ответ: Xопт = (1, 0, 0, 4) L( Xопт) = -3
При ограничениях:
x1 + 2x2 + 3x3 + x4 = 10
2x1 + x3 = 3
x1 + x2 + 2x3 = 6
xj ≥ 0 ( j = 1,2,3,4)
Умножим коэффициенты исходной функции на -1.
G = - x1 -2 x 2 -3 x3 → max
Будем искать наибольшее значение получившийся функции. А чтобы найти минимум функции - получившийся ответ мы должны будем умножить на -1. Определимся с начальным опорным решением. Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:
Переменная x4 входит в первое уравнение с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е x4 - базисная переменная.
Во втором уравнении нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную x5. Очевидно, переменная x5 будет являться базисной переменной, т.к. входит во второе с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.
В третьем уравнении нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную x6. Очевидно, переменная x6 будет являться базисной переменной, т.к. входит в третье уравнение с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.
x1 + 2x2 + 3x3 + x4 = 10
2x1 + x3 + x5 = 3
x1 + x2 + 2x3 + x6 = 6
xj ≥ 0 ( j = 1,2,3,4,5,6)
Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное решение: Xнач = ( 0 , 0 , 0 , 10, 3, 6 ).
Для нахождения начального опорного решения функции L, сначала придется решить вспомогательную задачу.
Введем в рассмотрение вспомогательную функцию W :
W = - x5 – x6
Функция G и вспомогательная функция W не должны содержать базисных переменных.