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

Лабораторная работа № 1

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

Цель  работы:  приобретение  практических  навыков  применения методов  линейного  программирования  для  формализации экономических процессов.

Вариант №7

Ход работы

1. Область допустимых планов

F = 16x1 + 12x2     max         

2x1 + 3x2 ≤ 180

4x1 + x2 ≤ 240

6x1 + 7x2 ≤ 426

x1, x2 ≥ 0

1) x1 = 0, x2 = 180/3 = 60    2)x1 = 0, x2 = 240               3) x1 = 0, x2 = 426/7 = 61

x2 = 0, x1 = 180/2 = 90       x2 = 0, x1 = 240/4 = 60         x2 = 0, x1 = 426/6 = 71

x2

 

 

 x1

 

Метод перебора вершин

О (0;0)

A (0;60)

B (4,5; 57)

пересечение прямых 1 и 3

2x1 + 3x2 = 180

6x1 + 7x2 = 426

x1= = 90 – 1,5x2

6 (90 – 1,5x2) + 7x2 = 426

 

540 – 9x2 + 7x2 = 426

114 = 2x2

x2 = 114/2 = 57

x1 = 30 – 1,5*57 = 4,5

 

C (57;12)

пересечение прямых 2 и 3

4x1 + x2 =240

6x1 + 7x2 = 426

 

x2 = 240 – 4x1

6x1 + 7(240 – 4x1) = 426

 

6x1 + 1680 – 28x1 = 426

1254 = 22x1

x1 =  57

x2 = 240 – 4*57 = 12

 

D (60; 0)

 

F0 = 0

FA = 0*16 + 12*60 = 720

FB = 16*4.5 + 12*57 = 756

FC = 16*57 + 12*12 = 1056 – максимальное значение

FD = 16*60 + 12*0 = 960

 

Вывод: максимальное значение целевой функции достигается в точке С, значит для достижения максимальной прибыли, равной 1056 денежных единиц, необходимо  расходовать 57 единиц корма для лисицы и 12 единиц корма для песца.

 

 

 

 

2. Построение градиента  и определение оптимального плана.

 

 x2

240

 

 

 

 10 0 61 71 90 x1

ЛУЦФ 

16x1 + 12x2 = 160

 

Вывод: ЛУЦФ в крайнем положении касается точки С области допустимых планов, в значит точка С – единственный оптимальный план.

Fmax = 16*57 + 12*12 = 1056

 

3. Решение задачи симплекс-методом

F = 16x1 + 12x2

2x1 + 3x2 + x3 = 180

4x1 + x2 + x4 =240

6x1 + 7x2 + x5 =426

 

 x3 = 180 - 2x1 - 3x2

x4 =240 - 4x1 - x2

x5 =426 -6x1 - 7x2

 

 

 

Вывод: Для получения наибольшего дохода, равного 1056 денежных единиц, предприятие должно затрачивать 57 единиц корма для лисицы и 12 единиц корма для песца. При этом 2 и 3 корм будут израсходованы полностью, а от 1 корма останется 30 единиц.