Xreferat.com » Рефераты по информатике и программированию » Линейное программирование: решение задач графическим способом

Линейное программирование: решение задач графическим способом

{Свободный член целевой ф-ии}

N: TNerav; {Коэффициенты неравенств}

i: 0..100; {Счетчик кол-ва неравенств}

MainF: TNerav; {Коэффициенты целевой ф-ии}

XResult,YResult: Real; {Ответ(кординаты)}


procedure ShowXOY;{Проц. показа координатных осей}

Begin

SetColor(White);

Line(MinX, MaxY,MinX-4, MaxY+7);{стрелочки у Y}

Line(MinX, MaxY,MinX+4, MaxY+7);

OutTextXY(MinX-15, MaxY, 'У');


MoveTo(MinX, MaxY);

LineTo(MinX, MinY);{Сами оси}

LineTo(MaxX, MinY);


Line(MaxX, MinY, MaxX-7, MinY-4);{стрелочки у X}

Line(MaxX, MinY, MaxX-7, MinY+4);

OutTextXY(MaxX, MinY+5, 'X');

End;


procedure ShowLine(_iN:TNerav);

var s: String;

Begin

if _iN.b/_iN.y<0 then begin{если коэффиц. при Y меньше 0}

MoveTo(MinX+Round((_iN.b-(Round(MinY/MASHT)*_iN.y))/_iN.x*MASHT),MaxY);

SetColor(15);

LineTo(MinX+Round(_iN.b/_iN.x*MASHT),MinY);

end;

if _iN.b/_iN.x<0 then begin{если коэффиц. при X меньше 0}

MoveTo(MinX,MinY-Round(_iN.b/_iN.y*MASHT));

SetColor(15);

LineTo(MaxX,MinY-Round((_iN.b-(Round(MaxX/MASHT)*_iN.x))/_iN.y*MASHT));

end;

SetColor(LightGreen);

Str(_iN.b/_iN.x:3:1,s);

OutTextXY(MinX+Round(_iN.b/_iN.x*MASHT),MinY+5,s);{рисуем значения на оси OX}

Str(_iN.b/_iN.y:3:1,s);

OutTextXY(MinX-40,MinY-Round(_iN.b/_iN.y*MASHT),s);{рисуем значения на оси OY}


MoveTo(MinX,MinY-Round(_iN.b/_iN.y*MASHT));

SetColor(15);{Рисуем саму линию}

LineTo(MinX+Round(_iN.b/_iN.x*MASHT),MinY);

End;


procedure EnterNerav;{процедура ввода неравенств до нажатия Esc}


procedure GetNerav;{подпроцедура ввода коэф-тов одного неравенства}

var j,k: Real;

Begin

repeat

SetFillStyle(1,0); Bar(0,0,GetMaxX,MaxY-1);

OutTextXY(7,3,'Введите коэффициенты неравенств: ');

Window(34,1,80,1);

Read(N.x, N.y, N.b);{вводим коэффициенты}

j:=N.x;

k:=N.y;

repeat{далее идет сокращение коэффициентов если это возможно}

if (Frac(N.b / j) = 0) then

if (Frac(N.x / j) = 0) then Break;

j:=j-1;

until (j<=0);

if J>=0 then

repeat

if (Frac(N.b / k) = 0) then begin

if (Frac(N.y / k) = 0) then

if (j=k) then begin

N.b:=N.b / k;

N.x:=N.x / k;

N.y:=N.y / k;

Break;

end

end;

k:=k-1;

until (k<=0);

until (N.x<>0) and (N.y<>0); {Ограничение чтоб небыло нулей}

Inc(i); {Увеличиваем счетчик}

Matr[i]:=N;{Добавляем в матрицу коэффициенты}

ShowLine(N);{Вызываем процедуру рисования линии}

SetFillStyle(1,0); Bar(0,0,GetMaxX,MaxY-1);

OutTextXY(7,3,'Ввести еще? (Enter=Да/Esc=Нет)');

End;


var

Key:Char;

Begin

GetNerav;

repeat

key:=#0;

if KeyPressed then begin

key:=ReadKey;

case key of

#13: GetNerav;{ввод еще одного нер-ва}

end;

end;

