Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

|0 = a11 (-x1) + a12 (-x2) + … + a1n |
|(-xn) + a1, n+1 |
|…………………………………………………….……………………………………… |
|0 = ak1 (-x1) + ak2 (-x2) + … + akn|
|(-xn) + ak, n+1 |
|yk+1 = ak+1, 1 (-x1) + ak+1, 2(-x2)+ … + ak+1, |
|n(-xn) + ak+1, n+1 |
|…………………………………………………….……………………………………… |
|ym = am1 (-x1) + am2 (-x2) + … + amn(-xn) |
|+ am, n+1 |
|Z = am+1, 1 (-x1) + am+1, 2(-x2)+ … + am+1, |
|n(-xn) + am+1, n+1 |

Условие несвободности отдельных или всех переменных здесь не отмечено.
Обозначения:

ai, n+1 = bi (i=1, …, m), am+1, j = -pj (j=1, …, n) am+1, n+1 = 0.

Таким образом, матрицу а мы дополнили столбцом свободных членов и строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:

Прямая задача Таблица 1
| |-x1 |-x2 | |-xn |1 |
|0 = |a11 |a12 |… |a1n |a1, n+1|
|…… |…………………………… |……… |
|0 = |.. |ak, n+1|
|yk+1 =|ak1 |ak2 |… |akn |ak+1, |
| | | | | |n+1 |
|…… |ak+1, 1|ak+1, 2|… |ak+1,|……… |
| | | | |n | |
|ym = |…………………………… |……… |
| |am1 |am2 |… |amn |am, n+1|
|Z = |am+1, n|am+1, 2|… |am+1,|am+1, |
| | | | |n |n+1 |

Номера свободных переменных запоминаются отдельно.
Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.

Прямая и двойственная задачи Таблица 2
| | |v1 = |v2 = | |vn = |W = |
| | |-x1 |-x2 | |-xn |1 |
|u1 |0 = |a11 |a12 |… |a1n |a1, n+1 |
| |…… |……………...……………… |……… |
|uk |0 = |ak1 |ak2 |… |akn |ak, n+1 |
|uk+1 |yk+1 =|ak+1, 1|ak+1, 2|… |ak+1,|ak+1, |
| | | | | |n |n+1 |
| |…… |…………………………… |……… |
|um |ym = |am1 |am2 |… |amn |am, n+1 |
|1 |Z = |am+1, n|am+1, 2|… |am+1,|am+1, |
| | | | | |n |n+1 |

vj - вспомогательные переменные двойственной задачи.

Тогда j-е ограничение из таблицы имеет вид:

vj = a1j u1 + a2j u2 + … + amj um + am+1, j ( 0, если xj ( 0

Если переменная xj свободна, то ей соответствует ограничение-равенство двойственной задачи:

0=a1j u1 + a2j u2 + … + amj um + am+1, j

т.е. вместо vj фактически будет нуль.

Кроме того первые k переменных двойственной задачи свободны, а остальные несвободны.

Целевая функция двойственной задачи

W= a1, n+1 u1 + a2, n+1 u2 + … + am, n+1 um + am+1, n+1

Совмещение в одной таблице прямой и двойственной задачи неслучайно.
Решая прямую задачу, мы получаем о дновременно решение двойственной задачи, причем

max Z = min W = am+1, n+1

Сделаем замену переменных в таблице 1 , перебросив вспомогательную переменную yr на верх таблицы со знаком минус, а основную пременную xs на бок таблицы (ars(0). Это означает движение из вершины x=(0, …, 0) в другую вершину многогранника ( по его ребру. Элемент аrs называется разрешающим, строка r - разрешающей строкой, столбец s - разрешающим столбцом. Такая замена переменных носит название модифицированных жордановых исключений
(МЖИ). Элементы матрицы а, не принадлежащие разрешающему столбцу или разрешающей строке, назовем рядовыми.

2.2 Описание исходных данных и результатов решения задачи линейного программирования.

Обсудим исходные данные (текстовой файл simp.dat) и результаты решения задачи линейного программирования (текстовой файл simp.res). В начале файла simp.dat расположены, так называемые, представительские данные - строковые данные, каждое из которых распологается в файле с новой строки:
1. Строка с номером варианта,
2. Строка с русским названием модуля,
3. Строка с координатами студента (ФИО, факультет, курс, группа),
4. Строка с датой исполнения.
Далее следуют строки файла с числовыми исходными данными:
1. Управляющий вектор kl - отдельная строка состоящая из трёх чисел kl1 , kl2 , kl3: kl1=0, если необходимо получить решение только прямой задачи. kl1=1, если необходимо получить решение только двойственной задачи. kl1=2, если необходимо получить решение обеих задач. kl2=0, если нет свободных переменных, иначе kl2 равен числу этих нуль- уравнений.
2. Число ограничений и переменных (отдельная строка ввода).
3. Коэффициенты расширенной матрицы a, начиная с отдельной строки ввода.
4. Вектор номеров свободных переменных, если они есть, начиная с отдельной строки ввода.

Результаты решения зависят от значения kl .

Если kl1=0, то при благоприятном исходе это будет вектор оптимального решения прямой задачи и оптимальное значение целевой функции. При неблагоприятном исходе, это одно из сообщений: либо "Система ограничений несовместна", либо "Целевая функция неограничена".

Если kl2=1, то же для двойственной задачи.

Если kl2=2, то сначала выдается решение прямой, а потом двойственной задачи. При не благоприятном исходе сообщения справедливы только для прямой задачи (для двойственной аналогичные сообщения не выдаются). Результаты помещаются в файл simp.res.

Рекомендуем скачать другие рефераты по теме: сочинение описание, банк курсовых.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата