Автор работы: Пользователь скрыл имя, 06 Июня 2012 в 10:39, курсовая работа
Симплекс-метод - это характерный пример итерационных вычислений. используемых при решении большинства оптимизационных задач. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования.
Введение… …..3
1. Теоретическая часть
1.1 Линейное программирование …..3
1.2 Табличный симплекс-метод …..4
2. Вычислительная процедура симплекс-метода
2.1 Нахождение исходного опорного решения общей задачи линейного программирования (I часть симплекса )……………………………………………5
2.2 Переход от найденного опорного решения к лучшему опорному решению (II часть симплекса)……………………………………………………...7
2.3 Метод искусственного базиса……………………………………………....9
3. Программная реализация
3.1. Блок-схема алгоритма ЗЛП …12
3.2. Описание основных процедур и функций …13
3.3 Листинг программы…………………………………………………………15
4. Контрольный пример …26
5.Руководство пользователя……………………………………………………….29
Заключение …32
Список использованной литературы …32
xj≥0, ; bi≥0,
В дальнейшем решается расширенная задача и по результатам её решения находится оптимальное решение исходной задачи или делается вывод о неразрешимости на основании следующих теорем:
Теорема 1. Если в оптимальном плане ={ , , …, , 0…0} расширенной задачи компоненты, соответствующие искусственным переменным, равны нулю, то исходная задача разрешима и её оптимальное решение имеет вид: ={ , , …, }.
Если хотя бы одна компонента, соответствующая
искусственной переменной, отлична
от нуля, то исходная задача не разрешима
из-за несовместимости системы
Теорема 2. Если расширенная задача не имеет оптимального решения, то и исходная задача не имеет решения.
Расширенная задача имеет опорный план:
а значит, её решение может быть найдено симплексным методом. В этом случае симплексная таблица решений расширенной задача имеет две индексные строки.
Оценки рассчитываются так же, как для обычного симплекса, но в первую строку ( ) помещают слагаемые, не содержащие параметра М, а во вторую строку записывают коэффициенты при М. Выбор ведущего элемента производят так же, как в обычном симплексе, но освобождаются от ненужных оценок сначала во второй строке. Причем, если искусственная переменная выводится из базиса, то она не должна быть введена повторно, поэтому в таблице Гаусса в столбце, соответствующем выводимой переменной, ставится прочерк.
После исключения из базиса последней искусственной переменной, вторая оценочная строка не вводится и далее освобождаются от ненужных оценок в первой индексной строке.
Пример . Решить задачу линейного программирования методом искусственного базиса.
Z(x)=2x1+3x2+ 2x3→max
х1 |
− |
х2 |
+ |
х3 |
= |
1 |
х2 |
+ |
х3 |
≤ |
2 | ||
х1 |
+ |
х2 |
+ |
х3 |
≥ |
3 |
xj≥0,
Решение. Приведем задачу к каноническому виду.
Z(x)=2x1+3x2+2 x3+0x4+0 x5→max
х1 |
− |
х2 |
+ |
х3 |
= |
1 | ||||
х2 |
+ |
х3 |
+ |
х4 |
= |
2 | ||||
х1 |
+ |
х2 |
+ |
х3 |
− |
х5 |
= |
3 |
Система уравнений разрешена только относительно переменной х4 во 2 -ом уравнении, поэтому вводим в 1-ое и 2-ое уравнения искусственные переменные х6, х7. Получаем расширенную задачу
х1 |
− |
х2 |
+ |
х3 |
+ |
х6 |
= |
1 | ||||||
х2 |
+ |
х3 |
+ |
х4 |
= |
2 | ||||||||
х1 |
+ |
х2 |
+ |
х3 |
− |
х5 |
+ |
х7 |
= |
3 |
Z(x)=2x1+3x2+2 x3+0x4+0 x5−Mx6−Mx7→max
Начальное опорное решение расширенной задачи:
Составляем симплекс - таблицу.
Баз. переем. |
Сбаз |
План |
2 |
3 |
2 |
0 |
0 |
-М |
-М | |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 | ||||
|
Х4 Х7 |
-M 0 -M |
1 2 3 |
0 1 |
-1 1 1 |
1 1 1 |
0 1 0 |
0 0 -1 |
1 0 0 |
0 | |
0 |
-2 |
-3 |
-2 |
0 |
0 |
0 |
0 | |||
-4 |
-2 |
0 |
-2 |
0 |
1 |
0 |
0 | |||
Х1 Х4 |
2 0 -M |
1 2 2 |
1 0 0 |
-1 2 |
1 1 0 |
0 1 0 |
0 0 -1 |
- - - |
0 1 | |
2 |
0 |
-5 |
0 |
0 |
0 |
- |
0 | |||
-2 |
0 |
0 |
0 |
1 |
- |
0 | ||||
Х1 Х2 |
2 0 3 |
2 1 1 |
1 0 0 |
0 0 1 |
1 1 0 |
0 1 0 |
-1/2 -1/2 |
- - - |
- | |
- |
7 |
0 |
0 |
0 |
0 |
- |
- | |||
Х1 Х5 Х2 |
2 0 3 |
3 2 2 |
1 0 0 |
0 0 1 |
2 2 1 |
1 2 1 |
0 1 0 |
- - - |
- - - | |
- |
12 |
0 |
0 |
5 |
5 |
0 |
- |
- | ||
Оптимальное решение расширенной задачи:
Тогда на основании теоремы 1 оптимальное решение исходной задачи, записанной в каноническом виде, имеет вид:
Без учета дополнительных переменных (балансовых), которые не требовалось находить, окончательно имеем:
3. Программная реализация
3.1 Блок-схема алгоритма программы для решения ЗЛП
3.2.Описание основных процедур и функций
Программа LP состоит из 5 модулей:
- Main – модуль для решения задачи ЛП симплекс-методом
- Parametrs – работа с целевой функцией и ограничениями задачи
- Warning – предупреждение «Целевая функция не задана»
- About – «О программе»
- Child – результат решения задачи ЛП
Блок-схема процедуры
отыскания положительных коэффициентов в главном столбце и наименьшего частного при делении базисных неизвестных на коэффициенты в главном столбце
Информация о работе Задача линейного программирования (симплекс-метод)