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

Цели и задачи дисциплины

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

Задачами дисциплины являются: обучение бакалавров

· теоретическим основам принятия решений;

· математическим основам синтеза оптимального решения;

· критериям выбора оптимального решения в условиях определенности, неопределенности и риска.

Предмет изучения дисциплины -алгоритмы принятия решений в процессе управления сложными системами.

Место дисциплины в структуре ООП

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

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

3. Требования к результатам освоения дисциплины:

Процесс изучения дисциплины направлен на формирование следующих компетенций:

а) общекультурных

1. Способен самостоятельно приобретать и использовать в практической деятельности новые знания и умения, стремится к саморазвитию (0К-5);

2. Способен понимать сущность и проблемы разразвития современного информационного общества (0К-7);

3. Обладать культурой мышления, способностью к обощению, анализу, систематизации, постановке целей и выбору путей их достижения; умеет логически верно, аргументированно и ясно строить свою речь. (0К-17);

б) профессиональных

Общепрофессиональными

4. Способен при решении профессиональных задач анализировать социально-экономические проблемы и процессы с применением методов системного анализа и математического моделирования (ПК-2).

5. Способен применять методы анализа прикладной области на концептуальном, логическом, математическом и алгоритмическом уровнях (ПК-17)

6. Способен применять системный подход и математические методы в формализации решения прикладных задач (ПК-21)

 

В результате изучения дисциплины студент должен:

 

ЗНАТЬ:

· Анализ полезности.

· Оптимальные статистические решения..

· Сущность и принципы системного подхода.

· Теорию оптимального управления.

· Моделирование как метод анализа систем и принятия решений.

· Измерительные шкалы.

· Расплывчатое и вероятностное описание ситуаций

 

УМЕТЬ:

· Выполнять анализ систем.

· Грамотно формулировать цели.

· Выбирать модель принятия решений и критерии отбора.

· Владеть технологиями синтеза управляющих решений.

· Реализовывать принятые решения.

ВЛАДЕТЬ навыками принятия решений:

· в условиях определенности.

· в условиях неопределенности.

· для систем массового обслуживания.

· в условиях противодействия.

Характеристика контрольной работы.

Контрольная работа состоит из двух разделов.

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

Второй вопрос – решение задачи линейного программирования графическим методом с обязательной проверкой в пакете EXCEL (опция «Поиск решения»).

Варианты задания

ПЕРВЫЙ ВОПРОС. Составить реферат по теме (в соответствии с вариантом)

1. Базовые понятия и определения задач принятия решений

2. Классификация задач принятия решений

3. Основные классы концептуальных задач теории принятия решений

4. Основные понятия о структурировании множества альтернатив

5. Классификация методов структурирования множества альтернатив

6. Связь различных способов описания выбора. Однокритериальный и многокритериальный выбор

7. Основные этапы процесса принятия решений.

8. Критерии в процессе принятия решений

9. Роль человека в процессе принятия решений

10. Метод анализа иерархий. Синтез приоритетов

11. Метод анализа иерархий. Согласованность локальных приоритетов

12. Метод анализа иерархий. Синтез альтернатив.

13. Метод анализа иерархий. Этапы метода анализа иерархий

14. Характеристика условий неопределенности в процессе принятия решений

15. Принятие решений в условиях неопределенности

16. Критерии принятия решений в условиях неопределенности

17. Классификация рисков в процессе принятия решений

18. Производственные и коммерческие риски

19. Финансовые риски и риски, возникающие на уровне государства

20. Подходы к учету неопределенности при описании рисков

21. Вероятностно-статистические методы принятия решений. Социально-экономическое прогнозирование

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

23. Вероятностно-статистические методы принятия решений. Экспертные методы прогнозирования

24. Вероятностно-статистические методы принятия решений. Проблемы применения методов прогнозирования в условиях риска

25. Критерии принятия решений в условиях риска. Критерий ожидаемого значения

26. Критерии принятия решений в условиях риска. Критерий «ожидаемое значение- дисперсия»

27. Критерии принятия решений в условиях риска. Критерий предельного уровня

28. Линейные оптимизационные модели. Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

29. Типовые задачи линейного программирования. Задача об оптимальном использовании ресурсов при производственном планировании

30. Типовые задачи линейного программирования. Задача о смесях (планировании состава продукции)

31. Типовые задачи линейного программирования. Транспортная задача

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

33. Построение опорного плана транспортной задачи

34. Улучшение начального опорного плана

35. Нелинейное программирование. Метод неопределенных множителей Лагранжа

36. Модель динамического программирования. Принцип оптимальности Беллмана

37. Задача распределения ресурсов. Постановка задачи. двумергная модель распределения ресурсов.

38. Построение дерева целей

39. Задачи сетевого планирования

40. Задача управления запасами. Постановка задачи.

41. Основная модель управления запасами. Направления в моделировании управления запасами

42. Теоретико-игровые модели принятия решений.

43. Классификация игр

44. Матричные игры. Решение матричных игр в чистых стратегиях

45. Системы массового обслуживания (СМО). Одноканальная СМО с отказами

46. Системы массового обслуживания. Многоканальная СМО с отказами.

47. Классические методы решения оптимизационных задач

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

49. Численные методы однопараметрической оптимизации. Метод дихотомии

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

51. Методы многомерной оптимизации. Метод штрафных функций.

52. Поисковые методы многомерной оптимизации. Метод релаксации.

53. Поисковые методы многомерной оптимизации. Метод градиента

54. Поисковые методы многомерной оптимизации. Метод наискорейшего спуска

55. Безградиентные методы оптимизации поиска. Метод сканирования

56. Безградиентные методы оптимизации поиска. Метод Гаусса-Зейделя

ВТОРОЙ ВОПРОС Найти графическим методом решение задачи линейного программирования (в соответствии с вариантом)

Задача 1

z= 2x₁ + 3x₂→max;

x₁ + 2x₂ ≥4;

2x₁ -x₂ ≥9;

5x₁+ 3x₂ ≤ 30;

4x₁ - l- 7x₂≤28;

x₁ ≥ 0, x₂ ≥ 0.

Задача 2

z= 3x₁ - 3x₂→max;

x₁ - 4x₂ ≤ 4;

3x₁ + 2x₂ ≤ 6;

-x₁ + x₂ ≥ 7;

x₁ + 2x₂ ≤ 2;

x₁ ≥ 0, x₂ ≥ 0.

Задача 3

z= 3x₁ + 4x₂→max;

-2x₁ + x₂ ≤ 1;

4x₁+ 6x₂ ≤ 12;

6x₁ + 3x₂ ≤ 9;

x₁ + x₂ ≥ 6;

2x₁ – 4x₂ ≥ 2;

x₁ ≥ 0, x₂ ≥ 0.

Задача 4

z = x₁ + 2x₂→max;

x₁ + x₂ ≤ 4;

3x₁ + x₂ ≥ 4;

x₁ + 5x₂ ≥ 4;

x₁ ≤ 3;

x₂ ≤ 3;

x₁ ≥ 0,

x₂ ≥ 0.

Задача 5

z = x₁ + x₂→max;

-4x₁ + x₂ ≤ 1;

2x₁ - 3x₂ ≤ 6;

2x₁ + x₂ ≤ 8;

-x₁ +x₂≤7;

x₁ + 2x₂ ≥ 2;

x₁ ≥ 0, x₂ ≥ 0.

Задача 6

z= 2x₁ + x₂→max;

2x₁- x₂ ≥ 4;

3x₁ + 2x₂ ≥ 3;

3x₁ - x₂ ≤ 6;

7x₁ + x₂ ≤ 7;

x₁ ≥ 0, x₂ ≥ 0.

Задача 7

z = x₁ + x₂ →max;

-4x₁ + x₂ ≤ 2;

2x₁ - 3x₂ ≤ 3;

2x₁ + x₂ ≤ 8;

x₁ - 4x₂≤4;

x₁ ≥0, x₂≥0.

Задача 8

z = 7x₁ + 6x₂ →max;

2x₁+ 5x₂ ≥ 10;

5x₁ + 2x₂≥ 10;

x₁ ≤6;

x₂≤5;

x₁ ≥ 0, x₂ ≥ 0.

Задача 9

z = x₁+ x₂ - x₃ + x₅ + 15→min;

-3x₁ + x₂ + x₃ = 3;

4x₁ + 2x₂ - x₄ = 12;

2x₁ ^_ x₂ + x₅ = 2;

x₁, x₂, x₃, x₄, x₅ ≥0.

Задача 10

z = x₁ + 2x₂ + x₄ + 3x₅ + 6→ max;

x₁ - 2x₂ + x₃ = 1;

2x₁ + x₂ — x₄ = 8;

x₁ + 2x₂ + x₅ = 3;

x₁, x₂, x3, x4, x₅ ≥ 0.

Задача 11

z = x₁ + 5x₂→min;

x₁ - 2x₂ ≤ 2;

-2x₁ - 3x₂ ≤ -4;

-2x₁ + x₂≤ 2;

x₁ ≥ 0, x₂ ≥ 0.

Задача 12

z = 3x₁ + x₂→max;

-x₁ + x₂ ≥ 1;

x₁ + 3x₂ ≤ 15;

-2x₁ + x₂ ≤ 4;

x₁ ≥0,x₂ ≥0.

Задача 13

z =x₁ + 2x₂ + x₄ + x₅ + 3 → max;

- x₁ - 2x₂ + x₃ = 1;

2 x₁ + x₂-x₄ = 4;

x₁ + 2x₂ + x₅ = 5;

x₁, x₂, x₃, x₄, x₅ → 0.

Задача 14

z= 3x₁ + 2x₂ →min;

x₁ - 2x₂ ≤ 1;

-2x₁ - 3x₂ ≤ -2;

-2 x₁ + x₂ ≤ 4;

x₁ ≥ 0, x₂ ≥ 0.

Задача 15

z= 3x₁ + 4x₂ → max;

x₁ + 2x₂ ≤ 4;

-2x₁ - 2x₂ ≥ 2;

2 x₁ + 4x₂ ≤ 8;

x₁ + 3x₂ ≤ 6;

4x₁ - 2x₂ ≤ 4;

x₁ ≥0, x₂≥ 0.

Задача 16

z = 5x₁ + x₂ → min;

x₁ + 7x₂ ≥ 7;

5 x₁ + 2x₂≥ 10;

-2x₁ + x₂ ≤ 6;

7x₁ + x₂ ≥ 7;

2x₁ + 5x₂ ≥ 10; 2 x₁ ≤ 12;

x₂≤7;

x₁ ≥ 0, x₂ ≥ 0.

Задача 17

z= 3x₁ - x₂ + 2x₃ - x₄ - 3 → min;

- x₁ + 2x₂-x₃ = 1;

2x₁ - x₂ + x₅ = 5;

x₁ + x₂ - x₄ = 2;

x_1, x_2, x_3, x_4, x₅≥0

Задача18

z= -6x₁ + 8х₂→ min;

9x₁ + Зх₂ ≥ 9;

-2x₁ + 2х₂ ≤ 4;

2x₁- Зх₂ ≤ -5;

x₁ ≥ 0, х₂ ≥ 0.

Задача19

z= -2x₁ + 4х₂ + 6→min;

x₁ - 3x₂ ≤ 1;

x₁ + х₂ ≤ 5;

-x₁ + x₂ ≤ 2;

x₁ ≥ 0, х₂ ≥ 0.

Задача20

z = 2x₁ + 2х₂→mах;

x₁ - х₂ ≥ - 4;

6x₁ + 7х₂ ≤ 42;

Зx₁ – 2x₂ ≤ 6;

х₂≤4;

x₁ ≥ 0, х₂ ≥ 0.

Задача21

z= 5x₁ - Зх₂→min;

Зx₁ + 2х₂ ≥ 6;

2x₁ - Зх₂ ≥ - 6;

x₁ - х₂ ≤ 4;

4x₁ + 7х₂ ≤ 14;

x₁ ≥ 0,х₂ ≥ 0.

Задача22

z= 5x₁ + Зх₂→min;

