В своей программе я использовал следующие модули, которые описываются в операторе uses и процедуры:
Crt - стандартный модуль подключения экрана и клавиатуры для работы с программой.
Gauss - процедура решения системы линейных уравнений методом Гаусса. Она берется из модуля Gausstpu, где интерфейсная часть имеет вид:
Interface Const nmax=20 Type Поэтому при объявлении матрицы С ссылаться надо на matr, а векторов A и B на vect.
Create_BC - процедура расчета матрицы С (С - матрица системы линейных уравнений для аппроксимации). Заголовок этой процедуры выглядит так:
procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect); var i,j:integer; r:vect;
А вот такие переменные используются только в этой процедуре, остальные засылаются из основной программы:
|Переменная |Тип |Описание переменной | | |переменной | | |i |integer |Используются в циклах для перебора | | | |численных значений | |j |integer |Используются в циклах для перебора | | | |численных значений | |R |vect |Рабочий вектор |
7.1 Ручной счет.
Составляем матрицу системы уравнений по следующему принципу:
|n |(xi |(xi2|(yi | |(xi |(xi2|(xi3|(xiyi| |(xi2 |(xi3|(xi4|(xi2y| | | | |i |
Для этого вычисляем необходимые значения:
n=10; (xi=1+6+0+3+8+2+12+9+2+5=48; (xi2=12+62+02+32+82+22+122+92+22+52=368; (yi=9+4+13+7+3+9+3+1+4+2=55; (xi3=13+63+03+33+83+23+123+93+23+53=3354; (xiyi=1*9+6*4+0*13+3*7+8*3+2*9+12*3+9*1+2*4+5*2=159; (xi3=14+64+04+34+84+24+124+94+24+54=33428; (xi2yi=12*9+62*4+02*13+32*7+82*3+22*9+122*3+92*1+22*4+52*2=1023.
Получается следующая матрица:
|10 |48 |368 |55 | |48 |368 |3354 |159 | |368 |3354 |33428 |1023|
Которая эквивалентна такой системе уравнений:
10a1 + 48a2 + 368a3 = 55
48a1 + 368a2 + 3354a3 = 159
368a1 + 3354a2 + 33428a3 = 1023
Мы решаем эту систему уравнений методом Гаусса:
|10 |48 |368 |55 | |0 |137,6 |1587,6 |-105 | |0 |1587,6|19885,6 |-1001 |
|10 |48 |368 |55 | |0 |137,6|1587,6 |-105 | |0 |0 |1568,203488|210.4680233 |
Получаем упрощенную систему уравнений:
1568,203488a3 = 210,4680233
137,6a2 + 1587,6a3 = -105
Решая которую получаем следующие окончательные значения, которые являются ответом:
a3=210,4680233/1568,203488=0,134209638 a2=(-105-1587,6 a3)/137,6=-2,311564115 a1=(55-48a2-368a3)/10=11,65659307
8.1 Обсуждение результатов с целью доказательства правильности алгоритма и программы.
Полученные результаты показывают, что алгоритм и программа составлены верно, так как значения полученные при ручном счете близки к машинным вычислением.
9.1 Выводы.
Данная программа очень эффективна, так как машина выполняет все действия гораздо быстрее, чем человек при ручном счете. Так же во время ручного счета могут произоити ошибки, что приведет к повторному перещитыванию, а у машины, при правильном алгоритме, таких сбоев не бывает (если только "зависает"). Следовательно эта программа во многом облегчает жизнь человеку.
II. Экономическая часть. Разработка модуля исключения нуль-уравнений в комплексе “Решение задачи линейного программирования”.
1.2 Постановка задачи линейного программирования и задание на разработку модуля.
Рассмотрим задачу оптимального планирования производства [1]. Пусть предприятие выпускает n изделий, для производства которых используется m ингредиентов. Ингредиенты это – детали определенного сортамента, станки, работники, электроэнергия и т.д., иначе говоря, все что требуется для осуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b1, b2,…, bm ), где bi - запас i-го ингридиента (i=1,…,m). Задана матрица А, элемент которой aij определяет расход i-го ингридиента для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан вектор рыночных цен изделий p=(p1, p2,…, pn), где p - цена j-го изделия (j=1,…,n).
Требуется составить такой план производства х=(х1, х2,…, хn), чтобы при выполнение условий
|a11x1 + a12x2 + … + a1nxn (| |b1 | |a21x1 + a22x2 + … + a2nxn (| |b2 | |…………………………….……………………. | |am1x1 + am2x2 + … + amnxn (| |bm | |xj ( 0, (j=1,…,n). |
достигался максимум функции
Z= p1x1 + p2x2 + … + pnxn
Функция Z называется целевой. i-е ограничение из (1) означает, что нельзя израсходовать i-го ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество (. Переменные, удовлетворяющие условию xj(0, называются несвободными. В нашей задаче это означает, что при xj=0 - ничего не производится или при xj>0 производится некоторое количество изделий.
Переменные, на которые условия неотрицательности не накладываются, называются свободными.
Задача (1)-(1') и есть задача оптимального производственного планирования, решение которой обеспечивает достижение в конкретных условиях максимальной прибыли.
Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для производства тех же n изделий. При этом количество приобретаемых ингридиентов определяется вектором b=(b1, b2, …, bm). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента для производства j-го изделия. Кроме того задан вектор цен p=(p1, p2, …, pn) на продукцию предприятия. Требуется отыскать вектор цен ингридиентов u=(u1, u2, …, um), где ui - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись условия:
|a11u1 + a21u2 + … + am1um (| |p1 | |a12u1 + a22u2 + … + am2um (| |p2 | |…………………………….……………………. | |a1nu1 + a2nu2 + … + amnum (| |pn | |ui ( 0, (i=1,…,m) |
при достижении минимума целевой функции
W=b1u1 + … + bmum
j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на производство j-го изделия, не меньше рыночной цены этого изделия.
Условие несвободности uj(0 означает, что j-й ингредиент либо бесплатен (uj=0), либо стоит положительное количество рублей (uj >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, то область ( запишется в виде:
|a11x1 + a12x2 + … + a1nxn = | |b1 | |…………………………….……………………… | |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) |
Требуется найти максимум функции
Z=p1x1 + p2x2 + … + pnxn
В общем случае среди переменных xj могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.
При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная ui (i=1,…,k), а свободной переменной xj ограничение - равенство: a1j u1 + a2j u2 + … + amj um =pj
Введем вспомогательные переменные yi(0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде:
|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 - разрешающим столбцом. Такая замена переменных носит название модифицированных жордановых исключений (МЖИ). Элементы матрицы а, не принадлежащие разрешающему столбцу или разрешающей строке, назовем рядовыми.
Страницы: 1, 2, 3
