44559 (Аппроксимация), страница 3

Задача (1)-(1') и есть задача оптимального производственного планирования, решение которой обеспечивает достижение в конкретных условиях максимальной прибыли.

Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для производства тех же n изделий. При этом количество приобретаемых ингридиентов определяется вектором b=(b₁, b₂, …, b_m). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента для производства j-го изделия. Кроме того задан вектор цен p=(p₁, p₂, …, p_n) на продукцию предприятия. Требуется отыскать вектор цен ингридиентов u=(u₁, u₂, …, u_m), где u_i - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись условия:

при достижении минимума целевой функции

(2')

W=b₁u₁ + … + b_mu_m

j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на производство j-го изделия, не меньше рыночной цены этого изделия.

Условие несвободности u_j0 означает, что j-й ингредиент либо бесплатен (u_j=0), либо стоит положительное количество рублей (u_j >0).

Опорным решением задачи (1)-(1') называется точка множества , в которой не менее чем n ограничений из (1) обращается в верное равенство. Это - так называемая, угловая точка множества. Для n=2 это - вершина плоского угла.

Опорным решением задачи (2)-(2') называется точка, в которой не менее чем m ограничений из (2) обращается в верное равенство.

В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не является.

Опорное решение, доставляющее максимум функции (1') или минимум функции (2') называется оптимальным. В работе [1] показано, что оптимальное решение можно всегда искать среди опорных решений.

Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и равенства. Тогда условимся писать эти равенства первыми. Если их количество равно k, то область  запишется в виде:

Требуется найти максимум функции

(3')

Z=p₁x₁ + p₂x₂ + … + p_nx_n

В общем случае среди переменных x_j могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.

При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная u_i (i=1,…,k), а свободной переменной x_j ограничение - равенство:

a_1j u₁ + a_2j u₂ + … + a_mj u_m =p_j

Введем вспомогательные переменные y_i0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде:

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

a_{i, n+1} = b_i (i=1, …, m),

a_{m+1, j} = -p_j (j=1, …, n)

a_{m+1, n+1} = 0.

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

Прямая задача Таблица 1

Номера свободных переменных запоминаются отдельно.

Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.

Прямая и двойственная задачи Таблица 2

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

Тогда 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) в другую вершину многогранника  по его ребру. Элемент а_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 Описание модуля типов.

Для задания типов и файловых переменных вводного и выводного текстовых файлов используется модуль типов unit typesm, структура которого приведена ниже

unit typesm;

interface