Линейное программирование и методы оптимизации

Тип работы:
Задача
Предмет:
Экономические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Задание 1.

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

Решение:

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

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

ОДР — многоугольник. Построим n=grad z=(2,1) и основную прямую z=0, перпендикулярную n.

Перемещая прямую z=0 в направлении n, получим, что последней крайней точкой, в которой прямая пересекается с ОДР, будет точка, в которой достигается максимальное значение целевой функции z. Координаты этой точки определяются решением системы двух линейных уравнений (I) и (II), на пересечении которых она находится. В результате решения системы уравнений (I) и (II) получим оптимальное решение x*:

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

Введём двойственные переменные; тогда двойственная задача будет иметь вид:

Задание 2.

Графическим способом решить задачу линейного программирования (). Сформулировать задачу двойственную по отношению к данной.

Решение:

Построим область допустимых решений на плоскости Ох1х2. Для этого запишем уравнения прямых из системы ограничений, заменяя неравенства равенствами:

Определим полуплоскости, которые задают неравенства-ограничения. Построим вектор и основную прямую, перпендикулярную

16

Перемещая прямую z=0 в направлении, получим, что первой крайней точкой, в которой прямая пересекается с ОДР, будет точка А. Следовательно в этой точке достигается минимальное значение целевой функции z. Координаты точки, А определяются решением системы 2-х линейных уравнений (I) и (II), на пересечении которых она находится.

В результате получаем оптимальное решение:

Сформулируем двойственную задачу.

Двойственная задача имеет вид:

Ответ.

Задание 3.

Построить математическую модель задачи и решить её с использованием симплекс-таблиц. Сформулировать соответствующую двойственную задачу и дать её экономическую интерпретацию.

На предприятии имеется несколько производственных линий. j-я линия производит в единицу времени единиц продукции i-го типа. Для выполнения задания предприятию необходимо выпускать не менее единиц i-го типа продукции, при этом эксплутационные расходы j-й линии составляют млн. руб. в единицу времени. Определить время работы каждой линии для выполнения задания при условии минимизации затрат.

Решение:

Постановка задачи в общем виде:

количество усл. ед. j-вида продукции.

Подставим исходные данные:

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

Б

x1

x2

x3

x4

y1

y2

z /

0

z

2

3

3

4

0

0

0

5

1

0

1

-1

0

10

2

1

3

2

0

-1

12

1

z

2

3

3

4

0

0

0

y1

-5

-1

0

-1

1

0

-10

y2

-2

-1

-3

-2

0

1

-12

2

z

-13

0

3

1

3

0

-30

x2

5

1

0

1

-1

0

10

y2

3

0

-3

-1

-1

1

-2

3

z

-10

0

0

0

2

1

-32

x2

8

1

-3

0

-2

1

8

x4

-3

0

3

1

1

-1

2

4

z

0

10/8

-30/8

0

18/8

-22

x1

1

1/8

-3/8

0

1/8

1

x4

0

3/8

15/8

1

ј

-5/8

5

5

z

0

2

0

2

0

2

-12

x1

1

Ѕ

12/8

1

0

6

y1

0

12/8

15/2

4

1

-5/2

20

Все коэффициенты в строке целевой функции и в столбце положительны, поэтому полученное решение является оптимальным.

Сформулируем двойственную задачу.

Экономическая интерпретация двойственной задачи:

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

Ответ:

Задание 4.

Построить математическую модель задачи и решить её с использованием симплекс-таблиц. Сформулировать соответствующую двойственную задачу и дать её экономическую интерпретацию.

При выпуске одной усл. ед. j-го вида товаров необходимо усл. ед. i-го типа сырья, при этом в виде отходов получают усл. ед. k-го типа сырья. При реализации одной усл. ед. j-го вида товаров выручают тыс. руб. От поставщиков не может поступать более усл. ед. i-го типа сырья. Рассчитать план выпуска каждого вида товаров для получения наибольшей прибыли.

Решение:

Постановка задачи в общем виде:

количество усл. ед. j-вида ресурса.

Подставим исходные данные:

Приведем ЗЛО к ОЗЛО, т. е. перейдем от ограничений-неравенств к ограничениям-равенствам путем введения новых переменных.

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

Б

x1

x2

x3

y1

y2

y3

z /

0

z

-2

-3

-2

0

0

0

0

y1

6

2

2

1

0

0

10

y2

0

4

1

0

1

0

3

y3

4

5

5

0

0

1

11

1

z

-2

0

-5/4

0

ѕ

0

9/4

y1

6

0

3/2

1

0

17/2

x2

0

1

ј

0

ј

0

ѕ

y3

4

0

15/4

0

-5/4

1

29/4

2

z

-2/3

0

0

0

1/3

1/3

14/3

y1

22/5

0

0

1

0

-2/5

28/5

x2

-4/15

1

0

0

1/3

-1/15

4/15

x3

16/15

0

1

0

-1/3

4/15

29/15

3

z

0

0

0

5/33

1/3

3/11

182/33

x1

1

0

0

5/22

0

-1/11

14/11

x2

0

1

0

2/33

1/3

-1/11

20/33

x3

0

0

1

-8/33

-1/3

4/11

19/33

Все коэффициенты в строке целевой функции и в столбце положительны, поэтому полученное решение является оптимальным.

Сформулируем двойственную задачу.

Экономическая интерпретация двойственной задачи:

Найти такую совокупность стоимостей единицы продукции i-го вида товара, при которых общая стоимость производимого товара была бы минимальной, при условии что суммарная цена единиц всех видов производимого товара была бы не меньше выручки при реализации одной условной ед. j-го вида товара.

Ответ:

Задание 5.

Пi

Зj

45

38

40

28

34

20

3

17

6

19

2

40

1

15

7

6

1

52

5

13

8

11

17

73

18

13

17

1

8

Завод имеет 4 цеха А, B, C, D и 5 складов. Производительность 1-го цеха за смену П1 тыс. шт. деталей, i =1,4; пропускная способность j-го склада за это же время составляет Е1 тыс. шт. деталей, j=1,5;. Стоимост перевозок 1 тыс. шт. деталей из цеха 1 в склад j задаются матрицей РРCijРР

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

Решение.

Пi

45

38

40

28

34

i

20

53

717

8 6

-519

2220

0

40

41+

615

7733-

-66

117

-1

52

5545-

713

887+

-511

217

0

73

1318

131 338

1417

1128

887

6

j

5

7

8

-5

2

Пi

45

38

40

28

34

i

20

23

1317

5 6

119

22

20

0

40

11

33+

1215

47

06

11

7-

-1

52

55

12-

1613

+

88

40

411

517

3

73

218

1313

38-

517

11

28

88

7+

0

j

2

13

5

1

2

Пi

45

38

40

28

34

i

20

-13

717

2 6

-519

22

20

0

40

1 1

40

915

47

36

41

+

2

52

55

5+

1313

7-

88

40

111

817

6

73

518

1313

31+

817

11

28

88

14-

6

j

-1

7

5

-5

2

Пi

45

38

40

28

34

i

20

23

717

5 6

-519

22

20

0

40

1 1

40

615

47

-66

41

+

-1

52

55

12

1013

88

40

-211

517

3

73

818

1313

38

1117

11

28

88

7

6

j

2

7

5

-5

2

План является оптимальным.

Задание 6.

На 5 складах находится по m горючего,. Его нужно перевести к 4 АЗС, потребности которых составляют m,. Стоимость перевозок от j-го склада к i-й АЗС задаются матрицей Составить такой план перевозки горючего, при котором транспортные расходы будут наименьшими.

Пi

Зj

90

120

170

125

75

110

9

3

1

4

6

190

4

9

3

7

15

130

3

8

4

13

7

150

7

4

9

5

10

Решение.

Пi

Зj

90

120

170

125

75

110

9

3

1

4

6

190

4

9

3

7

15

130

3

8

4

13

7

150

7

4

9

5

10

Постановка транспортной задачи в общем виде:

количество единиц груза, которое нужно доставить из i-ПО в j-ПН

Подставим исходные данные:

транспортная задача является закрытой.

Решим транспортную задачу с помощью транспортной таблицы методом потенциалов.

число базисных клеток.

Составим план перевозок методом наименьшей цены.

90

120

170

125

75

i

110

29

43

11

110

54

66

0

190

44

35

69

33

60

77

95

815

2

130

33

55

58

24

613

77

75

1

150

27

44

120

19

55

30

610

0

j

2

4

1

5

6

План можно улучшить, так как есть свободные клетки, где псевдостоимость больше стоимости (5> 4). Рассмотрим цикл, который минимизирует план на 95 единицы. Получился новый план. Снова рассчитаем псевдостоимости.

90

120

170

125

75

i

110

29

33

1 1

15

44

95

66

0

190

4 4

35

59

33

155

67

815

2

130

33

55

48

24

513

77

75

1

150

37

44

120

29

55

30

710

1

j

2

3

1

4

6

полученный план перевозок является оптимальным.

Сформулируем двойственную задачу:

Экономическая интерпретация двойственной задачи:

Найти такую совокупность u1…u9 — платежей от потребителей, чтобы общая сумма оплаты поставщикам за предоставленный груз была бы максимальной.

Ответ: ,.

ПоказатьСвернуть
Заполнить форму текущей работой