Графический метод применим только для двух и менее переменных х, что подходит к данному заданию. Линии, соответствующие ограничения, строятся на осях Ох. Заштрихованная область - область допустимых стратегий.
x1 + 5x2 £ 10;
3x1 + 2x2 £ 12;
2x1 + 4x2 £ 10.
x1 ³ 0; x2 ³ 0.
1). x1 + 5x2 £ 10;
x1 = 0, x2 = 2;
x1 = 10, x2 = 0.
2). 3x1 + 2x2 £ 12;
x1 = 0, x2 = 6;
x1 = 4, x2 = 0.
3). 2x1 + 4x2 £ 10;
x1 = 0, x2 = 2.5;
x1 = 5, x2 = 0.
4). Найдём экстремум функции:
F = 2x1 + 3x2 ,
ВЫВОДЫИ РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ ИСПОЛЬЗОВАНИЮ
Составление математической модели и решение систем линейных неравенств часто имеет место в реальной жизни. Примеры таких задач:
Пример 1. Рассматривается работа промышленного предприятия под углом зрения его рентабельности, причём приводится ряд мер с целью повышения этой рентабельности. Показатель эффективности - прибыль (или средняя прибыль), приносимая предприятием за хозяйственный год.
Пример 2. Группа истребителей поднимается в воздух для перехвата одиночного самолёта противника. Цель операции - сбить самолёт. Показатель эффективности - вероятность поражения цели.
Пример 3. Ремонтная мастерская занимается обслуживанием машин; её рентабельность определяется количеством машин, обслуженных в течение дня. Показатель эффективности - среднее число машин, обслуженных за день.
Пример 4. Группа радиолокационных станций в определённом районе ведёт наблюдение за воздушным пространством. Задача группы - обнаружить любой самолёт, если он появится в районе. Показатель эффективности - вероятность обнаружения любого самолёта, появившегося в районе.
Пример 5. Предпринемается ряд мер по повышения надёжности электронной цифровой вычислительной техники (ЭЦВТ). Цель операции - уменьшить частоту появления неисправностей (“сбоев”) ЭЦВТ, или, что равносильно, увеличить средний промежуток времени между сдоями (“наработку на отказ”). Показатель эффективности - среднее время безотказной работы ЭЦВТ.
Пример 6. Проводится борьба за экономию средств при производстве определённого вида товара. Показатель эффективности - количество сыкономленных средств.
С помощью анализа модели на чувствительность определить параметр, от которого результат зависит больше и решить, каким способом возможно увеличение эффективности и на сколько, а так же многое другое.
В данной части пояснительной записки к курсовой работе представлена и описана программа, реализующая решение систем линейных неравенств табличным методом.
НАЗНАЧЕНИЕ ПРОГРАММЫ
Программа предусмотрена для решения систем линейных неравенств табличным методом, а так же для попытки оптимизации различных экономических, социальных и т. д. проблем.
Метод, описанный в программе, может применяться на государственных и частных предприятиях для улучшения эффективности производства.
УСЛОВИЯ ПРИМЕНЕНИЯ
1.1 Ограничения и область применения
Из программных средств требуется операционная система MS DOS версии 5.0, программная Среда NORTON COMMANDER, язык программирования Borland Pascal 7.0. Кроме того НГМД должен содержать файлы в директории KURSOVIK:
1. Файл входных данных - KURS97.DAT
2. Программный файл - KURS97.EXE
1.2 Требования к техническим средствам
IBM PC или IBM PC - совместимый компьютер с дисководом 3.25” ёмкостью 1.2 Мб.
ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ
Входные и выходные данные заносятся в файлы KURS97.DAT и KURS97.RES соответственно. Входные данные записываются в определённом порядке. Выходные данные записываются в виде симплекс-таблиц.
ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ
Входные данные вносятся в файл KURS 97.DAT в следующей очерёдности:
сначача вводятся коэффициенты при неизвестных в целевой функции, затем вводятся элементы вектора ограничений, а потом - элементы матрицы ограничений по столбцам.
Результаты вычислений вы найдёте в файле KURS 97.REZ.
ТЕКСТ ИСХОДНОГО МОДУЛЯ
Полный текст программы KURS97.PAS выглядит следующим образом:
. program Kurs97;
uses crt;
const
n = 2;
m = 3;
Epsilon = 0.000001;
var
VectorA: array [1..m, 0..m+n] of real;
TargetVector: array [1..m+n] of real;
SimplexVector: array [0..m+n] of real;
DigitOfBasisVector: array [1..m] of real;
BasisVector: array [1..m] of integer;
IndexOfEnterVector: integer;
IndexOfOutputString: integer;
MinimumBuffer: real;
key: char;
FileOfOutput: text;
{ Описание процедур }
procedure ReadDates; { считывание данных из файла }
var
DateFile: text;
procedure ReadDatesTargetVector; { считывание данных целевого вектора }
var i: integer;
begin
for i:=1 to n do Readln(DateFile, TargetVector[i]);
end;
procedure ReadDatesVectorA; { считывание вектора А и заполнение единицами диагонали}
var i,j: integer;
begin
for j:=0 to n do
for i:=1 to m do
Readln(DateFile, VectorA[i, j]);
i:=1;
for j:=n+1 to n+m do
begin
VectorA[i, j]:=1;
inc(i)
end;
end;
procedure ReadDatesBasisVector;
var i: integer;
begin
for i:=1 to m do BasisVector[i]:=n+i;
end;
begin
Assign(DateFile, 'kurs97.dat');
Reset(DateFile);
ReadDatesTargetVector;
ReadDatesVectorA;
ReadDatesBasisVector;
Close(DateFile);
end;
procedure CountSimplexVector; { расчет симплек-вектора }
var
i,j: integer;
Summa: real;
Simplex: real;
begin
SimplexVector[0]:=0;
for i:=1 to m do
SimplexVector[0]:=SimplexVector[0] + DigitOfBasisVector[i]*VectorA[i, 0];
for j:=1 to m+n do
begin
Summa:=0;
for i:=1 to m do Summa:=Summa + DigitOfBasisVector[i]*VectorA[i, j];
SimplexVector[j]:=Summa - TargetVector[j];
if abs(SimplexVector[j]) <= Epsilon then SimplexVector[j]:=0;
end;
end;
function GetEnterVector: integer; { поиск вводимого вектора }
var
i: integer;
Min: real;
begin
GetEnterVector:=1;
Min:=SimplexVector[1];
for i:=2 to m+n do
if Min > SimplexVector[i]
then
begin
GetEnterVector:=i;
Min:=SimplexVector[i];
end;
end;
function GetOutputString: integer; { поиск выводимой строки }
var
i: integer;
Temp: real;
begin
GetOutputString:=1;
if VectorA[1, IndexOfEnterVector] > 0 then MinimumBuffer:=VectorA[1, 0] / VectorA[1, IndexOfEnterVector];
for i:=2 to m do
begin
Temp:=VectorA[i, 0] / VectorA[i, IndexOfEnterVector];
if Temp > 0 then
if MinimumBuffer >= Temp then
begin
MinimumBuffer:=Temp;
GetOutputString:=i;
end;
end;
end;
procedure ReCountOutputString; { пересчет коэффициентов выводимой строки }
var
i,j: integer;
Buffer: real;
procedure ReCountDigitOfBasisVector;
begin
DigitOfBasisVector[IndexOfOutputString]:=TargetVector[IndexOfEnterVector];
end;
procedure ReCountBasisVector;
begin
BasisVector[IndexOfOutputString]:=IndexOfEnterVector;
end;
begin
ReCountDigitOfBasisVector;
ReCountBasisVector;
Buffer:=VectorA[IndexOfOutputString, IndexOfEnterVector];
for i:=0 to m+n do
begin
VectorA[IndexOfOutputString, i]:=VectorA[IndexOfOutputString, i] / Buffer;
end;
end;
procedure ReCountVectorA;
var i,j: integer;
begin
for j:=0 to m+n do
begin
for i:=1 to m do
begin
if i <> IndexOfOutputString then
if j <> IndexOfEnterVector
then VectorA[i, j]:=VectorA[i, j] - VectorA[i,IndexOfEnterVector]*VectorA[IndexOfOutputString,j];
end;
end;
for i:=1 to m do
if i <> IndexOfOutputString then VectorA[i, IndexOfEnterVector]:=0;
end;
function AllIsPositiv: boolean;
var i: integer;
begin
AllIsPositiv:=True;
for i:=1 to m+n do
if SimplexVector[i] < 0 then AllIsPositiv:=False;
end;
function ToStr(const D: real): string;
var S: string;
begin
str(D:6:2, S);
ToStr:=' ' + S + ' ';
end;
procedure WriteMatrixs;
procedure WriteTargetMatrix;
var i: integer;
begin
writeln(' +-----------------------------------------------------+');
write (' ¦ Target ¦');
for i:=1 to n+m do write(ToStr(TargetVector[i]),'¦'); writeln;
end;
procedure WriteMatrixA;
var i,j: integer;
begin
writeln(' +-----------------+--------+--------+--------+--------+--------+--------¦');
writeln(' ¦ Basis ¦ D.Basis¦ A 0 ¦ A 1 ¦ A 2 ¦ A 3 ¦ A 4 ¦ A 5 ¦');
writeln(' +--------+--------+--------+--------+--------+--------+--------+--------¦');
for i:=1 to m do
begin
write(' ¦ A ',BasisVector[i],' ¦',ToStr(DigitOfBasisVector[i]),'¦');
for j:=0 to m+n do write(ToStr(VectorA[i, j]),'¦'); writeln;
if i = m then writeln(' +--------+--------+--------+--------+--------+--------+--------+--------¦')
else writeln(' +--------+--------+--------+--------+--------+--------+--------+--------¦');
end;
end;
procedure WriteMatrixSimplex;
var i: integer;
begin
write(' ¦ Simplex¦');
for i:=0 to m+n do write(ToStr(SimplexVector[i]),'¦'); writeln;
writeln(' +--------------------------------------------------------------+');
end;
begin
clrscr;
WriteTargetMatrix;
WriteMatrixA;
WriteMatrixSimplex;
end;
procedure WriteMatrixsInFile;
procedure WriteTargetMatrix;
var i: integer;
begin
writeln(FileOfOutput, ' +-----------------------------------------------------+');
write (FileOfOutput, ' ¦ Target ¦');
for i:=1 to n+m do write(FileOfOutput, ToStr(TargetVector[i]),'¦'); writeln(FileOfOutput);
end;
procedure WriteMatrixA;
var i,j: integer;
begin
writeln(FileOfOutput, ' +-----------------+--------+--------+--------+--------+--------+--------¦');
writeln(FileOfOutput, ' ¦ Basis ¦ D.Basis¦ A 0 ¦ A 1 ¦ A 2 ¦ A 3 ¦ A 4 ¦ A 5 ¦');
writeln(FileOfOutput, ' +--------+--------+--------+--------+--------+--------+--------+--------¦');
for i:=1 to m do
begin
write(FileOfOutput, ' ¦ A ',BasisVector[i],' ¦',ToStr(DigitOfBasisVector[i]),'¦');
for j:=0 to m+n do write(FileOfOutput, ToStr(VectorA[i, j]),'¦'); writeln(FileOfOutput);
if i = m then writeln(FileOfOutput, ' +--------+--------+--------+--------+--------+--------+--------+--------¦')
else writeln(FileOfOutput, ' +--------+--------+--------+--------+--------+--------+--------+--------¦');
end;
end;
procedure WriteMatrixSimplex;
var i: integer;
begin
write(FileOfOutput, ' ¦ Simplex¦');
for i:=0 to m+n do write(FileOfOutput, ToStr(SimplexVector[i]),'¦'); writeln(FileOfOutput);
writeln(FileOfOutput, ' +--------------------------------------------------------------+');
end;
begin
clrscr;
WriteTargetMatrix;
WriteMatrixA;
WriteMatrixSimplex;
end;
{ Головная программа }
BEGIN
ClrScr;
ReadDates;
Assign(FileOfOutput, 'kurs97.res');
Rewrite(FileOfOutput);
CountSimplexVector;
WriteMatrixs;
while not AllIsPositiv do
begin
IndexOfEnterVector:=GetEnterVector;
IndexOfOutputString:=GetOutputString;
ReCountOutputString;
ReCountVectorA;
CountSimplexVector;
WriteMatrixsInFile;
WriteMatrixs;
if key=#0 then key:=readkey; key:=#0;
end;
Close(FileOfOutput);
END.