- •Лекция 1 Задачи линейного программирования
- •1. Задача оптимального планирования производства
- •2. Графический метод решения задач линейного программирования
- •3. Алгоритм симплекс-метода решения задач линейного программирования
- •4 Решение задач линейного программирования средствами Excel
- •Лекция 2. Элементы теории матричных игр
- •1. Платежная матрица. Нижняя и верхняя цена игры
- •2 Приведение матричной игры к задаче линейного программирования.
- •3 Пример решения матричной игры средствами Excel
- •Лекция 3. Транспортная задача
- •1 Закрытая транспортная задача
- •2. Открытая транспортная задача
- •3 Пример решения транспортной задачи средствами Excel
- •Лекция 4. Сетевое планирование
- •1. Сетевой график и его элементы
- •2. Резервы времени выполнения работ сетевого графика
- •3 Пример построения сетевого графика и расчета резервов времени
- •Лекция 5. Динамическое программирование
- •1. Задача о распределении средств между предприятиями
- •2. Пример решения задача о распределении средств между предприятиями
- •Лекция 6. Ковариационный анализ
- •1. Коэффициенты ковариации и корреляции
- •2. Расчет коэффициентов ковариации и корреляции в табличном процессоре Microsoft Excel
- •3. Понятие о методе ранговой корреляции
- •Тема 7. Парная линейная регрессия
- •1. Линейное уравнение регрессии
- •2. Построение линейного уравнения регрессии в пакете «Stadia»
- •1 Построение множественного линейного уравнения регрессии в Excel
- •2 Пример построения линейной производственной функции
- •Лекция 9. Кластерный анализ
- •9 Иерархические кластер-структуры
- •2. Проведение кластерного анализа в пакете «Stadia»
- •Лекция 10. Дискриминантный анализ
- •1. Основные сведения о дискриминантном анализе
- •2. Проведение дискриминантнрого анализа в пакете «Stadia»
Лекция 1 Задачи линейного программирования
1. Задача оптимального планирования производства
Пусть предприятие из видов ресурсов производитвидов продукции. При этом для производства одной единицыj-го вида продукции расходуетсяединицi-го вида ресурса, т.е.норма расходаi-го ресурса на производствоj-го вида продукции. Матрица, составленная из норм расхода, называется матрицей норм расхода или технологической матрицей.
Обозначим через величину прибыли от реализации одной единицыj-го вида продукции. Эти значения прибыли запишем матрицей-строкой. План производства продукциих1,х2, …,хпобозначим матрицей-столбцомХ. Тогда произведение матрицпредставляет собой величину прибыли, полученной после реализации продукции.
Количество i-го ресурса обозначим. Значенияb1,b2, …,bm запишем матрицей-столбцомB. Тогда матричное неравенствоозначает необходимость, учитывать ограниченность ресурсов при рассмотрении планов производстваХ. Если это неравенство выполняется, то планявляется реальным или допустимым. Естественно, нужно найти такой допустимый план, который бы обеспечил наибольшую прибыль.
Эту задачу можно записать так:
.
Или в матричной форме:
,
,.
Такая задача называется задачей оптимального планирования производства. Функция называется целевой функцией. Множество всех плановХ, удовлетворяющих неравенствам,, называется множеством допустимых планов, и обозначаетсяD. Тогда нашу задачу можно сформулировать так: найти максимум целевой функциина множестведопустимых планов.
Область ограничений задается линейными функциями. Сама целевая функция также является линейной. Задачи такого вида называются задачами линейного программирования. К ним относятся, например, задачи о диете, о раскрое материала и другие.
Задача линейного программирования в общем виде такова: найти максимум или минимум линейной целевой функции при линейных ограничениях на переменные.
2. Графический метод решения задач линейного программирования
Пусть задача линейного программирования содержит две переменные, и. Графический метод ее решения состоит в следующем.
В системе координат строим многоугольник, который определяется системой ограничений. Целевая линейная функцияпри фиксированном значенииявляется уравнением прямой, называемой опорной прямой.
Значение целевой функции возрастает при движении прямойв направлении нормального вектора этой прямой. Перемещая эту прямую параллельно себе в направлении векторапо построенному многоугольнику ограничений, определяем вершины входа и выхода (может быть отрезок или луч).
Вершина, из которой выходит опорная прямая, дает максимальное значение, в которую приходит минимальное значение целевой функции. Определяем координаты этих вершин, и находим соответствующие значения целевой функции, подставляя координаты в выражение для целевой функции.
Пример.Решить графическим методом задачу линейного программирования: найти максимальное значение функциипри ограничениях
,
;
,.
Решение.В системе координатна плоскости строим прямуюпо двум точкам с координатамиив первой четверти, так как. Прямая делит плоскость на две полуплоскости, из которых нужно выбрать одну, удовлетворяющую первому неравенству в системе. Для этого возьмем точкуи подставим в неравенство. Если неравенство выполняется, то нужно заштриховать ту полуплоскость, в которой находится точка. Аналогично поступают с прямой. Получаем, что областью решений неравенств является четырехугольник.
Строим опорную прямую , и перемещаем ее параллельно себе в направлении векторапо четырехугольнику, определяем вершину выхода – точкуВ.
Находим координаты точки В, для этого решаем систему уравнений:
Найденные координаты точки подставляем в целевую функцию, и определяем максимальное значение:
.
Данное значение можно найти, если подставить координаты вершин четырехугольника в целевую функцию и выбрать среди них максимальное значение.