5.2 Алгоритм решения практических заданий

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

1. Строится область допустимых решений (из системы ограничений).

2. Строится вектор с точкой приложения в начале координат.

3. Перпендикулярно вектору проводится одна из линий уровня, например, линия уровня, соответствующая уравнению c₁x₁+c₂x₂=0.

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться max или min функции.

В зависимости от вида ОДР и целевой функции Z(X) задача может иметь единственное решение, представленное на рис. 1а, бесконечное множество решений – рис. 1б или не иметь ни одного оптимального решения – рис. 1в.

На рис. 1а линия уровня дважды становится опорной по отношению к ОДР. Минимальное значение целевой функции линия уровня обеспечивает в точке А, а максимальное - в точке С. На рис. 1б минимальное значение целевая функция принимает на опорной прямой, совпадающей с одной из сторон многоугольника. На рис. 1в ОДР не ограничена в сторону увеличения значений целевой функции. Значит, целевая функция максимального значения не имеет.

Рисунок 1 - График построения целевой функции и области допустимых значений

Пример. Решить задачу линейного программирования графическим способом Z (X) = 2x₁ + 4x₂  max.

Решение:

1. Построим на плоскости X₁OX₂ граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе): -2x₁ + 3x₂ = 12  l₁, x₁ +x₂ = 9  l₂, 3x₁ – x₂ = 12  l₃, x₁ = 0  l₄,

x₂ =0  l₅.

Область допустимых решений определяется многоугольником ОАВСД, представленным на рис. 2.

Рисунок 2 - Построение ОДЗ

2. Для линии уровня 2x₁ + 4x₂ = c (const) строим нормальный вектор n (2,4).

3. Перпендикулярно вектору n построим линию уровня, проходящую через начало координат (2x₁ + 4x₂ = 0 ).

1. Перемещаем линию уровня параллельно самой себе в направлении вектора n (т.к. задача на нахождение max целевой функции) до опорной прямой. В данном случае опорной прямой является прямая, проходящая через т.В. Точка В получается при пересечении двух граничных прямых l₁ и l₂. Для определения координат точки В решаем систему уравнений

Получаем: x₁ = 3 , x₂ = 6. Это и будет оптимальное решение данной задачи, которому соответствует максимальное значение целевой функции

Z_max (X) = 23 + 46 = 30.

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

Симплексный метод – это метод целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить, что оптимального решения нет (не существует).

Основное содержание метода состоит в следующем:

1. Указать способ нахождения начального (опорного) решения.

2. Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции ближе к оптимальному.

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

Пусть поставлена задача линейного программирования: среди неотрицательных решений системы уравнений

Найти такие решения, которые максимизировали (минимизировали) бы целевую функцию Z (X) = c₁x₁ + c₂x₂ + … + c_nx_n .

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

Выразим x₁, x₂, …, x_r (rm) через остальные переменные:

где b₁ 0, b₂ 0,…, b_r 0. Если ограничительные условия заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных балансовых переменных. Ограничительные условия могут задаваться и смешанным образом, т.е. неравенствами и уравнениями, тогда указанным способом их можно свести только к уравнениям. Переменные (неизвестные) x₁, x₂, …, x_r называются базисными, а весь набор { x₁, x₂,…, x_r}- базисом, остальные переменные называются свободными, система ограничений называется системой, приведенной к единичному базису. Подставляя в целевую функцию вместо базисных переменных их выражения через свободные из системы, получим

Z(X) =_r+1x_r+1+_r+2x_r+2+ … +_nx_n.

Теперь, полагая все свободные переменные равными нулю, найдем значения базисных переменных: x₁ = b₁, x₂ = b₂ , …, x_r = b_r. Таким образом, решение ( b₁, b₂,…, b_r, 0, …, 0) является допустимым- оно называется базисным. Решение задачи с помощью симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б мы переходим к другому базису Б с таким расчетом, чтобы значение целевой функции увеличивалось или, по крайней мере, не уменьшалось.

Пример. Максимизировать целевую функцию Z (X) = -x₄ + x₅ при ограничениях: x₁+ x₄– 2x₅ =1, x₂ –2x₄+ x₅ =2, x₃ + 3x₄ + x₅ =3.

Решение. Данная система уравнений-ограничений совместна, т.к. ранги матрицы системы

и расширенной матрицы

совпадают и равны 3. Следовательно, система уравнений совместна и три переменные (базисные) можно линейно выразить через две свободные переменные. Выразим, например, x₁, x₂ и x₃ через x₄ и x₅, т.е. приведем систему к единичному базису:

Целевую функцию Z (X) =-x₄ + x₅ выразим через свободные переменные x₄ и x₅ (в данном примере функция уже выражена через них). Теперь при x₄=0, x₅=0 найдем значения базисных переменных: x₁ =1, x₂ =2, x₃ =3, x₄ =0, x₅ =0, или (1, 2, 3, 0, 0). При найденном допустимом решении целевая функция Z (X) имеет значение 0, т.е. Z₁ =0.

Теперь попытаемся увеличить значение Z₁; увеличение x₄ уменьшит Z₁, т.к. перед x₄ стоит отрицательный коэффициент, а увеличение x₅ дает увеличение и Z₁. Увеличим поэтому x₅ так, чтобы x₁ , x₂ , x₃ не стали отрицательными, оставив x₄ =0. Из второго уравнения системы (15) следует, что x₅ можно увеличить до 2. Таким образом, получаем следующие значения переменных: x₁ =5, x₂ =0, x₃ =1, x₄ =0, x₅ =2 или (5, 0, 1, 0, 2).

Значение целевой функции Z (X) при этом допустимом решении равно Z₂ =2, т.е. при втором шаге оно увеличилось.

Далее, примем за свободные переменные х₂ и х₄, т.е. именно те, которые в новом решении имеют нулевые значения. С этой целью из второго уравнения системы (15) выразим х₅ через х₂ и х₄ и получим х₅ =2 – х₂ + 2х₄. Тогда

Переменные х₁, х₃ и х₅ образуют новый базис. Для увеличения значения Z(X) будем увеличивать х₄. Из второго уравнения системы (16) видно, что при условии неотрицательности х₃ значение х₄ можно довести до х₄ =1/5. При этом условии новое допустимое решение есть х₁ =28  5, х₂=0, х₃=0, х₄ =1  5, х₅ =12  5 или (28  5, 0, 0, 1  5, 12  5). Значение целевой функции при этом Z₃ =11  5.

Выразим теперь х₁, х₄, х₅ через свободные переменные х₂ и х₃:

Переменные х₁, х₄ и х₅ образуют новый базис. Т.к. в последней целевой функции обе свободные переменные входят с отрицательными коэффициентами, то наибольшее значение Z (X) достигает при х₂ =0, х₃ =0. Это означает, что решение (28  5,0,0,1  5,12  5) является оптимальным и Z_max =11/5.

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

Данным методом решаются задачи о назначениях, которые являются частным случаем транспортных задач. Метод состоит из следующих шагов:

1) Преобразование строк и столбцов матрицы. Цель данного шага – получение максимально возможного числа нулевых элементов в исходной матрице. Для этого из всех элементов каждой строки вычитаем минимальный элемент соответствующей строки, а из всех элементов каждого столбца вычитаем минимальный элемент соответствующего столбца.

2) Определение назначения. Если после выполнения первого шага в каждой строке и каждом столбце матрицы можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.

3) Модификация преобразованной матрицы. Если допустимое решение, состоящее из нулей, не найдено, то проводим минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Выбираем наименьший невычеркнутый элемент. Этот элемент вычитаем из каждого невычеркнутого элемента и прибавляем к каждому элементу, стоящему на пересечении проведенных прямых.

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

Примечания. 1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на какой-либо объект, то соответствующая стоимость полагается равной достаточно большому числу М.