2x₁ + 2х₂ ≥ 6;

2x₁ – 2x₂ ≥ -6;

x₁ + 2х₂ ≤ 4;

4x₁ + Зх₂ ≤ 12;

x₁ ≥ 0, х₂ ≥ 0.

Задача23

z = 2x₁ - Зх₂→min;

Зx₁ + 2х₂ ≥ 6;

x₁ - 0,5x₂ ≤ 2;

x₁ + 2,5х₂ ≤ 5;

x₁ ≥ 0, х₂ ≥ 0.

Задача24

z = 2x₁ - 4х₂→mах;

8x₁ – 5x₂ ≤ 16;

x₁ + Зх₂ ≥ 3;

2x₁ + 5х₂ ≤ 10;

x₁ ≥ 0, х₂ ≥ 0.

Задача25

z = x₁ + 2х₂ →min;

-Зx₁ + 2х₂ ≤ 9;

Зx₁ + 4х₂ ≥ 28;

2x₁ + х₂ ≤ 8;

x₁ ≥ 0, х₂ ≥ 0.

Задача26

z = x₁ + Зх₂→mах;

-Зx₁ + 4х₂ ≤ 12;

Зx₁ + Зх₂ ≤ 9;

Зx₁ - 4х₂ ≤ 3;

2x₁ + Зх₂ ≤ 6;

x₁ ≥ 0, х₂ ≥ 0.

Задача27

z = 2x₁ - 4х₂→min;

4x₁ + Зх₂ ≤ 12;

x₁ + Зх₂ ≥ 6;

2x₁ + 5х₂ ≤ 10;

x₁ ≥ 0, х₂ ≥ 0.

Задача28

z = 2x₁ + Зх₂→mах;

2x₁ - 4х₂ ≥ 8;

x₁ + х₂ ≥ 4;

Зx₁ + 6х₂ ≤ 12;

x₁ ≥ 0, х₂ ≥ 0.

Задача29

z = x₁ + 4х₂→mах;

- x₁ + х₂ ≤ 5;

x₁ + х₂ ≤ 8;

Зx₁ + 2х₂ ≤ 18;

x₁ ≥ 0, х₂ ≥ 0.

Задача 30

z = 4 x₁ + 2х₂→min;

x₁ + 4х₂ ≥ 8;

5x₁ + Зх₂ ≥ 15;

7x₁ + х₂ ≥ 7;

Зx₁ + 5х₂ ≥ 15;

x₁ ≥ 0, х₂ ≥ 0.

Задача 31

z = 2x₁ + х₂→mах;

-x₁ + 2х₂ ≤ 14;

7x₁ + 4х₂ ≤ 28;

4x₁ - Зх₂ ≤ 12;

5x₁ + 2х₂ ≥ 10;

10x₁ - 8х₂ ≥ 2;

x₁ ≥ 0, х₂ ≥ 0.

Задача 32

z = x₁ - Зх_2→ min;

x₁ + х₂ ≤ 3;

- x₁ + 2х₂ ≤ 5;

x₁ ≥ 0, х₂ ≥ 0.

Задача33

z = x₁ + 2х₂→min;

-Зx₁ +4х₂ ≤ 12;

x₁ + 4х₂ ≥ 4;

Зx₁ - 4х₂ ≥ 10;

x₁ ≥ 0, х₂ ≥ 0.

Задача34

z = x₁ + х₂→mах;

З x₁ + х₂ ≤ 20;

2x₁ + Зх₂ ≤ 30;

x₁ ≥ 0, х₂ ≥ 0;

Задача35

z = x₁ + х₂→mах;

x₁ + Зх₂ ≤ 30;

2x₁ + х₂ ≤ 20;

x₁ ≥ 0, х₂ ≥ 0.

Задача36

z = 2x₁ + х₂→mах;

2x₁ + 6х₂ ≤ 15;

4x₁ + Зх₂ ≤ 11;

x₁ ≥ 0, х₂ ≥ 0.

Задача 37

Z = 2x₁ + 2х₂→max;

0,2x₁ + Зх₂ ≤ 24;

