Математические уравнения

Автор работы: Пользователь скрыл имя, 22 Марта 2012 в 19:50, практическая работа

Описание

Оптимизацию ЗЛП обычно производят симплекс-методом с использованием симплекс-таблиц, в которые заносят

Скачать (345.14 Кб) Сколько стоит заказать работу?
Работа состоит из  1 файл

симплекс-метод.pptx

— 392.94 Кб (Скачать документ)

Оптимизацию ЗЛП обычно производят симплекс-методом               с использованием                          симплекс-таблиц,                                      в которые заносят

преобразованную                  каноническую форму ЗЛП.

БП

Значения b

x1

x2

s1

s2

  

s1

1000

5

10

1

0

  

s2

25

0,1

0,3

0

1

  

Z

0

-40

-100

0

0

  
   

Δ1

Δ2

y1

y2

  

 

Пример 3. Построить  симплекс-таблицу для оптимизации  ЗЛП Примера 2

 

X (0) ={x1=0, x2=0, s1=1000, s2=25}.

 

Таблица 1

Самостоятельная работа 2

 

Задание. При решении симплекс-методом задачи  линейного программирования  с системой ограничений

 

начальное допустимое базисное решение имеет вид …

А.   x1= 0,  x2 = 0,  s1 = 9,    s2 = 8

В.  x1= 3,  x2 = 0,  s1 = 0,    s2 = -2

С.   x1= 4,  x2 = 0,  s1 = -3,   s2=0

Переход от одного базисного  плана                к другому сопровождается преобразованием  симплекс-таблиц.

 

Такой переход называется итерацией.

 

Каждая итерация состоит из нескольких действий.

Итерация 1

  1). Проверка критерия оптимальности.

 Если в строке Z симплекс-таблицы нет отрицательных значений, решение оптимально.

 

У нас  имеются отрицательные элементы. Следовательно, начальный план не оптимален.

 

БП

Значения b

x1

x2

s1

s2

  

s1

1000

5

10

1

0

  

s2

25

0,1

0,3

0

1

  

Z

0

-40

-100

0

0

  
   

Δ1

Δ2

y1

y2

  

2). Переход  к новому ДБР

2.1. Определение  значения новой базисной переменной.

  Так как  план не оптимален, нужно изменить базис (вести в него одну из переменных х1 или х2).

 

Обычно  в состав БП вводят СП xk, для которой отрицательная оценка наименьшая (наибольшая по модулю

 

Столбец k при этом называют ведущим.

БП

Значения b

x1

x2

s1

s2

  

s1

1000

5

10

1

0

  

s2

25

0,1

0,3

0

1

  

Z

0

-40

-100

0

0

  
   

Δ1

Δ2

y1

y2

  

 

Выберем х2 в качестве новой базисной переменной (вводим в базис производство второго продукта)

 

Столбец х2 - ведущий

 

Таблица 1

2.2. Определение  новой свободной переменной.

 

Для определения  новой свободной переменной составим отношения столбца значений базисной переменной (второго столбца «Значения b») к положительным элементам ведущего столбца х2  и найдем среди них минимальное

 

В общем случае свободной делают БП xl, для которой отношение cвободного элемента к положительному элементу  ведущего столбца минимальное:

 

Строку l при этом называют ведущей.

БП

  

Значение b

x1

  x2

s1

s2

    b׳I /a׳ik

s1

 

1000

 5

  10

1

0

  

s2

  

25

 0,1

  0,3

0

1

  

Z

  

0

-40

 -100

0

0

  
     

Δ1

  Δ2

y1

y2

  

 

Таблица 1

БП

  

Значение b

x1

  x2

s1

s2

    b׳I /a׳ik

s1

 

1000

 5

  10

1

0

  

s2

  

25

 0,1

  

0

1

  

Z

  

0

-40

 -100

0

0

  
     

Δ1

  Δ2

y1

y2

  

 

0,3

 

Минимальное значение достигается для S2.Значит, базисная переменная S2 переходит в свободные

 

Строка S2 - ведущая

 

Число на пересечении ведущего столбца и ведущей строки – ведущий элемент

 

Таблица 1

БП

  

Значение (b')

x1

x2

s1

s2

b׳I /a׳ik

s1

              

x2

              

Z

              
     

Δ1

Δ2

y1

y2

  

 

2.3. Пересчет симплекс-таблицы

 

Таблица 2

 

   Для нового базиса S1, x2 составим новую симплекс-таблицу.

 

2.3.1. Все элементы второй (ведущей) строки делим на ведущий элемент 0,3 и получаем вторую строку новой таблицы.

БП

  

Значение (b')

x1

x2

s1

s2

b׳I /a׳ik

s1

              

x2

  

250/3

1/3

1

0

10/3

  

Z

              
     

Δ1

Δ2

y1

y2

  

 

Таблица 2

 

БП

  

Значение b’

x1

  x2

s1

s2

    b׳I /a׳ik

s1

 

1000

 5

  10

1

0

  

s2

  

25

 0,1

  

0

1

  

Z

  

0

-40

 -100

0

0

  
     

Δ1

  Δ2

y1

y2

  

 

Таблица 1

 

0,3

2.3.2. Остальные элементы новой таблицы получаем из соответствующих элементов             старой таблицы.

 

    Каждому элементу  соответствует один элемент в   ведущей строке и один элемент  в ведущем столбце.

 

 

Формула для пересчета:

БП

  

Значение (b')

x1

x2

s1

s2

b׳I /a׳ik

s1

  

500/3

          

x2

  

250/3

1/3

1

0

10/3

  

Z

              
     

Δ1

Δ2

y1

y2

  

 

БП

  

Значение

x1

  x2

s1

s2

s1

  

1000

 5

  10

1

0

s2

  

25

 0,1

  

0

1

Z

  

0

-40

 -100

0

0

     

Δ1

  Δ2

y1

y2


 

Таблица 2

 

0,3

 

Пересчет  Значения  b’ для S1

 

Пересчет  первой строки

БП

  

Значение (b')

x1

x2

s1

s2

b׳I /a׳ik

s1

  

500/3

 5/3

        

x2

  

250/3

1/3

1

0

10/3

  

Z

              
     

Δ1

Δ2

y1

y2

  

 

БП

  

Значение

x1

  x2

s1

s2

s1

  

1000

 5

  10

1

0

s2

  

25

 0,1

  

0

1

Z

  

0

-40

 -100

0

0

     

Δ1

  Δ2

y1

y2


 

Таблица 2

 

0,3

 

Пересчет х1

 

Пересчет  первой строки

БП

  

Значение (b')

x1

x2

s1

s2

b׳I /a׳ik

s1

  

500/3

 5/3

  0

      

x2

  

250/3

1/3

1

0

10/3

  

Z

              
     

Δ1

Δ2

y1

y2

  

 

БП

  

Значение

x1

  x2

s1

s2

s1

  

1000

 5

  10

1

0

s2

  

25

0,1

  

0

1

Z

  

0

-40

 -100

0

0

     

Δ1

  Δ2

y1

y2

Информация о работе Математические уравнения