3. Если исходная задача является задачей максимизации, то все элементы исходной матрицы следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем задачу следует решать как задачу минимизации.

4. Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости.

Пример. Распределить ресурсы по объектам, если задана матрица

.

Решение: 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5 и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим

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

3-й шаг. Вычеркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2:

.

Вычитаем его из всех невычеркнутых элементов и, складывая его со всеми элементами, расположенными на пересечении двух линий, получим

. Итак, .

Ответ: Первый ресурс направляем на 3-й объект, второй – на 2-й объект, четвертый – на 1-й объект, третий – на 4-й объект. Стоимость назначения: 9+4+11+4=28.

4. ОФОРМЛЕНИЕ КУРСОВОЙ РАБОТЫ

Работа должна быть написана на одной стороне листа белой бумаги формата А4 через полтора интервала. Цвет шрифта должен быть черным, высота букв, цифр и других знаков – не менее 12. Текст следует печатать, соблюдая следующие размеры полей: правое – 10 мм, верхнее – 20 мм, левое и нижнее – 20 мм. Разрешается использовать компьютерные возможности акцентирования внимания на определенных терминах, формулах, применяя шрифты разной гарнитуры.

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

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

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

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

Внутри пунктов могут быть приведены перечисления. Перед каждым перечислением следует ставить дефис или, при необходимости, ссылки в тексте документа на одно из перечислений, строчную букву (за исключением е, з, й, о, ч, ь, ы, ъ), после которой ставится скобка. Для дальнейшей детализации перечислений необходимо использовать арабские цифры, после которых ставится скобка, а запись производится с абзацного отступа.

Иллюстрации (чертежи, графики, схемы, диаграммы, фотоснимки) следует располагать непосредственно после текста, в котором они упоминаются впервые, или на следующей странице. Иллюстрации могут быть в цветном исполнении. На все иллюстрации должны быть даны ссылки в тексте.

Чертежи, графики, диаграммы, схемы, иллюстрации должны соответствовать требованиям государственных стандартов Единой системы конструкторской документации (ЕСКД).

Если рисунок один, то он обозначается «Рисунок 1». Слово «рисунок» и его наименование располагают посредине строки. Допускается нумеровать иллюстрации в пределах раздела. В этом случае номер иллюстрации состоит из номера раздела и порядкового номера иллюстрации, разделенных точкой. Например, Рисунок 1.1

Иллюстрации, при необходимости, могут иметь наименование и пояснительные данные (подрисуночный текст). Слово «Рисунок» и наименование помещают после пояснительных данных и располагают следующим образом: Рисунок 1 – Кривая спроса.

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

Таблицу следует располагать непосредственно после текста, в котором она упоминается впервые, или на следующей странице. На все таблицы должны быть ссылки. При ссылке следует писать слово «таблица» с указанием ее номера.

Таблицу с большим количеством строк допускается переносить на другой лист (страницу). При переносе части таблицы на другой лист слово «Таблица» и номер ее указывают один раз слева над первой частью таблицы, над другими частями пишут слово «Продолжение» и указывают номер таблицы, например: «Продолжение таблицы 1». При переносе части таблицы нижнюю горизонтальную черту, ограничивающую таблицу, не проводят.

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

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

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

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

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

Формулы следует нумеровать порядковой нумерацией в пределах всей работы арабскими цифрами в круглых скобках в крайнем правом положении на строке. Ссылки в тексте на порядковые номера формул дают в скобках. Например, - …в формуле (1). Допускается нумерация формул в пределах раздела. В этом случае номер формулы состоит из номера раздела и порядкового номера формулы, разделенных точкой, например (3.1).

Ссылки на использованные источники литературы следует приводить в квадратных скобках, например [8].

