Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

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

;
  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 с.
1234
скачать работу

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

 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