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


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

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

ресурсные ограничения. Справа находится то, что мы используем на производстве, слева - то, что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0». Эти переменные несут определенный экономический смысл. Обычно они отражают недорасход ресурсов (остаток).Ограничения вида «=». Часто бывает, несмотря на то, что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса. В систему ограничений они входят с коэффициентом «1», а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»). (Метод искусственного базиса).Ограничения вида «?» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные как в предыдущем случае.

Решение ЗЛП наиболее рационально можно выполнять в табличной форме. Такие таблицы называются симплексными. В разной литературе построения симплекс таблиц немного отличаются друг от друга. Наиболее приемлемыми на мой взгляд являются таблицы, описанные в табл. 1. Таблица 1

БП

СП

1

-x m+1 …………….. - x m+s …………. -x n

x 1 = x k = x m =

b 11 …………………. b 1s ……………. b 1,n-m b k1 ……………………b ks ……………. b k,n-m b m1 …………………. b ms …………… b m,n-m

b 10 b k0 b m0

f =

b 01 …………………. b0s …………….. b 0,n-m

b 00
1.2 Метод искусственного базиса

Как уже говорилось выше, часто бывают проблемы с выделением единичного базиса. В таком случае предпочтительным является метод искусственного базиса. Наряду с исходной задачей, рассматривается расширенная задача, составленная на основе исходной, путем введения неотрицательных искусственных переменных, а из целевой функции вычтем сумму искусственных переменных, умноженную на сколь угодно большое положительное число М. В результате получим так называемую М-задачу.F = cj xj -x n+i {max} (7)

a ij + x n+i = a i0 (i = 1, …, m) (8) j >=0 (j = 1, …, n+m) (9)

В системе (8) переменные x n+i (i = 1, …, m) образуют базис, называемый искусственным. При x 1= … = x n = 0 из (8) получаем начальный опорный план М-задачи: (0; …; 0; a 10; …; a m0).

Получение оптимального плана исходной задачи с привлечением М-задачи основано на следующих утверждениях:

1. Если в оптимальном плане М-задачи все искусственные переменные равны нулю (х 1; …; х n; 0; …; 0), то план (х 1; …; хn) является оптимальным для исходной задачи.

2. Если в оптимальном плане М-задачи по крайней мере одна из искусственных переменных положительна при любом большом М, то исходная задача не имеет ни одного плана.

. Если М-задача неразрешима, то и исходная задача неразрешима.

При решении ЗЛП методом искусственного базиса искусственные переменные следует вводить лишь в те уравнения, которые не разрешены относительно «естественных» базисных переменных.

Как видно из (7), целевая функция теперь содержит два слагаемых cj xj иx n+i

поэтому в симплекс-таблицах для f



Интересная статья: Быстрое написание курсовой работы