Читать контрольная по менеджменту: "Задачи линейного программирования" Страница 1

(Назад) (Cкачать работу)

ОглавлениеВведение

Глава 1. Теоретические основы

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

.2 Метод искусственного базиса

Глава 2. Практическая часть

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

Данная работа освещает один из способов решения задач линейного программирования (ЗЛП), а именно линейного программирования с вещественными числами симплекс-методом (конкретно - методом искусственного базиса). Глава 1. Теоретические основы

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

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

Общей задачей линейного программирования (ОЗЛП), заданной в произвольной форме записи, называют задачу, в которой требуется максимизировать (минимизировать) функциюf =cj xj (1)

при условиях

a ij x j =0 ( j= 1, …, t)

Существуют разные формы записи ЗЛП, но по теме задания нас интересует каноническая форма записи ЗЛП, так как именно к такой форме записи применим широко используемый симплекс-метод.

Задачей линейного программирования в канонической форме записи называют задачу, в которой требуется максимизировать функциюf =cj xj (4)

при условиях

a ij x j = a i0 ( i = 1, …, m) (5) j >=0 ( j= 1, …, n) (6)

Замечание: задачу минимизации f можно формально заменить задачей максимизации функции (-f).

Для того, чтобы выразить общую идею симплексного метода, приведем несколько основных понятий, относящихся к линейному программированию:

Набор чисел Х = (x 1; …; x n), удовлетворяющий всем ограничениям задачи называется планом.Набор чисел Х = (x 1; …; x n), называется опорным планом, если он соответствует крайней точке многогранника решений.План Х = (x 1; …; x n), доставляющий функцию в экстремум называется оптимальным.

Так вот суть симплекс - метода состоит в упорядоченном переборе только опорных планов при котором значение целевой функции возрастает. Таким образом мы постепенно приходим к оптимальному плану (если задача разрешима).

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

Ограничения вида «?»-

Похожие работы