Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
Helga
0 / 0 / 0
Регистрация: 29.03.2009
Сообщений: 22
1

Оптимизация. ДЛП

05.12.2010, 10:21. Просмотров 720. Ответов 2
Метки нет (Все метки)

Здравствуйте. Помогите, пожалуйста. По курсовой надо "Оптимизация задач дробно-линейного программирования". Есть код, который решает задачу линейного программирования. Надо немного преобразовать его, но не знаю как.
Задачу ДЛП можно свести к задаче ЛП и решить симплексным методом.
Обозначаем у0 = 1 / dj * xj .
при условии d * x не равно 0
Введем новые переменные уj = y0xj.
Тогда задача примет вид L = c * y стремится к max/min
при ограничениях: a * y - b * y0 = 0, d * y = 1
После этого решается обычным симплекс-методом.. То есть в проге надо тока начало дописать и в конце обратные преобразования выполнить: х1=у1/у0, х2=у2/у0, х3=у3/у0, х4=у4/у0.
Но паскаль был на 1 курсе.. так давно...
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
{Программа составлена для решения задачи линейного программирования
 симплексным методом}
uses crt;
const n=2;{число неизвестных исходной задачи}
      m=3;{число ограничений}
      m1=0;{последняя строка равенств}
      m2=1;{последняя строка неравенств вида >=}
label 5,15,20,10;
var b,cb:array[1..m] of real;c,x,e:array[1..50] of real;a:array[1..m,1..50] of real;
    s0,max,mb,s1:real;i,j,k,i0,j0,m21,nm1,n1:integer; Bi:array[1..m] of integer;
begin
     clrscr;
     writeln;
     writeln (' Симплексный метод решения задачи линейного программирования:');
     writeln;
     writeln (' Проведем некоторые преобразования с данной задачей:');
     writeln;
     writeln (' Подготовьте матрицу: сначала равенства, потом неравенства вида >= и неравенства  вида <=;');
     writeln (' Целевая функция должна быть на минимум (привести ее к такому виду); ');
     writeln (' Вектор b должен состоять только из положительных элементов (привести его к та-  кому виду);');
     writeln(' Введите матрицу А ',m,'*',n,' построчно:');
     for i:=1 to m
         do begin for j:=1 to n
                      do read (a[i,j]);
                      readln
                  end;
     writeln (' Введите в виде строки вектор b, состоящий из ',m,' компонент:');
     for i:=1 to m
         do read (b[i]);
     writeln(' Введите теперь вектор с, состоящий из ',n,' компонент:');
     for i:=1 to n
          do read (c[i]);
     m21:=m2-m1+n;nm1:=n+m-m1;n1:=n+m-m1+m2;
     for i:=1 to m
         do for j:=n+1 to n1
                do a[i,j]:=0;
     {переход к равенствам в неравенствах >=}
     for i:=m1+1 to m2
         do a[i,n+i-m1]:=-1;
     {переход к равенствам в неравенствах <=}
     for i:=m2+1 to m
         do a[i,m21+i-m2]:=1;
     {создание искуственного базиса}
     for i:=1 to m2
         do a[i,nm1+i]:=1;
         {ввод mb в вектор с}
     mb:=12345;
     for i:=n+1 to nm1
         do c[i]:=0;
     for i:=nm1+1 to n1
         do c[i]:=mb;
     {выписать cb}
     for i:=1 to m2
         do begin cb[i]:=mb; Bi[i]:=nm1+i end;
     for i:=m2+1 to m
         do begin Bi[i]:=m21+i-m2;
                  cb[i]:=0;
            end;
     for i:=1 to n1
         do x[i]:=0;
     writeln(' Решение задачи:');
     {применяем симплексный метод, вычисляем оценки}
     5: for j:=1 to n1
            do begin s0:=0;
                     for i:=1 to m
                         do s0:=s0+cb[i]*a[i,j];
                     e[j]:=s0-c[j]
               end;
     max:=e[1];j0:=1;
     for i:=2 to n1
         do if e[i]>max
               then begin max:=e[i];
                          j0:=i
                    end;
     {получили столбец с максимальной оценкой}
     if max<=0
        then begin for i:=1 to m
                       do x[Bi[i]]:=b[i];
                                        goto 15
             end;
     s1:=a[1,j0];
     for i:=2 to m
         do if s1<a[i,j0]
               then s1:=a[i,j0];
     if s1<=0
        then goto 10;
     s1:=mb;
     for i:=1 to m
         do if a[i,j0]>0
               then if s1>b[i]/a[i,j0]
                       then begin
                                  s1:=b[i]/a[i,j0];
                                  i0:=i
                            end;
     {главный элемент a[i0,j0]}
     s0:=a[i0,j0]; Bi[i0]:=j0;
     for j:=1 to n1
         do a[i0,j]:=a[i0,j]/s0;
     b[i0]:=b[i0]/s0;
     for i:=1 to m
         do if i<>i0
               then begin s1:=-a[i,j0];
                          b[i]:=b[i]+b[i0]*s1;
                          for j:=1 to n1
                              do a[i,j]:=a[i,j]+a[i0,j]*s1
                    end;
      cb[i0]:=c[j0];
      goto 5;
      10: writeln(' Нет оптимального плана, функция неограничена');
      goto 20;
      {просмотр иск. переменных}
      15: for i:=nm1+1 to n1
              do if x[i]>0
                    then begin writeln(' Пустое множество планов');
                               goto 20
                         end;
 
      for i:=1 to n
          do writeln(' x[',i,']=',x[i]:7:4);
      20:readkey
end.
Добавлено через 13 часов 49 минут
помогите, пожалуйста...
в понедельник уже курсовую сдавать....
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 10:21
Ответы с готовыми решениями:

Типы оптимизация: черная оптимизация, серая оптимизация и белая оптимизация
Много много лет назад, на заре становления профессии &quot;оптимизатора&quot; в какой то умной книжке был...

Оптимизация методом Ньютона (нахождение точки минимума). Оптимизация кода
MATLAB только начал осваивать. Попытался реализовать нахождение точки минимума методом Ньютона...

Оптимизация
Добрый день. Я начинающий программист и меня сильно интересует опрос оптимизации. Что будет...

оптимизация
Привет. У меня есть сайт проката автомобилей, находится в первой десятке GOOGLE,YAHOO,MSN,YANDEX ,...

Оптимизация БД
Создаю БД, в которой будет неимоверное кол-во группированных записей Вместо создания отдельных...

2
pavelr
Заблокирован
05.12.2010, 11:34 2
Это ж с симплекс-методом возиться!
0
Helga
0 / 0 / 0
Регистрация: 29.03.2009
Сообщений: 22
05.12.2010, 11:41  [ТС] 3
ну если я правильно понимаю, то тут тока строчек 6-10 добавить надо.. сам симплекс то написан...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2010, 11:41

Оптимизация
Всем привет, недавно начал изучать c#, никак не пойму, как можно оптимизировать этот прекрасный...

Оптимизация
помогите оптимизировать формулы Добавлено через 5 минут не могу закинуть файл, пишет ошибка...

Оптимизация
Вот 2 аналогичные работы, но с другими данными. Почему в одной все работает без ошибок ,а в другой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru