Методы решения задач линейного и целочисленного программирования

Страницы работы

15 страниц (Word-файл)

Фрагмент текста работы

Приведем заданную модель к каноническому виду, введя свободные переменные y3 и y4, превращающие неравенства в равенства. Переменные y3 и y4 входят в уравнение с коэффициентом единица и только один раз:

84y1+84y2→min

12y1 + 7y2 – y3 = 8

7y1 + 12y2 – y4 = 9

y3 = – 8 – (–12y1 – 7y2)

y4 = – 9 – (–7y1 – 12y2)

Составим симплекс – таблицу:

Базовые переменные

Свободные члены

Свободные переменные

Y1

Y2

Y3

–8

–12

–7

Y4

–9

–7

–12

F

0

–84

–84

                За разрешающий элемент мы берем -12, т.к. он находится на пересечении разрешающего столбца и разрешающей строки. Разрешающая строка – это строка с максимальным по модулю отрицательным элементом столбца свободных членов. Разрешающий столбец – столбец, с минимальным симплекс отношением, полученным в результате деления элементов F-строки на элементы разрешающей строки.

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

Базовые переменные

Свободные члены

Свободные переменные

Y1

Y4

Y3

–8-(-7*(-9)/12)

–12-(-7*(-7)/12)

–7/12

Y2

9/12

7/12

–1/12

F

0-(-84*(-9)/12)

–84-(-84*(-7)/-12)

–84/12

Базовые переменные

Свободные члены

Свободные переменные

Y3

Y4

Y1

-2,75

-7,91667

-0,58333

Y2

0,75

0,583333

-0,08333

F

63

-35

-7

                План не является оптимальным, т.к. в столбце свободных членов есть отрицательные значения. Значит принимаем за разрешающий элемент -7,91667 и получаем следующую симплекс таблицу:

Базовые переменные

Свободные члены

Свободные переменные

Y3

Y4

Y1

2,75/7,91667

-1/7,91667

0,5833/7,91667

Y2

0,75-(0,583*(-2,75)/ -7,916)

0,583/7,916

-0,083-

(-0,583*0,583/-7,916)

F

63-(-35*(-2,75)/ -7,916)

-35/7,916

-7-(-35*(-0,583)/ 7,916)

Базовые переменные

Свободные члены

Свободные переменные

Y3

Y4

Y1

0,347368421

-0,12632

0,073684

Y2

0,547368421

0,073684

-0,12632

F

75,15789474

-4,42105

-4,42105

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

Ответ:

X1*=0,3473

X2*=0,5473

F*=75.1589

6. Математическая постановка задачи линейного целочисленного программирования.

Многие экономические задачи ха­рактеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуа­ций приводит к моделям дискретного программирования. В об­щем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или мини­мума) целевой функции f(xl,x2,...,xn) на множестве D, опреде­ляемом системой ограничений

                          

где  — некоторое конечное, или счетное, множество. Ус­ловие  называется условием дискретности. Особое место среди дискретных задач занимает целочисленная за­дача линейного программирования в канонической форме (ЦКЗЛП):

                                                           

                               

где   Z+ ={0; 1; 2; ...} — множество неотрицательных целых чи­сел.

(4)       f=8x1+9x2→max

(1)       12x1+7x≤ 84

7x1+12x≤ 84

(2)       x1≥0,   x2≥0

(3)       х1, х2 –целые неотрицательные числа.

Найти значения х1, х2, удовлетворяющие ограничениям (1) – (3) и доставляющие целевой функции (4) максимальное значение.

7. Дать графическую интерпретацию задачи ЛЦП. Выделить множество допустимых точек. Решить графическим способом задачи ЛЦП.

8x1+9x2→max

12x1+7x2 ≤ 84

7x1+12x2 ≤ 84

x1≥0,  x2≥0

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

Оптимальный план - точка В (4,421; 4,421). f(B)= 75,157.

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

x2– дробь; подбираем дополнительное ограничение:

≤ 4 


Проверяем точку (5;4)

8*5+9*4 = 40 + 36 = 76 > 75    Данное решение не попадает в ОДР.

Проверяем точку(5;3)

8*5 + 9*3 = 40 + 27 = 67  < 75  => Данное решение является целочисленным решением

Проверяем точку(4;4)

8*4 + 9*4 = 32 + 36 = 68  < 75  => Данное решение является целочисленным решением, и оно более точное.

Ответ:

x1*=4

x2*=4

F*=68

8. Решение задачи линейного программирования с помощью метода Гомори.

Решение происходит на основе прямого симплекс метода.

Базовые переменные

Свободные члены

Свободные переменные

x3

x4

X1

X2

F

Выбираем свободный член с наибольшей дробной частью.

x2 = + *x3 *x4

Дополнительное ограничение имеет вид

*x3*x4 -  ≥ 0

 

Умножим неравенство на -1 и преобразуем его в уравнение. Введем новую переменную х5

*x3*x4  =

х5 = + *x3 + *x4

Составим симплекс-таблицу.

Базовые переменные

Свободные члены

Свободные переменные

x3

x4

X1

X2

X5

F

Делаем симплекс преобразование.

Базовые переменные

Свободные члены

Свободные переменные

x3

X5

X1

7028/1577

11/83

-7/83

X2

6876/1577

-7/83

12/83

X4

40/83

7/83

-95/83

F

118108/1577

25/83

52/83

Так как в Z-строке есть отрицательный элемент,- решаем дальше.

Выбираем свободный член x4.

x4 =  *x3 *x5

Дополнительное ограничение имеет вид

*x3*x5≥ 0

Умножим неравенство на -1 и преобразуем его в уравнение. Введем новую переменную х6

*x3*x5≥ 0

x6= *x3*x5

Составим симплекс-таблицу.

Базовые переменные

Свободные члены

Свободные переменные

x3

X5

X1

7028/1577

11/83

-7/83

X2

6876/1577

-7/83

12/83

X4

40/83

7/83

-95/83

X6

-40/83

76/83

-12/83

F

118108/1577

25/83

52/83

Делаем симплекс преобразование.

Базовые переменные

Свободные члены

Свободные переменные

x3

X6

X1

4

2/3

-7/12

X2

3

1

1

X4

1

7/3

-95/12

X5

3

19/3

-83/12

F

72

14

52/12

Так как свободный член F целочисленный (72), то целочисленное решение найдено.

Ответ:

X1*=4

X2*=3

F*=72

9. Решение задачи линейного целочисленного программирования с помощью метода ветвей и границ.

(1)       f=8x1+9x2→max

 


(2)       12x1+7x2≤84           

7x1+12x2≤84                                                  

(3)       x1≥0, x2≥0

(4)       х1, х2 –целые неотрицательные числа.

(5)       0≤ х1≤5; 0≤ х2≤5

Снимаем условие целочисленности (4) и решаем задачу1, с условиями 2,3,5

x1=

x2=

W=

Ортимальное решение не целочисленно. Вносим в основной список задач 2 задачи.

Задача2: 4≤ х1≤5; 0≤ х2≤5; (1), (2), (3)

Задача3: 0≤ х1≤4; 0≤ х2≤5

Решаем Задачу2.

При х1=4,

х2==

худовлетворяет условию, следовательно в основной список задач добавляем две задачи:

Задача4:   х1=4; 0≤ х2≤3; (1), (2), (3)

Задача5:   х1=4; 4≤ х2≤5; (1), (2), (3)

При х1=5,

х2==

худовлетворяет условию, следовательно в основной список задач добавляем две задачи:

Задача6:   х1=5; 0≤ х2≤4; (1), (2), (3)

Задача7:   х1=5; 5≤ х2≤5; (1), (2), (3)

Решаем Задачу4.

При х1=4,

х2==

хне удовлетворяет условию, следовательно решений нет.

Решаем Задачу5.

При х1=4 и х2=4,

W=8*4+9*4=68

Решение целочисленно, поэтому запомнаем его.

При х1=4 и х2=5,

W=8*4+9*5=77

Решение целочисленно, но больше чем исходное нецелочисленное решение, поэтому не запомнаем его.

Решаем Задачу6.

При х1=5 и х2=5,

W=8*5+9*5=85

Решение целочисленно, но больше чем исходное нецелочисленное решение, поэтому не запомнаем его.

Решаем Задачу7.

При х1=5,

х2==

хне удовлетворяет условию, следовательно решений нет.

Решаем Задачу3.

При х1=4,

х2==

худовлетворяет условию, следовательно в основной список задач добавляем две задачи:

Задача8:   х1=4; 0≤ х2≤3; (1), (2), (3)

Задача9:   х1=4; 3≤ х2≤5; (1), (2), (3)

Решаем Задачу8.

При х1=4,

хне удовлетворяет условию, следовательно решений нет.

Решаем Задачу9.

При х1=4,

х2==

худовлетворяет условию, следовательно в основной список задач добавляем две задачи:

Задача10:   х1=4; 3≤ х2≤4; (1), (2), (3)

Задача11:   х1=4; 4≤ х2≤5; (1), (2), (3)

Решаем Задачу10.

При х1=4 и х2=3,

W=8*4+9*3=59

Решение целочисленно, поэтому запомнаем его.

При х1=4 и х2=4,

W=8*4+9*4=68

Решение целочисленно, поэтому запомнаем его.

Решаем Задачу11.

При х1=4,

х2==

хне удовлетворяет условию, следовательно решений нет.

Список задач пуст.

Таким образом, имем два оптимальных целочисленных решения:

1)  х1=4; х2=3; W=8*4+9*3=59

2)  х1=4; х2=4; W=8*4+9*4=68

Так как 68>59 то решением примем 2 решение.

Ответ:

х1*=4

х2*=4;

F*=68

Общий вывод:

Задача линейного программирования была решена пятью методами

Похожие материалы

Информация о работе