- •Экономико-математические методы
- •1 Общая задача математического
- •1.1 Модель математического программирования
- •1.2 Математическая формулировка задач линейного
- •1.3 Примеры построения простейших моделей математического
- •1.4 Геометрическая интерпретация задач линейного
- •1.4.1 Графический метод решения
- •1.4.2 Схема решения задачи графическим методом
- •1.4.3 Особые случаи решения задач линейного
- •1.5 Контрольные вопросы к разделу 1
- •2 Симплекс-метод решения задач линейного
- •2.1 Симметричный симплекс-метод
- •2.2 Экономический анализ оптимального плана по последней
- •2.3 Симплекс-метод с искусственным базисом
- •2.4. Схема решения задач линейного программирования
- •2.5. Особые случаи при решении задач симплекс-методом
- •2.6 Контрольные вопросы к разделу 2
- •3 Двойственные задачи линейного
- •3.1 Понятие о двойственных задачах
- •3.2 Теоремы двойственности в линейном программировании
- •3.3 Экономическая интерпретация двойственных задач
- •3.4. Примеры построения двойственных задач
- •3.5 Контрольные вопросы к разделу 3
- •4 Транспортная задача линейного
- •4.1 Математическая постановка транспортной задачи
- •4.2 Метод потенциалов решения транспортной задачи
- •Числаui являются потенциалами строк, аvj – потенциалами столбцов. Из теоремы следует, что для того, чтобы план был оптимальным, необходимо выполнение следующих условий:
- •Если хотя бы одна незанятая клетка не удовлетворяет условию (б), то план не оптимален.
- •4.3 Схема решения транспортной задачи
- •4.4 Контрольные вопросы к разделу 4
- •5 Методы решения задач нелинейного
- •5.1 Классификация задач математического программирования
- •5.2 Метод Лагранжа
- •5.3 Метод динамического программирования
- •5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования
- •5.5 Контрольные вопросы к разделу 5
- •6 Наиболее распространенные модели
- •Содержание
- •Литература
- •Экономико-математические методы Учебное пособие
1.4 Геометрическая интерпретация задач линейного
программирования, графический метод решения
1.4.1 Графический метод решения
В отдельных случаях задачи линейного программирования удается решить с помощью наиболее простого и наглядного геометрического метода. Геометрический метод позволяет наглядно описать область допустимых решений, целевую функцию и процесс получения оптимального решения путем последовательного приближения к оптимальной точке.
Система линейных ограничений задачи (1.5) задает в пространстве многогранное множество – областьдопустимых решений. Экстремум целевой функции (1.4) достигается на его границе, чаще всего в одной из вершин многогранника.
Если задача зависит от двух переменных x1иx2, то ее можно решить графически. Рассмотрим пример.
Задача 1.4. Найти оптимальный план математической модели:
Z = 2∙x1+x2+4 → max
x1 + x2 4
8∙x1 - 4∙x2-16
x1 ≤ 2
x1, x2 0.
РЕШЕНИЕ.
1 П о с т р о е н и е о б л а с т и д о п у с т и м ы х р е ш е н и й.
Последовательно определим области точек, удовлетворяющих каждому ограничению в отдельности. Границами этих областей будут прямые, уравнения которых получаются из ограничений.
Границей допустимой области первого ограничения является прямая
x1 + x2 = 4; (1)
границей второго ограничения – прямая
8∙x1 - 4∙x2 = -16; (2)
третьего – прямая
x1 = 2. (3)
Построим эти прямые на чертеже (рисунок 1.1). Для каждого ограничения стрелкой отметим: в какой стороне от граничной прямой располагается допустимая область.
Рисунок 1.1 – Нахождение оптимального плана графическим методом
Например, рассмотрим первое ограничение задачи. Границей его допустимой области является прямая (1). Очевидно, в точках этой прямой выполняется равенствоx1 +x2= 4. Чтобы узнать, где расположены точки, удовлетворяющиеx1 +x2> 4, подставим в это неравенство координаты любой точки на плоскости, например (0,0). Получим 0+0 > 4 – это неверно, следовательно, все точки, лежащие ниже прямой (1) также не удовлетворяют первому ограничению. Тогда область точек,удовлетворяющихограничению, будет лежать выше прямой: на что и указывает стрелка.
Пересечением допустимых областей всех ограничений является
Δ АВС,он представляет собой множество допустимых решений задачи.
2 П о с т р о е н и е л и н и и у р о в н я ц е л е в о й ф у н к ц и и
и определение направления ее наискорейшего возрастания
Линия уровня функции определяется уравнением
,
т.е. это область точек, в которых функция принимает одно и тоже значение, равное некоторой заданной константе.
Если функция зависит только от двух переменных и является линейной, ее линия уровня представляет собой прямую на плоскости координат.
Построим линию уровня целевой функции. Константу задаем произвольно, но так, чтобы прямую можно было легко расположить на нашем рисунке 1.1. Если взять= 4, то уравнение линии уровня будет иметь вид:
2∙x1+x2= 0.
Очевидно, эта прямая проходит через начало координат; на рисунке она обозначена Z=4. Нашей задачей является определение такой линии уровня целевой функции, чтобы она соответствовала наибольшему из возможных ее значений в пределах нахождения в допустимой области (ΔАВС).
Линии уровня линейной функции параллельны.
Так как экстремум целевой функции достигается на границе многоугольника допустимых решений, оптимальную точку определяем параллельным перемещением прямой в направлении возрастания (при поиске максимума) или убывания (в задачах минимизации) вплоть до крайней точки допустимой области.
Направление наискорейшего возрастания функции определяет ее градиент: вектор с координатами (с1, с2), перпендикулярный линии уровня. На рисунке 1.1 показан градиентцелевой функцииZ= 2∙x1+x2+4, с координатами (2, 1).
3 О п р е д е л е н и е о п т и м а л ь н о г о п л а н а
Перемещаем линию уровня Z=4параллельно в направлении градиента. По ходу движения целевая функции возрастает. Очевидно, для того, чтобы выполнялись ограничения задачи, перемещаемая прямая должна иметь хотя бы одну общую точку с допустимой областью (ΔАВС). Таким образом, оптимальной точкой является вершина В. Через эту точку проходит линия уровняZ=ZМАХ, в точках которой целевая функция принимает значениеZМАХ. Координаты вершиныВ являются решением системы уравнений, составленной из уравнений пересекающихся прямых (2) и (3):
.
Оптимальный план:
, ,
ZМАХ= 2∙x1+x2+4 =2∙2+8+4 = 16.