Выводы

9.1 Выводы.

Данная программа очень эффективна, так как машина выполняет все действия гораздо быстрее, чем человек при ручном счете. Так же во время ручного счета могут произоити ошибки, что приведет к повторному перещитыванию, а у машины, при правильном алгоритме, таких сбоев не бывает (если только "зависает"). Следовательно эта программа во многом облегчает жизнь человеку.

II.       Экономическая часть. Разработка модуля исключения нуль-уравнений в комплексе “Решение задачи линейного программирования”.

1.2 Постановка задачи линейного программирования и задание на разработку модуля.

Рассмотрим задачу оптимального планирования производства [1]. Пусть предприятие выпускает n изделий, для производства которых используется m ингредиентов. Ингредиенты это – детали определенного сортамента, станки, работники, электроэнергия и т.д., иначе говоря, все что требуется для осуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b₁, b₂,…, b_m ), где b_i  - запас i-го ингридиента (i=1,…,m). Задана матрица А, элемент которой a_ij определяет расход i-го ингридиента для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан вектор рыночных цен изделий p=(p₁, p₂,…, p_n), где p - цена j-го изделия (j=1,…,n).

Требуется составить такой план производства х=(х₁, х₂,…, х_n), чтобы при выполнение условий

a11x1 + a12x2 + … + a1nxn £ b1

(1)   a21x1 + a22x2 + … + a2nxn £ b2

…………………………….…………………….

am1x1 + am2x2 + … + amnxn £ bm

xj ³ 0, (j=1,…,n).

достигался максимум функции

	(1')

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

 

Функция Z называется целевой.

i-е ограничение из (1) означает, что нельзя израсходовать i-го ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество W. Переменные, удовлетворяющие условию x_j³0, называются несвободными. В нашей задаче это означает, что при x_j=0 - ничего не производится или при x_j>0 производится некоторое количество изделий.

Переменные, на которые условия неотрицательности не накладываются, называются свободными.

Задача (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), чтобы выполнялись условия:

a11u1 + a21u2 + … + am1um ³ p1

(2)   a12u1 + a22u2 + … + am2um ³ p2

…………………………….…………………….

a1nu1 + a2nu2 + … + amnum ³ pn

ui ³ 0, (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') называется точка множества W, в которой не менее чем n ограничений из (1) обращается в верное равенство. Это - так называемая, угловая точка множества. Для n=2 это - вершина плоского угла.

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

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

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

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

a11x1 + a12x2 + … + a1nxn = b1

…………………………….………………………

(3)   ak1x1 + ak2x2 + … + aknxn = bk

ak+1, 1x1+ak+1, 2x2+…+ak+1, n xn£bk+1

…………………………….………………………

am1x1 + am2x2 + … + amnxn £ bm

xj ³ 0, (j=1,…,n)

 

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

	(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 в виде:

 

0 = a11 (-x1) + a12 (-x2) + … + a1n (-xn) + a1, n+1

…………………………………………………….………………………………………

(4)   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

 

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

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

	-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, n	am+1, 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, n	ak+1, n+1
	……	……………………………				………
um	ym =	am1	am2	…	amn	am, n+1
1	Z =	am+1, n	am+1, 2	…	am+1, n	am+1, n+1

 

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) в другую вершину многогранника 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.