Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
nbsp;
Рассмотрим задачу о размещении заказа. Имеется m однородных групп оборудования, на котором нужно выполнить заказ на выпуск n видов продукции в объемах х*j, . Мощность оборудования ограничена, например, временем Тi. Производительность оборудования задана коэффициентами аij. Известны коэффициенты затрат Сij - затраты i - го оборудования на производство j - го продукта. Построить план хij размещения заказа (загрузки оборудования). Составим математическую модель задачи.
F(x) = > min , xij ? 0, j= , ,
по мощности - , ,
по видам продукции, план по которой может быть перевыполнен
, j= ,
по видам продукции, план по которой должен соответствовать заказу
, j= ,
по видам продукции, заказ на которую принимается для более полной загрузки
оборудования
, j= .
4. Графический метод решения ЗЛП. Основные свойства ЗЛП
Графический метод решения ЗЛП используется, если число неизвестных задачи не больше 2 или если разность между числом неизвестных и ограничений задачи, записанных в виде уравнений не более двух.
Схема решения.
- Строим область допустимых решений.
- Строим линию уровня.
- Определяем направление градиента.
- Определяем точку максимума (минимума):
Точка максимума - точка допустимой области, наиболее удаленная от линии уровня в направлении градиента, точка минимума - точка допустимой области, наиболее удаленная от линии уровня в направлении антиградиента.
При решении ЗЛП возможны следующие случаи:
Основные свойства ЗЛП (см. рис.).
- ЗЛП является выпуклой задачей, поэтому решение всегда единственно.
- Оптимальное решение достигается по крайней мере в одной из вершин допустимой области: а) только в одной вершине; б) в двух вершинах и имеет бесконечное множество планов.
- Если допустимая область не ограничена, то ЗЛП может быть разрешима или не разрешима, что зависит от целевой функции: в) задача на max не разрешима, а на min - разрешима; г) ЗЛП не разрешима.
- Если допустимая область состоит из единственной точки, то в ней достигается и максимум и минимум - д).
- Если допустимая область пуста, то ЗЛП не разрешима - е).
- Если допустимая область ограничена и не пуста, то ЗЛП всегда имеет решение.
Лекция 3
Симплекс-метод решения ЗЛП
Вопросы:
1. Стандартная форма ЗЛП, правила построения.
. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР), метод искусственного базиса.
. Симплекс-метод.
1. Стандартная форма ЗЛП, правила построения
Графический метод решения ЗЛП можно использовать, если число неизвестных равно 2 или разность между числом неизвестных и числом ограничений, записанных в виде уравнений, равна 2. В общем случае эти требования не всегда выполняются. Чтобы использовать для решения некий универсальный метод решения, ЗЛП необходимо записать в определенной, стандартной форме.
Стандартная форма ЗЛП представляет собой такой вид задачи, в котором:
) все переменные неотрицательны;
) все ограничения заданы в виде уравнений;
) целевая функция сформулирована на минимум.
Требования эти оправданы. Во-первых, поиск максимума линейной функции сводится к поиску минимума функции с противоположными по знаку коэффициентами: оптимальные точки совпадают, а значения целевых функций равны по абсолютному значению. Во-вторых, линейная функция не имеет экстремумов и достигает своего наибольшего или наименьшего значения на границе допустимой области, поэтому и решать необходимо не неравенства, а уравнения. Запишем правила приведения любой ЗЛП к стандартному виду.
Правила построения стандартной формы ЗЛП:
1) Если F(x) = C1x1 + C2x2 + … + Cnxn max, то можно искать
F(x) = - C1x1 - C2x2 - … - Cnxn min.
) Ограничения в виде неравенств ( ) могут быть сведены к уравнениям введением дополнительных, уравновешивающих неотрицательных уравнений.
Например: 2х1 + 3х2 4 2х1 + 3х2 + х3 = 4, х3 - уравновешивающая переменная.
x1 + 2x2 5 4x1 + 2x2 - x4 = 5, x4 - уравновешивающая переменная.
) Если некоторая переменная х может быть не ограничена знаком, то в стандартном виде такую переменную можно представить в виде разности двух неотрицательных переменных: x = x' - x'', x' , x'' .
При этом дополнительные переменные не входят в целевую функцию. Стандартная форма ЗЛП в матричном виде выглядит так: Ax = b, x , F(x) = CTx min.
2. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР), метод искусственного базиса
Чтобы ЗЛП имела решение необходимо, чтобы система ограничений была совместна. Это возможно, если ранг m системы (число линейно независимых уравнений) был не больше числа неизвестных n. Случай m > n невозможен. При m = n система имеет единственное решение, которое определяется методами обычной алгебры. Если m < n, то система имеет m линейно независимых векторов - базис, через которые любой вектор системы может быть выражен как линейная комбинация. Таких базисов может быть несколько, но не больше, чем Сnm. Переменные ЗЛП, соответствующие m векторам базиса, являются базисными, остальные переменные - свободные.
Базисом называют любой набор m переменных такой, что определитель, составленный из коэффициентов при этих переменных, отличен от нуля. Соответствующее решение называю базисным решением.
Переменные, входящие в базис, называют базисными (б.п.), остальные n - m переменных называют свободными.
Чтобы пол