0,5x₁ + 0,1x₂ ≤ 5;

Зx₁ + 2x₂ ≤ 30;

x₁ ≥ 0, х₂ ≥ 0.

Задача 38

z = x₁ + x₂→max;

Зx₁ + х₂ ≤ 20;

2x₁ + Зх₂ ≤ 30;

x₁ ≥ 0, х₂ ≥ 0.

Задача 39

z = x₁ - Зх₂→min;

- x₁ + 2х₂ ≤ 6;

x₁ + 2х₂ ≤ 5;

x₁ ≥ 0, х₂ ≥ 0.

Задача 40

z = 2 x₁ + х₂→max;

2x₁ + 6х₂ ≤ 15;

4x₁ + 3x₂ ≤ 11;

x₁ ≥ 0, х₂ ≥ 0;

Задача 41

z = 2x₁ + 2х₂→min;

x₁ + x₂ ≥ 4;

-x₁ + 2х₂ ≤ 8;

5x₁ + 2х₂ ≤ 10;

x₁ ≥ 0, х₂ ≥ 0.

Задача 42

z = x₁ - 4х₂→min;

3x₁ + 5х₂ ≥ 8;

-Зx₁ + 10х₂ ≤ 16;

x₁ ≥ 0, х₂ ≥ 0.

Задача 43

z = Зx₁ + 2х₂ →max;

x₁ ≥ 1;

x₂ ≥0,6;

0,1x₁ + 0,4x₂ ≤ 2;

x₁ ≥ 0, x₂ ≥ 0.

Задача 44

z = x₁ + 2х₂→max;

-Зx₁ + 2х₂ ≤ 9;

Зx₁ + 4х₂ ≥ 28;

2x₁ + x₂ ≤ 8;

x₁ ≥ 0, x₂ ≥ 0.

z = x₁ + x₂→max;

-4x₁ + x₂ ≤ 1;

2x₁ – 3x₂ ≤ 6;

2x₁ + x₂ ≤ 8;

-x₁ + x₂ ≤ 7;

x₁ + 2x₂ ≥ 2;

x₁ ≥ 0, x₂ ≥ 0.

z = x₁ + x₂→max;

3x₁ + x₂ ≤ 20;

2x₁ + 3x₂ ≤ 30;

x₁ ≥ 0,x₂ ≥ 0.

z = x₁ +x₂-x₃ +x₅ + 15→min;

-3x₁ + x₂ + x₃ = 3;

4x₁ + 2x₂ - x₄ = 12;

2x₁ – x₂ + x₅ = 2;

x_1, x_2, x_3, x_4, x₅ ≥ 0

x = 3x1 + 2x2 →max;
0,1x1 + 0,4x2 ≤4;
Зx1 + 5x2 ≤ 15;
x1 + x2 ≥ 1;
x2 ≥ 0,6;
x1 ≥1.
z = 5x1 + x2 →max;
3x1 + 6x2 ≤ 11;
x1 ≤ 2,75;
3x2 ≤ 1,1;
x1 ≥ о, x2 ≥ 0.
z = x1 + 2x2 + х4 + x5 + 3→min;
-x1 – 2x2 + x3 = 1;
2x1 + x2 + x3 = 4;
x1 + 2x2 + x5 = 5;
x1, x2, x3, x4, x5 ≥ 0

 

Указания Вариант задания по первому и второму вопросам для каждого студента выбирают по двум последним цифрам номера студенческого билета.

Оформление контрольной работы должно соответствовать требованиям к оформлению текстовых документов. Для задачи необходимо приложить распечатку результатов решения в EXCEL.

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

Задача

Найти , доставляющие максимум критерию

при условиях: (1)

Решение:

Учитывая, что поставленную задачу можно решить, используя геометрическую интерпретацию ЗЛП.

Пусть – свободные переменные

– базисные переменные

Тогда:

Т.к. , то получим область допустимых решений на плоскости :

Принимая знак равенства, в (3) получаем 4 уравнений прямых , определяющих границу области допустимых решений.

Определим направление градиента:

minI находится на границе области допустимых решений в направлении антиградиента: