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

Ниже приведено условие  и решение задачи. Закачка решения в формате doc  начнется автоматически через 10 секунд.

На предприятии имеется возможность выпускать n видов продукции . При ее изготовлении используются ресурсы Р1, Р2 и Р3. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2 и b3. Расход ресурса i-го вида на единицу продукции j-го вида составляет аij единиц. Цена единицы продукции j-го вида равна сj ден. ед.

 

 

а11

а12

а13

а14

b1

 

 

1

1

1

1

6000

 

а21

а22

а23

а24

b2

=

 

0.5

1

5

0.5

5000

 

а31

а32

а33

а34

b3

 

 

0.5

0.5

20

0.5

9000

 

с1

с2

с3

с4

 

 

 

80

100

300

80

 

 

Требуется:

1)     составить экономико-математическую модель задачи, позволяющую найти сбалансированный по ресурсам план выпуска продукции, обеспечивающий предприятию максимальный доход;

2)     симплексным методом найти оптимальный план выпуска продукции по видам; (дать содержательный ответ, раскрыв экономический смысл всех переменных, приведенных в решении задачи);

3)     сформулировать в экономических терминах двойственную задачу и составить ее математическою модель;

4)     найти компоненты оптимального плана двойственной задачи (двойственные оценки  используя решение исходной задачи и соответствие между двойственными переменными.

Решение

 

Обозначим через Х1 , Х2 , Х3-- количество единиц продукции соответственно П1, П2, П3,  планируемой к выпуску, а через  f--величину прибыли от реализации этой  продукции.  Тогда , учитывая значение  прибыли от единицы  продукции П1 =80 ден. ед., П2=100 ден. ед.,  П3=300 ден. ед.,    запишем сум­марную величину прибыли - целевую функцию - в следующем виде:

f = 80Х1  + 100Х2 +300Х3.                           (2.1)

Переменные Х1, Х2 , Х 3    должны удовлетворять ограничениям, наклады­ваемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса P1 на выполнение плана (Х1 , Х2 , Х3) составят (Х123) ед., где Х1 - затраты ресурса P1на выпуск Х1   ед. продукции П1;  Х2- затраты ресурсы P1 на выпуск Х2   ед. продукции П2 и т.д. Понятно, что указанная сумма не может превышать имеющийся запас P1 в 6000 ед., т.е.

Х123 ≤6000.               (2.2)

Аналогично получаем ограничения по расходу ресурсов P2 и P3:

0.5 Х12 +5Х3 ≤5000.                              (2.3)

0.5Х1 +0.5Х2 +20Х3 ≤9000.                           (2.4)

По смыслу задачи переменные Х1, Х2 , Х 3    не могут выражаться отрицатель­ными числами, т.е.

Хj  ≥0   (j=1,3)                                        (2.5)

 

Соотношения (2.1) - (2.5) образуют экономико-математическую модель данной задачи.

Итак, математически задача сводится к нахождению числовых значений Х1*, Х2*, Х 3*   переменных Х1, Х2 , Х 3 , удовлетворяющих линейным нера­венствам (2.2) - (2.5) и доставляющих максимум линейной функции (2.1)

 

2. Прежде чем решать задачу линейного программирования симплекс-методом, ее модель приводят к канонической форме. Основным признаком канонической формы является запись ограничений задачи в виде равенств. В нашем же случае ограничения (2.2) - (2.4) имеют вид неравенств типа "≤". Чтобы преобразовать их в эквивалентные уравнения, введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные  Х4 ,  Х5 , Х6   , обозначающие разности между правыми и левыми частями этих нера­венств. В результате модель можно записать в виде

f = 80Х1  +100Х2 +300Х3 (max)                         (2.6)

 

              Х123 + Х4 = 6000

         0,5Х12 +5Х3 + Х5 =5000                                   (2.7)

          0.5Х1 +0.5Х2 +20Х3 + Х=9000             

 

           Хj  ≥0   (j=1,6)                                        (2.8)

 

  Заметим здесь же, что дополнительные переменные Х4 ,  Х5 , Х6   имеют вполне определенный экономический смысл - это возможные остатки ресур­сов соответственно P1, P2, P3 . Их еще называют резервами.

Анализируя каноническую модель (2.6) - (2.8), замечаем, что каждая из переменных Х4 ,  Х5 , Х6   входит только в одно из уравнений системы (2.7). Это обстоятельство свидетельствует о том, что в системе (2.7) переменные Х4 ,  Х5 , Х6   являются базисными, а остальные переменные Х1 ,  Х2 , Х3   - свободными. В связи с этим в первую симплекс-таблицу систему ограничительных урав­нений (2.7) можно записать в виде, разрешенном относительно базиса Х4 ,  Х5 , Х6   (табл. 2.1).

 

Таблица 2.1

БП

1

СП

- Х1

- Х2

- Х3

Х4=

6000

1

1

1

Х5=

5000

0.5

1

5

Х6=

9000

0.5

0.5

20

f

0

-80

-100

-300

 

Все элементы столбца свободных членов положительны, поэтому со­держащийся в табл. 2.1 план (0; 0; 0;  6000;5000; 9000), является опорным. Однако этот план не является оптимальным: в f — строке имеются отрицательные элементы.

Чтобы получить опорный план, более близкий к оптимальному, выпол­ним симплексное преобразование табл. 2.1. С этой целью выберем перемен­ные, участвующие в преобразовании базиса Х4 ,  Х5 , Х6   в новый базис. Наи­больший по модулю отрицательный элемент (-300) f-строки указывает, что в новый базис следует ввести переменную Х3 ,т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять первый столбец. Что­бы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них

 

Min(6000/1;5000/5;9000/20)=9000/20=450

Итак, из базиса надо исключить переменную, стоящую в третьей (разре­шающей) строке, т.е. Х6. На пересечении разрешающих столбца и строки на­ходится разрешающий элемент 20, с которым и выполняется симплексное преобразование (шаг жорданова исключения). В результате приходим к табл. 2.2.

В f-строке табл. 2.2 есть отрицательные элементы, значит, опорный

план (0;0; 450;5550;2750;0) оптимальным не является.

 

Таблица 2.2

БП

1

СП

- Х1

- Х2

- Х6

Х4=

5550

0.975

0.975

-0.05

Х5=

2750

0.375

0.875

-0.25

Х3=

450

0.025

0.025

0.05

f

135000

-72.5

-92.5

15

 

Рассуждая аналогично предыдущему, устанавливаем, что для улучшения этого плана надо выполнить очередное симплексное преобразование с раз­решающим элементом   0.875 . В результате получаем табл. 2.3

Таблица 2.3

БП

1

СП

- Х1

- Х5

- Х6

Х4=

2486

0.557

-1.11

0.229

Х2=

3143

0.429

1.143

-0.286

Х3=

371.4

0.014

-0.029

0.057

f

425714.3

-32.86

106

11.43

В f-строке табл. 2.2 есть отрицательные элементы, значит, опорный план оптимальным не является. Рассуждая аналогично предыдущему, устанавливаем, что для улучшения этого плана надо выполнить очередное симплексное преобразование с раз­решающим элементом   0.557 . В результате получаем табл. 2.4

Таблица 2.4

БП

1

СП

- Х4

- Х5

- Х6

Х1=

4462

 

 

 

Х2=

1231

 

 

 

Х3=

307.7

 

 

 

f

572307.7

59

40

2.05

Следовательно, опорный план (4462 ; 1231 ; 307.7 ; 0 ; 0 ;  0 ) является опти­мальным, а соответствующее ему значение 572307.7 целевой функции будет макси­мальным.

Итак, по оптимальному плану следует изготовить 4462 ед. продукции П1 , 1231 ед. продукции П2, 307.7 ед. продукции П3 .

При этом предприятие получит максимальную прибыль в размере 572307.7  ден. ед. Pесурсы будут израсходо­ваны полностью.

3. Двойственная переменная Yiвыступает коэффициентом при b i     ,следовательно определяет зависимость целевой  функции от изменения ресурсов b i  на единицу.     

Чтобы составить модель двойственной задачи, напишем матрицу ис­ходной

задачи (2.1)- (2.5) в следующем виде:

 

1

1

1

6000

0.5

1

5

5000

0.5

0.5

20

9000

80

100

300

f max

Транспонируем матрицу (2.9). В результате получим матрицу (2.10) двойственной задачи:

1

0.5

0.5

80

1

1

0.5

100

1

5

20

300

6000

5000

9000

φ min

 

По матрице (2.10) легко написать модель   задачи, двойственной к ис­ходной задаче:

φ =6000Y1  + 5000Y2 +9000Y3 (min)                          (2.11)

 

Y1 +0.5Y2 +0.5Y3 ≥80

     Y1 +Y2 +0.5Y3 ≥100

    Y1 +5Y2 +20Y3 ≥300                                 (2.12)

 

           Yi ≥0   (j=1,3)                                        (2.13)

4. Из теорем двойственности следует, что если решена одна из пары двойственных задач, то одновременно найдено решение и другой задачи. Компоненты оптимального плана этой задачи находятся в строке целевой функции последней симплекс - таблицы решенной задачи.

В п. 2  мы нашли оптимальный план исходной задачи, его компоненты находятся в

табл. 2.3. В f-строке этой же таблицы содержатся и компоненты Yi* оптимального плана двойственной задачи (2.11) - (2.13). Выписать ком­поненты Yi* поможет соответствие между переменными двойственных задач. Чтобы установить это соответствие, преобразуем ограничения-неравенства (2.12) в эквивалентные уравнения, вычитая из левых частей до­полнительные неотрицательные переменные Y1, Y2 и Y3 , равные разностям между левыми и правыми частями этих неравенств. Тогда модель (2.11)-- (2.13) запишется в виде

φ = 6000Y1  + 5000Y2 +9000Y3 (min)                         

Y1 +0.5Y2 +0.5Y3 - Y4=80

     Y1 +Y2 +0.5Y3 - Y5=100

   Y1 +5Y2 +20Y3 - Y6=300                          

           Yi ≥0   (j=1,6)                                       

В этой записи переменные Y4, Y5 и Y6 являются базисными, а Y1, Y2 и Y3 - свободными. В исходной задаче (2.6) - (2.8) переменные Х1 ,  Х2 и Х3  яв­ляются свободными, a  Х4 ,  Х5 и  Х6  - базисными.

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

Х4 Y1, Х5 Y2, Х6 Y3, Х1 Y4, Х2 Y5, Х3 Y6,            (2.14)

 

Воспользуемся соответствием (2.14) следующим образом. Как видно, переменная Y1 связана с переменной Х4 (поэтому их называют двойственными переменными. Y1 соответст­вует Х4, а в табл.2.4 под Х4 в f- строке находится элемент 59 ,следовательно, Y1* = 59. Точно так же устанавливается, что Y2* = 40,  Y3* = 2.05; Y4* = 0 ; Y5* = 0 ; Y6* = 0 .

Из теорем двойственности следует, что экстремальные значения целе­вых функций разрешимых двойственных задач совпадают, поэтому       φ min = f max =572307.7  

Имя файла: mathprog1.doc

Размер файла: 77.5 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке