Реферат: Математические методы в экономике 3
(1.2)
(1.3)
Функция (1.1) называется целевой функцией. Система (1.2) называется системой ограничений, а условие (1.3) – условием неотрицательности.
§1. «Геометрическая интерпретация ЗЛП. Графический метод решения ЗЛП»
Графический метод решения ЗЛП основан на следующих утверждениях.
Система ограничений ЗЛП геометрически представляет собой выпуклый многоугольник или выпуклую многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы.
Целевая функция Z = c1 x1 + c2 x2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору нормали N(с1 ,с2 ). Эти прямые называются линиями уровня.
Линия уровня – это прямая, вдоль которой целевая функция принимает фиксированное значение.
Теорема. При перемещении линии уровня в направлении вектора нормали N значение целевой функции возрастает, в противоположном направлении - убывает.
Алгоритм графического метода решения ЗЛП.
1. В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;
2. найти полуплоскость решения каждого неравенства системы (обозначить стрелками). Для определения полуплоскости необходимо выбрать любую контрольную точку, не лежащую на данной прямой. Подставить ее координаты в систему ограничений. Если неравенство выполняется, то нужно выбрать полуплоскость, содержащую контрольную точку. Если неравенство не выполняется нужно выбрать полуплоскость, не содержащую контрольную точку. В качестве контрольной точки рекомендуется выбирать точку с координатами (0;0);
3. найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;
4. построить вектор нормали N. Начало вектора нормали в точке с координатами (0;0), конец вектора в точке с координатами (с1 , с2 );
5. через начало координат построить линию уровня, перпендикулярно к вектору нормали;
6. перемещать линию уровня параллельно самой себе по области решения в угловые точки, достигая max f при движении вектора N (min f при движении в противоположном направлении);
7. найти координаты точки max (min). Для этого необходимо решить систему уравнений прямых, которые пересекаются в этой точке или определить координаты по графику;
8. вычислить значение целевой функции в этой точке (ответ).
§2. «Симплексный метод решения ЗЛП»
Симплексный метод представляет собой схему получения оптимального плана за конечное число шагов.
Для использования симплексного метода ЗЛП должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
Оптимизационные исследования ЗЛП удобно проводить, пользуясь симплекс-таблицами. Существует достаточно большое количество форм симплекс-таблиц. Воспользуемся одной из форм, по которой рекомендуется следующий порядок решения ЗЛП:
1 . Математическая модель задачи приводится к канонической форме с помощью дополнительных неотрицательных переменных.
2. Определяется начальное базисное допустимое решение. Для этого переменные разбивают на две группы – основные (базисные) и неосновные. В качестве основных переменных следует выбрать (если возможно) переменные, каждая из которых входит только в одно из уравнений системы ограничений. Дополнительные переменные удовлетворяют этому правилу.
3. Составляется исходная симплекс-таблица (таблица 1), в которую записывают параметры, соответствующие начальному базисному допустимому решению:
3.1. Весовые коэффициенты cj при переменных xj (j = 1,...,n) целевой функции (строка C ).
3.2. Весовые коэффициенты ci при базисных переменных xi (i = 1,...,m) целевой функции (столбец C b ).
3.3. Переменные xi (i = 1, ... ,m) , которые входят в текущий базис (столбец Ab ).
3.4. Свободные коэффициенты bi (i =1, ... ,m) уравнений ограничений (столбец B). В этом же столбце находим оптимальный план задачи.
3.5. Элементы a ij (i = 1, ... ,m ; j = 1, ... ,n) матрицы условий задачи (столбцы A1 , .., An ).
Таблица 1
|
К-во Просмотров: 346
Бесплатно скачать Реферат: Математические методы в экономике 3
|