Ю. Ю. Горюнов, Т. Ю. Горюнова, Д. В. Дружинин Теория и методы принятия решений Учебное пособие пенза 2010
Скачать 0.54 Mb.
|
| ^ Если система ограничений и целевая функция задачи линейного программирования содержат две переменные, то эту задачу можно решить геометрически. Геометрическое решение задачи линейного программирования состоит в следующих действиях:
Пример. Решить задачу линейного программирования: 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. Если требуется найти максимум целевой функции f, то найти минимум целевой функции –f. 2. Найти любое опорное решение задачи линейного программирования. 3. Если опорное решение существует, то найти оптимальное (min) опорное решение; 4. Если требовалось найти максимум целевой функции, то умножить на -1 найденный минимум. ^ 1. Преобразовать систему ограничений к стандартному виду:  (1)Примечание. Переменные слева от равенств называются базисными, а в круглых скобках – свободные. 2. Если в системе (1) все i 0, то приравнять к нулю все свободные переменные и этим получить опорное решение. 3. Если в системе (1) найдётся i < 0, то найти и поменять местами свободную переменную xk и базисную переменную xn (то есть свободную переменную xk ввести в состав базисных, а базисную переменную xn – в состав свободных). 4. Если обмен произвести удалось, то продолжить с п. 2, иначе опорного решения не существует. Пример. Найти опорное решение следующей задачи линейного программирования  (2)Решение. 1. Приводим систему ограничений к стандартному виду: а) получаем систему линейных уравнений по правилу: если в системе ограничений есть неравенства, то в левые части неравенств со знаком "" следует добавить новые переменные , а из левых части неравенств "" – вычесть новые переменные: в системе ограничений (2) есть неравенства и все со знаком "", поэтому, добавляем к левым частям неравенств новые переменные:  (3)б) Приводим систему линейных уравнений (3) к ступенчатому виду:
 ;
 ;
 .в) Приводим систему линейных уравнений к приведённому ступенчатому виду:
 ;
 или  или 
 (4)Базисные переменные: x1, x2 и x3, свободные переменные: x4, y1, y2 и y3. 2. В системе (4) есть не отрицательные свободные члены, поэтому ищем для обмена свободную и базисную переменные:
в системе (4) берём первое уравнение;
в первом уравнении два отрицательных коэффициента при x4 и y3;
возьмём переменную x4 и выделим столбец с x4;
в столбце с x4 два коэффициента в первой и второй строках, знаки которых совпадают со знаками свободных членов, находим минимальное отношение: 
минимальное отношение находится в первой строке, поэтому берём базисную переменную x1:
(выделенные столбец и строка)
в нашем случае меняем местами переменные x4 и x1: в первой строке выражаем x4 через оставшиеся переменные:  подставляем выражение для x4 во второе и третье уравнения:  и получаем новый стандартный вид системы:  (5)В этой системе все свободные члены не отрицательные, поэтому, приравнивая к нулю все свободные переменные, получим опорное решение:  ^ Если опорное решение найдено, то для отыскания оптимального опорного решения (минимального) необходимо:
из (5) получаем  (6)
в нашем случае есть положительный коэффициент;
в целевой функции (6) положительный коэффициент только у свободной переменной y3, поэтому в системе (6) выделяем столбец с y3:
то целевая функция минимума не имеет, в выделенном столбце есть положительные коэффициенты;
в выделенном столбце только один положительный коэффициент, поэтому выделяем ту строку, в которой он находится, то есть первую строку:
свободную переменную y3 вводим в состав базисных, а базисную x4 – в состав свободных (выразить переменную y3 через все оставшиеся переменные в выделенной строке): 
В целевой функции все коэффициенты являются отрицательными, поэтому  и достигается при (приравниваем к нулю свободные переменные)  Ответ. Минимум целевой функции равен -10 и достигается при  |
в виде 
где все переменные x1, x2, … являются свободными,
являются не положительными, то 
Похожие:
 | Список вопросов к экзамену по дисциплине Системы принятия решений для групп ук-41, стс-41 Основные понятия теории принятия решений(теория принятия решений, сппр, манипулирование, альтернатива, критерии) | | Методы прогнозирования и принятия решений Учебное пособие предназначено для студентов вузов, аспирантов, а также специалистов по прикладной экономике и прогнозированию |
 | Вопросы к экзамену по дисциплине «методы принятия управленческих решений» Поведение человека в процессе принятия решений. Феномены поведения человека в процессе принятия решений | | 1. Предмет и задачи курса «Теория принятия решений» В простейших случаях трудностей может и не быть, но в таких алгоритмически сложных областях, как принятие решений, управление, системное... |
| Учебное пособие Челябинск д анилова Ирина Валентиновна, Моцаренко... Данилова Ирина Валентиновна, Моцаренко Наталья Васильевна. Общая экономическая теория: Учебное пособие. – Челябинск: Издательство... | | Вычислительная математика Учебное пособие Мастяева И. Н., Семенихина О. Н. Численные методы: Учебное пособие / Московский международный институт эконометрики, информатики,... |
| Учебное пособие Челябинск Законодательство России обязывает каждое предприятие вести бухгалтерский учет. Но для принятия управленческих решений существует... | | Задачи теории игр в экономике, финансах и бизнесе. Теория игр Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях |
| Задачи теории игр в экономике, финансах и бизнесе. Теория игр Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях | | Задачи теории игр в экономике, финансах и бизнесе. Теория игр Теория игр – раздел современной математики, изучающий математические модели принятия решений в т н конфликтных ситуациях |