Приложения оформляют как продолжение курсовой работы. В тексте на все приложения должны быть даны ссылки. Приложения располагают в порядке ссылок на них в тексте документа. Каждое приложение следует начинать с новой страницы с указанием наверху посередине страницы слова «Приложение», его обозначения. Приложение должно иметь заголовок, который записывают симметрично относительно текста с прописной буквы отдельной строкой. Приложения обозначают заглавными буквами русского алфавита, начиная с А, за исключением букв Е, З, Й, О, Ч, Ь, Ы, Ъ. После слова «Приложение» следует буква, обозначающая его последовательность. Приложения должны иметь общую с остальной частью документа сквозную нумерацию страниц.

СПИСОК ЛИТЕРАТУРЫ

1. Афанасьев М.Ю., Суворов Б.В. Исследование операций в экономике. – М. Инфра-М, 2008.

2. Бирман Л.А. Управленческие решения. – М.: Дело, 2008.

3. Емельянов А.А., Власова Е.А., Дула Р.В. Имитационное моделирование экономических процессов. – М.: Финансы и статистика, 2009.

4. Дик В.В. Методология формирования решений в экономических системах и инструментальные среды их поддержки. - М: Финансы и статистика, 2006.

5. Джекел П. Применение методов Монте-Карло в финансах. – М: Интернет-Трейдинг, 2010.

6. Пужаев А.В. Управленческие решения – М.: КНОРУС, 2012.

7. Коротков Э.М. Менеджмент – М.: Юрайт, 2011.

8. Трофимова Л.А Методы принятия управленческих решений – М.: Юрайт, 2013.

9. Трояновский В.М. Разработка управленческого решения. - М.: Изд-во РДЛ, 2009.

10. Сербиновский Б.Ю. Управление персоналом – М.: Дашков и К, 2008.

11. Фатхутдинов Р.А. Разработка управленческого решения. – М.: Инфра-М, 2007.

ПРИЛОЖЕНИЕ А

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Рязанский институт (филиал)

федерального государственного бюджетного образовательного учреждения высшего профессионального образования

Московский государственный университет машиностроения (МАМИ)

Кафедра Экономики, менеджмента и маркетинга

КУРСОВАЯ РАБОТА

на тему: «…………………………………………………………………………»

по дисциплине: «Методы принятия управленческих решений»

Работу выполнил студент ______________________ ____факультета____курса специальности_________ шифр_________________ Руководитель__________

Рязань 20__

ПРИЛОЖЕНИЕ Б

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Рязанский институт (филиал)

федерального государственного бюджетного образовательного учреждения высшего профессионального образования

Московский государственный университет машиностроения (МАМИ)

Кафедра экономики, менеджмента и маркетинга

ЗАДАНИЕ

на курсовую работу по дисциплине «Методы принятия управленческих решений»

студенту____курса группы_____ шифр________

____________________________________________________________________

Предмет исследования: ________________________________________________

____________________________________________________________________

Исходные данные: тема №____, задание для практической части по варианту_____________

Содержание курсовой работы

Введение

Теоретическая часть

Практическая часть

Заключение

Список используемой литературы

Дата выдачи задания «__»___________20___г

Дата сдачи курсовой работы «__»___________20___г

Задание получил ____________________

Руководитель курсовой работы ____________________

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Рязанский институт (филиал)

федерального государственного бюджетного образовательного учреждения высшего профессионального образования

Московский государственный университет машиностроения (МАМИ)

Учебное издание

МЕТОДЫ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ

ИГНАТЬЕВ Андрей Игоревич, АСАЕВА Татьяна Александровна, СОЛОВЬЕВА Ирина Павловна

Методические указания и задания по выполнению курсовой работы для студентов очной и заочной формы обучения направление подготовки 080200 «Менеджмент», профиль подготовки - «Производственный менеджмент в строительстве», квалификация – бакалавр

Рецензент к.э.н., доцент Е. Я. Жевнина

Подписано в печать ______.Формат 60х84\1 16. Бумага типографская. Тираж ___экз.

________________________________________________________________________________

Рязанский институт (филиал) университета машиностроения

390000, г.Рязань, ул. Право-Лыбедская, 26/ 53

36