Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010


НазваниеЮ. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010
страница4/12
Дата публикации16.03.2013
Размер0.54 Mb.
ТипУчебное пособие
userdocs.ru > Математика > Учебное пособие
1   2   3   4   5   6   7   8   9   ...   12
^

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


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

Геометрическое решение задачи линейного программирования состоит в следующих действиях:

  1. заменить в каждом ограничении знак неравенства на знак равно;

  2. в прямоугольной системе построить соответствующие прямые,

  3. выделить область точек на плоскости, координаты которых удовлетворяют системе ограничений (ограничению со знаком "" удовлетворяют точки, находящиеся выше прямой, а знаку "" – ниже прямой);

  4. в целевой функции отбросить свободный член и построить соответствующую прямую;

  5. при поиске максимума последнюю прямую параллельно перемещаем вверх, а минимума – вниз;

  6. координаты точки области, которую прямая пересечёт последней, будут давать максимум (минимум) целевой функции, если эта точка существует.

Пример. Решить задачу линейного программирования:

f = x1 + 2x2 + 3  max



Решение.

1. Заменим в ограничениях знаки "" на знак равно, получим уравнения двух прямых:



Построим эти прямые в прямоугольной системе координат:



2. Выделим область точек на плоскости, координаты которых удовлетворяют системе ограничений (на рисунке эта область 0ABC закрашена):

первому ограничению удовлетворяют точки на плоскости, которые лежат ниже прямой L1, второму ограничению – ниже прямой L2, третьему – точки, находящиеся правее оси Ox2, четвёртому – выше оси Ox1

3. Отбросим свободный член в целевой функции, получим функцию y = x1 + 2x2, построим график этой функции (прямую L3).

4. Перемещая прямую L3 параллельно вверх, находим, что последней точкой области 0ABC, которую она пересечёт, будет точка B.

5. Для нахождения координат точки В решаем систему уравнений:

решение системы: x1 = 3, x2 = 4.

Вывод: максимальное значение целевой функции f равно 3 + 2*4 + 3 = 14 и достигается при x1 = 3, x2 =4.

Примечание.

Упражнения. Решить геометрически задачу линейного программирования, результат проверить в Microsoft Excel.

1. 2.

3. 4.
^

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


Решение задач линейного программирования симплекс-методом осуществляется по следующему алгоритму.

1. Если требуется найти максимум целевой функции f,

то найти минимум целевой функции –f.

2. Найти любое опорное решение задачи линейного программирования.

3. Если опорное решение существует,

то

найти оптимальное (min) опорное решение;

4. Если требовалось найти максимум целевой функции,

то

умножить на -1 найденный минимум.
^

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


1. Преобразовать систему ограничений к стандартному виду:

(1)

Примечание. Переменные слева от равенств называются базисными, а в круглых скобках – свободные.

2. Если в системе (1) всеi  0,

то

приравнять к нулю все свободные переменные и этим получить опорное решение.

3. Если в системе (1) найдётся i < 0,

то

найти и поменять местами свободную переменную xk и базисную переменную xn (то есть свободную переменную xk ввести в состав базисных, а базисную переменную xn – в состав свободных).

4. Если обмен произвести удалось,

то

продолжить с п. 2,

иначе

опорного решения не существует.

Пример. Найти опорное решение следующей задачи линейного программирования

(2)

Решение.

1. Приводим систему ограничений к стандартному виду:

а) получаем систему линейных уравнений по правилу:

если в системе ограничений есть неравенства, то в левые части неравенств со знаком "" следует добавить новые переменные , а из левых части неравенств "" – вычесть новые переменные:

в системе ограничений (2) есть неравенства и все со знаком "", поэтому, добавляем к левым частям неравенств новые переменные:

(3)

б) Приводим систему линейных уравнений (3) к ступенчатому виду:

  • записываем расширенную матрицу системы из коэффициентов при неизвестных и свободных членов:

;

  • умножаем вторую строку на -1 и меняем местами первую и вторые строки:

;

  • умножаем первую строку на 5 и складываем со второй, умножаем первую строку на 3 и складываем с третьей и получаем ступенчатый вид матрицы:

.

в) Приводим систему линейных уравнений к приведённому ступенчатому виду:

  • первую строку умножаем на -1, третью строку делим на -3:

;

  • умножаем третью строку на -3 и складываем со второй, складываем третью и первую строки и получаем приведённый ступенчатый вид матрицы:

или

или



  • приводим систему к стандартному виду:

(4)

