Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Дробно-линейное программирование




Если в задаче с линейными ограничениями задана дробно-линейная целевая функция, то такая задача мо­жет быть преобразована к традици­онному виду путем несложных пре­образований. Преобразованная модель может быть разрешена симплексным ме­тодом, а найденное решение трансформировано в решение ис­ходной задачи дробно-линейного программирования. Все этапы алгоритма проиллюстрируем на конкретном примере.

1. Систему ограничений приводят к каноническому виду:

где ─ основные переменные;
─ дополнительные переменные;
─ искусственные переменные.

2. Знаменатель целевой функции обозначают через , это приво­дит к следующему:

§ появится дополнительное ограничение или ;

§ функция цели приобретет вид .

3. Все ограничения умножают на и к ним добавляют дополни­тельное соотношение.

 

4. Вводят обозначения:

; ; ;

; ; ; .

Упорядочивают систему относительно новых переменных, перено­ся из правой части элементы, связанные с . Кроме того, в допол­нительное ограничение вводят искусственную переменную со сле­дующим номером, в данном случае вводят . Это необходимо для формирования начального базиса. В результате указанных преоб­разований задача приобретает вид:

 

5. Задача приобрела каноническую форму, ее решение может быть выполнено симплексным методом. Учитывая, что индексы векторов должны соответствовать индексам переменных (, , и т.д.), вектор свободных членов обозна­чают через - это избавит от путаницы.

 

         

 


Таблица 1

Начальное симплекс-решение

 

Б С                   С.о.
    -6       -1              
    -14         -1            
      -5                    
                    1/5  
-строка       -3   -2                  
-строка     -20       -1   -1          

 

Данной таблице соответствуют такие значения переменных:

; ; ; ; ; ; ; ; .

Это решение не оптимально.

В таблице 1 получено три одинаковых симплексных отноше­ния, - все они равны нулю. При выборе ключевой строки руковод­ствуются правилом: берут ту, которая соответствует большему элементу ключевого столбца. В данном случае выбирают первую строку, и генеральный элемент равен 6.

Таблица 2

Вторая симплексная таблица

 

Б С                 С.о.
    -1   1/6     -1/6            
    -12   40/6   2/6   -1          
      -4   5/6     1/6            
    19/6     5/6           6/19  
-строка     -2   -16/6     -2/6              
-строка     -7   59/6     7/6   -1        

 

Второе решение выглядит так:

; ; ; ; ; ; ; ; .

Оно не оптимально.

Переход к третьей таблице выполняется по обычным правилам с учетом комментария к выбору ключевой строки, сделанного после таблицы 1.


Таблица 3

Третье симплексное решение

 

Б С               С.о.
    -28/40       -7/40   1/40       -  
      -72/40       2/40   -6/40       -  
      -100/40       5/40   5/40       -  
    428/40     27/40   19/40       40/428  
-строка     -272/40       -8/40   -16/40          
-строка     428/40       27/40   19/40      

 

Третье решение:

.

Условие оптимальности все еще не выполняется, переходят к следующей таблице.

Анализ показывает, что значения большинства переменных будут равны нулю до тех пор, пока ключевой строкой будет оставаться строка с нулевым элементом в . Как только ключевой станет строка с ненулевым эле­ментов в , так базисные переменные обретут конкретные зна­чения.

Таблица 4

Четвертое симплексное решение

 

Б С             С.о.
  28/428         -56/428   24/428     -  
    72/428         70/428   -30/428     72/70  
    100/428         121/428   101/428     100/121  
  40/428         27/428   19/428     40/27  
-строка   272/428         98/428   -42/428        

 

Решение, соответствующее таблице 4, имеет вид:

, , , , .

Оно не является оптимальным, строят следующее симплекс-преобразование.

 


Таблица 5

Пятое симплексное решение

 

Б С            
  21/121           20/121   56/121  
    4/121           -25/121   -70/121  
    100/121           101/121   428/121  
  5/121           -1/121   -27/121  
-строка   54/121           -35/121   -98/121  

 

В таблице 5 получено решение, удовлетворяющее условию опти­мальности:

, , , , .

 

6. Определяют значения исходных переменных:

Таким образом, решение задачи дробно-линейного программиро­вания будет следующим:

.

7. Дают, если возможно, геометрическую интерпретацию задачи:

§ находят область допустимых значений;

§ отмечают точки, соответствующие симплекс-таблицам.

 

Областью решений является треугольник . Первые ре­альные значения переменных появились в четвертой симплекс­ной таблице, им соответствуют такие значения исходных неизвестных: . На графике – это вершина , она оптимальной не является. Оптимальное решение обеспечивает верши­на .

 

                                               
                                                     
                                                     
                                                     
                                                     
                                                   
                            А                    
                                                 
                                                   
                                                     
                                                     
                                                   
                                                     
                                С         В      
                                           
                                               
    -5   -4   -3   -2   -1                              
                                                     
                        -1                            

Замечание. Дробно-линейную задачу с двумя переменными можно решать графическим методом, основываясь на таких правилах:

1. По системе заданных ограничений строят область допустимых решений.

2. Выбирают произвольное значение и строят соответствующую прямую – она обязательно пройдет через начало координат.

3. Обозначим

§ если , то, поворачивая прямую против часовой стрелки до опорного положения, получим точку минимума (для получения максимума прямую поворачивают по часовой стрелке);

§ если , то для получения минимума прямую поворачивают по часовой стрелке до опорного положения (для максимума – против часовой стрелки).

4. Определив оптимальные точки, находят их координаты – это и будут оптимальные значения переменных, после чего вычисляют величину функции цели.

 

Пример. Найти решение дробно-линейной задачи.

, рассмотрим 2 варианта функции

а) б)

 

1. Строим область допустимых решений – она определяется тремя неравенствами и представляем собой треугольник .

 

2. Строим прямую

а)

б)

; ;

а) ; ; ; ;

б) ; ; ; ;

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...