Математическое программирование

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

,

 

Решение 

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

        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      или

 

      Границы области допустимых решений

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

 
 

      Рассмотрим  целевую функцию задачи F = 4x₁+7x₂ → max.  
Построим прямую, отвечающую значению функции F = 0: F = 4x₁+7x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Равный масштаб

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

      Прямая  F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых: 
2x₁+7x₂≤21 
7x₁+2x₂≤49 
Решив систему уравнений, получим: x₁ = , x₂ = . 
Откуда найдем максимальное значение целевой функции:

      

 

       2. Предприятие   выпускает продукцию  двух видов:  и . Используются три вида ресурсов: оборудование, сырье и электроэнергия. Нормы расхода, лимиты ресурсов и прибыль от единицы продукции представлены в таблице:

      Найти оптимальный план выпуска продукции. 

     Решение

     Составим  математическую модель задачи. Пусть  соответственно – количество единиц продукции и , которую производит предприятие. По смыслу задачи эти переменные неотрицательны. Тогда совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать. Подсчитаем ресурсов:

1. оборудование: , по условию затраты не превосходят 30,
2. сырье: , по условию затраты не превосходят 20,
3. электроэнергия: , по условию затраты не превосходят 18.

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

     

     

     

     Решим задачу симплекс - методом.

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

      ·  Свободные члены системы ограничений должны быть неотрицательными.

      Свободные члены системы ограничений неотрицательные.

      ·  Система ограничений должна быть приведена к каноническому виду.

      К левой части неравенства 1 системы  ограничений прибавляем неотрицательную  переменную x₃ - преобразуем неравенство 1 в равенство.

      К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x₄ - преобразуем неравенство 2 в равенство.

      К левой части неравенства 3 системы  ограничений прибавляем неотрицательную  переменную x₅ - преобразуем неравенство 3 в равенство. 
 
 
 

 

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

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

      Наличие единичного базиса в системе ограничений  позволяет легко найти начальное  опорное решение. Рассмотрим подробнее:

      Переменная x₃ входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₃ - базисная переменная.

      Переменная x₄ входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₄ - базисная переменная.

      Переменная x₅ входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₅ - базисная переменная.

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

      X _нач = ( 0 , 0 , 30 , 20 , 18 )

      ·  Функция F не должна содержать базисных переменных.

      Вернемся  к рассмотрению функции F.

      Функция F не содержат базисных переменных.

      Значение  функции F для начального решения: F (X _нач) = 0

      Для составления начальной симплекс таблицы мы выполнили все условия.

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

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

      Шаг 1

      За  ведущий выберем столбец 1 , так  как -30 наименьший элемент в F строке. Элемент F строки, принадлежащий столбцу свободных членов не рассматриваем.

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

      Разделим  элементы строки 3 на 2.