45. Методы линейного планирования.

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

Применение линейной модели планирования:

Линейная модель планирования обычно является достаточно всеобъемлющей и может применяться по нескольким причинам:

1. планы такого типа разрабатываются для создания новых организаций;

2. организации могут представлять подобные планы регулярно (например, каждые 5 лет), при этом, на основе самооценки организацией определяются миссия, задачи, цели и планы действий на определенный период деятельности, которые затем утверждаются руководством;

3. организации могут разрабатывать указанные планы по требованию учредителя как условие получения финансовой поддержки;

4. для организаций, осуществляющих крупные новаторские проекты, ведущих строительство, проводящих кампании по сбору средств или намеревающихся изменить основное направление своей деятельности, такой подход может явиться полезным при разработке четкой концепции будущего компании;

5. линейный подход часто используется в том случае, когда организации необходимо продемонстрировать широкое участие общественности в процессе планирования или выработать план, который будет опубликован в качестве официального документа и будет изучаться и комментироваться как противниками, так и сторонниками.

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

46. Общая постановка задачи линейного планирования.

Требуется определить значения n переменных (x1,x2,x3 …), которые минимизируют целевую функцию и при этом удовлетворяют условиям ограничений

Для решения таой задачи те условия ограничений, в которых неравенство обозначено ≥, должны умножить на (-1). Если все условия ограничений заданы системой неравенств, то говорят, что задача линейного планирования задана в канонической форме (нахождение min-ма). Каноническая форма представляет собой нахождение минимального значения функции

Условия ограничений задач в каноническом форме представляют собой чёткое равенство левой и правой частей

Неравенство обращается в равенство введением дополнительных переменных

При введении новых переменных должно соблюдаться условие: x_j ≥0; x_k+1≥0.

Если рассмотреть первоначальную поставленную задачу и задачу в канонической форме, в первой задаче x_j=n, а в задаче , в которой имеется неравенство количество искомых переменных увеличится на такое значение, сколько присутствует неравенств.

47. Геометрическая интерпретация задачи линейного плакирования.

Найти параметры х1 х2… максимизирующих целевую функцию. При этом должны удовлетворятся условиям ограничения. Для этого целевую функцию умножим на (-1) , а в условиях ограничений от неравенств перейдем к равенству, введя дополнительную переменную. Изобразим полученные прямы на оси координат. Оптимальное решение на-ся в одной из вершин области допустимых решений. Если целевая функ-я зависит от n переменных, то и условие ограничения будут представлять собой объемную фигуру, а оптимальное решение будет лежать на плоскости n переменных в одной из вершин, объемной области допустимых решений.

Пусть имеются вектора

A1*x1+A2*x2+…+An*xn=B

Вектор ограничения разлагается на систему векторов А причем х1 х2 …хn наз. компонентами данного разложения. Необходимо найти допустимые решения задач, которые были бы неотрицательны по векторам условий ограничений. Сис-ма ур-й ограничений имеет множество решений, и в этом множестве необходимо найти оптимальное. n-m – свободные переменные которые могут принимать произвольные значения(оптимальные), а остальные m переменные выражаются через свободные переменные и наз базистыми. Значение пременных х1 х2 ..хn, в которых базисные переменные положительны, а остальные свободные переменные раны 0 наз опорными решениями. Каждое опорное решение соответствует определенной вершине области допустимых решений.