Реферат: Аппроксимация
Тогда 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) в другую вершину многогранника W по его ребру. Элемент а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.
3.2 Описание модуля типов.