Симплекс - метод

  • 31 авг. 2013 г.
  • 3305 Слова
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………….…………3
1. Симплекс-метод……………………………………………………….…….4
2. Идея симплекс-метода………………………………………………………4
3. Общая схема симплекс – метода……………………………………………5
4. Реализация симплекс-метода на примере………………………………….8
5. Табличная реализация простого симплекс-метода…………………..…..12
ЗАКЛЮЧЕНИЕ……………………………………………………………..…17
СПИСОК ИСПОЛЬЗОВАННОЙЛИТЕРАТУРЫ………………………..…18

ВВЕДЕНИЕ
Тема реферата касается решения задач, возникающих в экономике. При этом встает вопрос о выборе наилучшего в некотором смысле варианта решения. А на поиск возможного варианта часто влияют разного рода факторы, сужающие рамки выбора. Иначе говоря, требуется решить задачу оптимизации, которая состоит в необходимости выбора наилучшего варианта решений среди некоторого, как правило, ограниченного множества возможныхвариантов.
Задача оптимизации может быть сформулирована на языке математики, если множество доступных вариантов удается описать с помощью математических соотношений (равенств, неравенств, уравнений), а каждое решение - оценить количественно с помощью некоторого показателя, называемого критерием оптимальности или целевой функцией. Тогда наилучшим решением будет то, которое доставляет целевойфункции наибольшее или наименьшее значение, в зависимости от содержательного смысла задачи. Так, например, при инвестировании ограниченной суммы средств в несколько проектов естественной является задача выбора тех проектов, которые могут принести в будущем наибольшую прибыль. При доставке в магазины продукции от различных поставщиков возникает задача минимизации транспортных затрат.
Процесс формализациизадачи называется построением ее математической модели. Он состоит из трех этапов.
1.                Выбор параметров задачи, от которых зависит решение. Эти параметры называют управляющими переменными и обозначают , формируя из них вектор . Принять решение – это значит задать конкретные значения переменных.
2.                Построение числового критерия, по которому можно сравнивать различныеварианты решений. Такой критерий принято называть целевой функцией и обозначать через .
3.                Описание всего множества X допустимых значений переменных ограничений, связанных с наличием материальных ресурсов, финансовых средств, технологическими возможностями и т.п..
Математическая задача оптимизации состоит в нахождении такого допустимого решения , которое доставляет целевой функциинаибольшее или наименьшее значение среди всех возможных решений.
.
1. Симплекс-метод

 Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге.
Применение симплекс-метода для задачи линейного программирования предполагаетпредварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.
Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода.

2. Идеясимплекс-метода
Рассмотрим универсальный метод решения канонической задачи линейного программирования
, , ,
с n переменными и m ограничениями-равенствами, известный как симплекс-метод. 
Множество планов канонической задачи – выпуклое многогранное множество, имеющее конечное число угловых точек. И если эта задача имеет оптимальное решение,...
tracking img