Реферат: Аппроксимация

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

v_j = a_1j u₁ + a_2j u₂ + … + a_mj u_m + a_{m+1, j} ³ 0, если x_j ³ 0

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

0=a_1j u₁ + a_2j u₂ + … + a_mj u_m + a_{m+1, j}

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

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

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

W= a_{1, n+1} u₁ + a_{2, n+1} u₂ + … + a_m, n+1 u_m + a_{m+1, n+1}

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

max Z = min W = a_{m+1, n+1}

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

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

Обсудим исходные данные (текстовой файл simp.dat) и результаты решения задачи линейного программирования (текстовой файл simp.res). В начале файла simp.dat расположены, так называемые, представительские данные - строковые данные, каждое из которых распологается в файле с новой строки:

1. Строка с номером варианта,

2. Строка срусским названием модуля,

3. Строка с координатами студента (ФИО, факультет, курс, группа),

4. Строка с датой исполнения.

Далее следуют строки файла с числовыми исходными данными:

1. Управляющий вектор kl - отдельная строка состоящая из трёх чисел kl₁ , kl₂ , kl₃ :

kl₁ =0, если необходимо получить решение только прямой задачи.

kl₁ =1, если необходимо получить решение только двойственной задачи.

kl₁ =2, если необходимо получить решение обеих задач.

kl₂ =0, если нет свободных переменных, иначе kl₂ равен числу этих нуль-уравнений.

2. Число ограничений и переменных (отдельная строка ввода).

3. Коэффициенты расширенной матрицы a, начиная с отдельной строки ввода.

4. Вектор номеров свободных переменных, если они есть, начиная с отдельной строки ввода.

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

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

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

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

3.2 Описание модуля типов.