Общая задача линейного программирования

Постановка задачи коммерческой деятельности может быть представлена в виде модели ЛП, если целевая функция представлена в линейной форме, а связь с ограниченными ресами представлена в виде линейных уравнений или неравенств. В общем виде такая задача имеет вид: найти максимальное (минимальное) значение линейной целевой функции F(x с палочкой сверху)=ΣCiXi->max(min) (1) при условиях ограничения Σaijxj≤bi i=1,k (2), Σaijxj=bi I=k+1,m k≤m, xj≥0,j=1,l (4)

Aij, bi, cj-заданные переменные

Стандартной задачей ЛП называется задача в определении макс (мин) значения целевой функции 1 при выполнении 2 и 4. Канонической задачей ЛП называется задача в определении макс (мин) 1 при выполнении 3 и 4. Совокупность чисел х с вектором, удовлетворяющих ограничениям задачи называется допустимым решением или планом. План х* вектор, при котором целевая функция принимает максимальное (мин) значение, называется оптимальным. В случае, когда требуется найти минимум функции F(x вектор)=(c1x1+…+cnxn) всегда можно перейти к нахождению максимума F1=F(x вектор)=-(c1x1+…+cnxn). Ограничения неравенства исходной задачи имеющие вид ≤ преобразуются в ограничения равенства путём добавления к левой части доп неотрицательной переменной, а ограничения неравенства вида ≥ преобразуются в = вычитанием из левой части доп неотрицательной переменной. Если ограничение задачи отражает наличие и расход производственных ресов, тогда значение доп переменной в плане задачи = объёму неиспользуемого соответствующего реса. Запишем ограничеие 3 в векторной форме:

X1A1 с вектором+…+ XnAn с вектором=В (5)

А и В – m-мерные векторы-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи. План Х вектор называется опорным планом основной задачи если система векторов Аj вектор, входящих в уравнение 5 с положительными коэффициентами xj>0 линейно независима. Так как векторы Аj вектор являются m-мерными, то число положительных компонент опорного плана не может превышать m. Опорный план называется невырожденным, если он содержит ровно m положительных компонент. Если в опорном плане <m, то план называется вырожденным.

19.03.12

Постановка задачи комм деятельности

Рассмотрим примеры преобразования задач комм деятельности к общей задаче ЛП и построения экономико-мат моделей.

1) Планирование товарооборота

Предприятие реализует товары нескольких групп: Aj (j=1,n). Для реализации эхтих товаров используются ресы с ограниченным объёмом: b1 – рабочее время, человекочасы; b2 – площадь торгового зала, м2; b3 – издержки обращения, руб. Известны нормы расхода каждого вида ресурса на реализацию единицы j-ой группы товара aij(i=1,3; j=1,n). Доход от продажи в расчёте на единицу товара Сj. Необходимо составить оптимальный план товарооборота по критерию максимума дохода или минимума издержек обращения.

Построение модели задачи: величина дохода линейно связана с объёмом продажи товаров Xj. Поэтому целевую функцию можно записать в виде: F(X с чертой)= (с1х1+…+сnxn)->max. При этом объём продаж не может быть <0 (Xj>=0). Добавляем ограничения на норму затрат ресов и х – их объёмы.

Σa1jxj<=b1

Σa2jxj<=b2

Σa3jxj<=b3