Базисные переменные: x1, x2 и x3, свободные переменные: x4, y1, y2 и y3.

2. В системе (4) есть не отрицательные свободные члены, поэтому ищем для обмена свободную и базисную переменные:

  • взять любое уравнение с отрицательным свободным членом,

в системе (4) берём первое уравнение;

  • если во взятом уравнении нет отрицательных коэффициентов при свободных переменных, то опорного решения не существует,

в первом уравнении два отрицательных коэффициента при x4 и y3;

  • взять любую свободную переменную с отрицательным коэффициентом и выделить столбец, содержащий взятую переменную,

возьмём переменную x4 и выделим столбец с x4;







-

(











)





9

-

(









)







-

(










)

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

в столбце с x4 два коэффициента в первой и второй строках, знаки которых совпадают со знаками свободных членов, находим минимальное отношение:



  • взять базисную переменную, которая находится в строке с минимальным отношением,

минимальное отношение находится в первой строке, поэтому берём базисную переменную x1:







-

(











)





9

-

(









)







-

(










)

(выделенные столбец и строка)

  • обменять местами выбранные свободную и базисную переменные, для этого:

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

в нашем случае меняем местами переменные x4 и x1:

в первой строке выражаем x4 через оставшиеся переменные:



подставляем выражение для x4 во второе и третье уравнения:



и получаем новый стандартный вид системы:

(5)

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


^

1.4.2. Поиск оптимального решения


Если опорное решение найдено, то для отыскания оптимального опорного решения (минимального) необходимо:

  1. представить целевую функцию в виде где все переменные x1, x2, … являются свободными,

из (5) получаем

(6)

  1. если все коэффициенты являются не положительными, то

в нашем случае есть положительный коэффициент;

  1. если среди коэффициентов есть положительный, то в последней системе стандартного вида выделить столбец, содержащий свободную переменную с положительным коэффициентом в целевой функции,

в целевой функции (6) положительный коэффициент только у свободной переменной y3, поэтому в системе (6) выделяем столбец с y3:







-

(











)







-

(









)







-

(










)

  1. если в выделенном столбце нет положительных коэффициентов у свободных переменных,

то

целевая функция минимума не имеет,

в выделенном столбце есть положительные коэффициенты;

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

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







-

(











)







-

(









)







-

(










)

  1. свободную переменную в выделенном столбце ввести в состав базисных, а базисную переменную в выделенной строке ввести в состав базисных,

свободную переменную y3 вводим в состав базисных, а базисную x4 – в состав свободных (выразить переменную y3 через все оставшиеся переменные в выделенной строке):



  1. значение новой базисной переменной подставить во все оставшиеся уравнения и целевую функцию:



  1. продолжить с п. 2).

В целевой функции все коэффициенты являются отрицательными, поэтому и достигается при (приравниваем к нулю свободные переменные)

Ответ. Минимум целевой функции равен -10 и достигается при
1   2   3   4   5   6   7   8   9   ...   12

Похожие:

Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconСписок вопросов к экзамену по дисциплине Системы принятия решений для групп ук-41, стс-41
Основные понятия теории принятия решений(теория принятия решений, сппр, манипулирование, альтернатива, критерии)
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconМетоды прогнозирования и принятия решений
Учебное пособие предназначено для студентов вузов, аспирантов, а также специалистов по прикладной экономике и прогнозированию
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconВопросы к экзамену по дисциплине «методы принятия управленческих решений»
Поведение человека в процессе принятия решений. Феномены поведения человека в процессе принятия решений
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 icon1. Предмет и задачи курса «Теория принятия решений»
В простейших случаях трудностей может и не быть, но в таких алгоритмически сложных областях, как принятие решений, управление, системное...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconУчебное пособие Челябинск д анилова Ирина Валентиновна, Моцаренко...
Данилова Ирина Валентиновна, Моцаренко Наталья Васильевна. Общая экономическая теория: Учебное пособие. – Челябинск: Издательство...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconВычислительная математика Учебное пособие
Мастяева И. Н., Семенихина О. Н. Численные методы: Учебное пособие / Московский международный институт эконометрики, информатики,...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconУчебное пособие Челябинск
Законодательство России обязывает каждое предприятие вести бухгалтерский учет. Но для принятия управленческих решений существует...
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconЗадачи теории игр в экономике, финансах и бизнесе. Теория игр
Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconЗадачи теории игр в экономике, финансах и бизнесе. Теория игр
Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях
Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010 iconЗадачи теории игр в экономике, финансах и бизнесе. Теория игр
Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница