Автор работы: Пользователь скрыл имя, 21 Ноября 2010 в 22:06, Не определен
Целью данной курсовой работы является решение конкретной задачи линейного программирования. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования
Так
как базисные переменные x6 и x7 имеют
ненулевые коэффициенты в (z - c) – строке,
эту строку следует преобразовать:
(z - c): 0 0 0 0 0 -1 -1 0
+
1 * x6: 3 -1 0 -1 0 1 0 0
+
1 * x7: 1 1 0 0 -1 0 1 4
= (z - c): 4 0 0 -1 -1 0 0 4
| Базис | x1 | x2 | x3 | x4 | x5 | x6 | x7 | Решение | Отношение |
| x3 | 1 | -4 | 1 | 0 | 0 | 0 | 0 | 4 | 4 |
| x6 | 3 | -1 | 0 | -1 | 0 | 1 | 0 | 0 | 0 ← |
| x7 | 1 | 1 | 0 | 0 | -1 | 0 | 1 | 4 | 4 |
| (z - c)’ | 4 | 0 | 0 | -1 | -1 | 0 | 0 | 4 |
↑
| Базис | x1 | x2 | x3 | x4 | x5 | x6 | x7 | Решение | Отношение |
| x3 | 0 | -3 и 2/3 | 1 | 1/3 | 0 | -1/3 | 0 | 4 | |
| x1 | 1 | -1/3 | 0 | -1/3 | 0 | 1/3 | 0 | 0 | |
| x2 | 0 | 1 и 1/3 | 0 | 1/3 | 1 | -1/3 | 1 | 4 | 3 ← |
| (z - c)’ | 0 | 4/3 | 0 | 1/3 | -1 | -4/3 | 0 | 4 |
↑
| Базис | x1 | x2 | x3 | x4 | x5 | x6 | x7 | Решение | Отношение |
| x3 | 0 | 0 | 1 | 5/4 | 11/4 | -5/4 | 11/4 | 4 | |
| x1 | 1 | 0 | 0 | -1/4 | 1/4 | 1/4 | 1/4 | 0 | |
| x2 | 0 | 1 | 0 | 1/4 | 3/4 | -1/4 | 3/4 | 4 | |
| (z - c)’ | 0 | 0 | 0 | 0 | -2 | -5/3 | -1 | 4 |
Так как достигнуто
min (z - c)’ = 0, то получено допустимое базисное
решение для второго этапа: x1 = 1, x2 = 3, x3 = 15. Искусственные переменные
могут быть исключены.
Этап 2.
Перепишем исходную задачу с учётом полученного базисного решения:
f = x1 + x2 + 0x3 + 0x4 + 0x9 →
max
x3 + 5/4 x4 + 11/4 x5 = 15;
x1 – 1/4 x4 + 1/4 x5 = 1;
x2 + 1/4 x4 + 3/4 x5 = 3;
x1, x2, x3, x4, x5 >= 0.
| Базис | x1 | x2 | x3 | x4 | x5 | Решение |
| x1 | 1 | 0 | 0 | 1/4 | 1/4 | 1 |
| x2 | 0 | 1 | 0 | 1/4 | 3/4 | 3 |
| x3 | 0 | 0 | 1 | 5/4 | 11/4 | 15 |
| (f - c) | 1 | -1 | 0 | 0 | 0 | 0 |
Согласуем значения
в строке (f - c) с остальной частью таблицы:
(f - c): -1 -1 0 0 0 0
+
1 * x1: 1 0 0 -1/4 1/4 1
+
1 * x2: 0 1 0 1/4 3/4 3
= (f-c)’: 0 0 0 0 1 4
Исходное решение
является оптимальным.
Ответ: max (f) = 4 при x1 = 1, x2 = 3, x3 = 15, x4 = 0, x5 = 0.
Так как небазисные
переменные равны нулю, задача имет
множество альтернативных оптимальных
решений, находящихся н отрезке
AB (x1+
x2
= 4).
Заключение.
Симлекс-метод – это характерный пример итерационных вычислений. используемых при решении большинства оптимизационных задач.
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки (обычно начало координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Из
теоретических положений, лежащих в основе
симплекс-метода, следует, что оптимальное
решение задачи линейного программирования
соответствует крайней точке пространства
допустимых решений задачи. В свою очередь,
крайние точки пространства допустимых
решений полностью определяются базисными
решениями задачи ЛП, представленной
в стандартной форме. Для компьютерной
реализации симплекс-метода разработан
способ использования искусственных переменных,
что позволяет найти начальное базисное
решение задачи. В этой главе также рассмотрены
теоретические и практические аспекты
особых случаев реализации симплекс-метода:
вырожденность, альтернативные оптимальные
решения, неограниченность и отсутствие
допустимых решений.
Литература.