Until Key in [#27];{до нажатия Esc}

End;


procedure EnterMainF;

{эта процедура предлагает выбрать пользователю выбрать выход из ОДЗ}

var key: Char;

j: 0..100;

S: String;

Begin

SetFillStyle(3,1); FloodFill(MinX+1, MinY-1, 15);

SetFillStyle(1,0); Bar(0,0,GetMaxX,MaxY-1);

SetColor(White);

OutTextXY(7,3,'Введите коэффициенты целевой функции: ');

Window(40,1,80,25); Read(MainF.x, MainF.y);

End;


procedure GetResult;

var

k,j: 0..100;

X: Real;

Y: Real;

XTmp: Real;

YTmp: Real;

cTmp: Real;

boolAnswer: Boolean;

key: Char;

STmp: String;

Result: String;{Строка для вывода на экра результата}

procedure SolveOprtel(inN, inMainF: TNerav; ic:Real; var outX, outY: Real);

{в этой подпроцедуре подностью вычисляется определитель}

var

_d: Real;{Дельта определителя}

dx: Real;{Дельта X определителя}

dy: Real;{Дельта Y определителя}

Begin

_d:=(inN.x*(inMainF.y)) - (inN.y*inMainF.x);

dx:=(inN.b*(inMainF.y)) - (inN.y*ic);

dy:=(inN.x*ic) - (inN.b*inMainF.x);

if _d <> 0 then begin{исклюсаем бесчисленное мн-во решений}

outX:=dx/_d;

outY:=dy/_d;

end;

if (_d = 0) and ((dx = 0) xor (dy = 0)) then begin{исклюсаем - нет решений}

SetColor(Red);

OutTextXY(300,230,'Нет решений!!!');

ReadKey;

CloseGraph;

Halt;

end;

End;


Begin

Bar(0,0,GetMaxX,MaxY-1);

SetColor(White);

OutTextXY(7,3,'Пожалуйста подождите... (Esc - Отмена)');

{считаем координаты выхода}

c:=0;

cTmp:=0;

repeat

if i=1 then SolveOprtel(Matr[1], MainF, c, XResult, YResult)

else

for j:=1 to i-1 do begin

SolveOprtel(Matr[j], MainF, c, XTmp, YTmp);

for k:=j+1 to i do begin

SolveOprtel(Matr[k], MainF, c, X, Y);

if X=XTmp then XResult:=X;

if Y=YTmp then YResult:=Y;

end;

end;

{далее мы находим максимум функции}

BoolAnswer:=False;

for k:=1 to i do begin

N:=Matr[k];

if (N.x*XResult+N.y*YResult<=N.b) then begin

{Если в ОДЗ}

c:=cTmp;

boolAnswer:=True;

end;

{далее проверяем вышла ли cTmp за ОДЗ}

if (N.x*XResult+N.y*YResult>N.b) then begin Exit

end;

end;

cTmp:=cTmp+STEP;{Увеличиваем cTmp на STEP}

if keyPressed then key:=ReadKey;{если Esc нажата, то прерываем}

until (key=#27) or (cTmp>=10000);

if boolAnswer then begin

{пишем ответ:}

{1. Рисуем целевую ф-ю в нужном месте}

c:=MainF.x*XResult+MainF.y*YResult;

MoveTo(MinX+1,MinY-Round(C/MainF.y*MASHT)-1);

SetColor(Red);{рисуем целевую линию на экр. красным}

LineTo(MinX+Round(C/MainF.x*MASHT)+1,MinY-1);


SetLineStyle(1,0,NormWidth);

SetColor(Yellow);

{2. Считаем max(f)}

Str(MainF.x*XResult+MainF.y*YResult:2:1,STmp);

Result:='max(f)='+Stmp;

{3. Рисуем значение на оси X}

Line(MinX+Round(XResult)*MASHT,MinY-Round(YResult)*MASHT,MinX+Round(XResult)*MASHT,MinY+3);

Str(XResult:2:1,STmp);

OutTextXY(MinX+Round(XResult)*MASHT,MinY+4,STmp);

Result:=Result+' при x='+Stmp;

{4. Рисуем значение на оси Y}

Line(MinX+Round(XResult)*MASHT,MinY-Round(YResult)*MASHT,MinX-3,MinY-Round(YResult)*MASHT);

Str(YResult:2:1,STmp);

OutTextXY(MinX-30,MinY-Round(YResult)*MASHT,STmp);

Result:=Result+' y='+Stmp;

SetColor(White);

SetLineStyle(0,0,NormWidth);

OutTextXY(300,230,Result);{Выводим строку ответа}

end

else

OutTextXY(7,3,'Вычисления не закончены!!!');


{Завешение программы}

Bar(0,0,GetMaxX,MaxY-1);

SetColor(White);

OutTextXY(7,3,'Нажмите любую клавишу для выхода');

ReadKey;

End;


BEGIN

i:=0;{Начальное значение кол-ва неравенств}

Gd:=Detect;

InitGraph(Gd, Gm, 'C:BPBGI'); { Путь к BGI драйверам }

if GraphResult <> grOk then Halt(1);

ShowXOY;

EnterNerav;

EnterMainF;

GetResult;

CloseGraph;

END.

Заключение

Программа решения задач линейного программирования графическим способом на IBM PC была написана на языке Borland Pascal 7.1. В ней, для удобства, рассматривается случай когда количество переменных равно двум т. е. решение задачи можно разместить на плоскости. С помощью этой программы можно наглядно продемонстрировать метод графического решения задач.

Вообще, с помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если N и M связаны соотношением N – M = 2.

Действительно, пусть поставлена задача линейного программирования.

Найти максимальное значение линейной функции

Z = С1х1+С2х2+... +СNxN
при ограничениях

a11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

aМ1x1 + aМ2x2 + ... + aМNХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

где все уравнения линейно независимы и выполняется cоотношение N - M = 2.

Используя метод Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х1, х2, ..., хM, а свободными - два последних: хМ+1, и хN, т. е. система ограничений приняла вид:

x1 + a1,М+1xМ+1 + a1NХN = b1

x2 + a2,М+1xМ+1 + a2NХN = b2

. . . . . . . . . . . .

xМ + aМ, М+1x2 + aМNХN = bМ


xj ≥ 0 (j = 1, 2, ..., N)

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные - неотрицательные: хj ≥ 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.


Литература

1. Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. - 184 с.

2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие - 2-е изд., испр. и доп. - М.: Высш. шк. ,1993 - 336 с.

3. Ашманов С.А.Линейное программирование. - М.: Наука, 1981.

4. Баканов М.И., Шеремет А.Д. Теория экономического анализа: Учебник. -4-е изд., доп. и перераб. - М.: Финансы и статистика, 2000. - 416 с.

5. Баканов М.И., Шеремет А.Д.Экономический анализ: ситуации, тесты, примеры, задачи, выбор оптимальных решений, финансовое прогнозирование: Учеб. пособие. - М.: Финансы и статистика, 1999. -656 с.

6. Банди Б. Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. -176 с.

7. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 176 с.

8. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.2. Транспортные задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 240 с.

9. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента - СПб.: Издательство “Лань”, 2000. -480 с.

10. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование,теория, методы и приложения. - М.: Наука, 1969.

11. Гасс С.Линейное программирование. - М.: Физматгиз, 1961.

12. Заварыкин В. М. и др. Численные методы: Учеб. пособие для студентов физ.-мат. спец. пед. ин-тов / В.М. Заварыкин, В.Г. Житомирский, М.П. Лапчик. - М.: Просвещение, 1990. - 176 с

13. .Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. /Под общ. ред. проф. Кузнецова А.В., М., “ВЫШЭЙШАЯ ШКОЛА”, 1994. - 288 с.

14. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие. – 2-е изд., перераб и доп. - М.: Высш. школа, 1980. -300 с.

15. Ляшенко И.Н, Карагодова Е.А, Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Издательское объединение “Вища школа”, 1975. - 372 с.

16. Пер. с яп. /М. Кубонива, М. Табата, С. Табата, Ю. Хасэбэ, под ред. М. Кубонива. Математическая экономика на персональном компьютере: - М.: Высш. школа, 1980.

17. Под ред и с предисл. Е.З. Демиденко – М.: Финансы и статистика, 1991. – 304 с.

18. Солодовников А.С. Введение в линейную алгебру и линейное программирование. М., Изд. “Просвещение”, 1966. - 184 с.

19. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т.1: Пер с англ. - М.: Мир, 1991. -360 с.

20. Тынкевич М.А. Экономико-математические методы (исследование операций). Изд. 2, испр. и доп. - Кемерово, 2000. - 177 с.

Рецензия

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: