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

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

Рубрика Экономико-математическое моделирование
Вид задача
Язык русский
Дата добавления 11.07.2010
Размер файла 579,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

16

Задание 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

-1/2

18/8

-22

x1

1

1/8

-3/8

0

-1/4

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

-1/2

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

-1/2

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

131338

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 - платежей от потребителей, чтобы общая сумма оплаты поставщикам за предоставленный груз была бы максимальной.

Ответ:, .


Подобные документы

  • Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.

    контрольная работа [398,2 K], добавлен 15.08.2012

  • Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.

    дипломная работа [311,3 K], добавлен 17.01.2014

  • Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.

    реферат [193,4 K], добавлен 28.12.2008

  • Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.

    курсовая работа [458,6 K], добавлен 10.12.2013

  • Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.

    курсовая работа [54,1 K], добавлен 05.03.2010

  • Построение одноиндексной математической модели задачи линейного программирования, ее решение графическим методом. Разработка путей оптимизации сетевой модели по критерию "минимум исполнителей". Решение задачи управления запасами на производстве.

    контрольная работа [80,8 K], добавлен 13.12.2010

  • Понятие "транспортная задача", ее типы. Отыскание оптимального плана перевозок однородного груза, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок. Решения прямой и двойственной задачи линейного программирования.

    контрольная работа [81,9 K], добавлен 14.09.2010

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

    курсовая работа [106,0 K], добавлен 05.10.2014

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

    контрольная работа [187,0 K], добавлен 23.05.2010

  • Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.

    контрольная работа [467,8 K], добавлен 13.06.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.