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