1. Сутність задачі лінійного програмування (злп).Сформулюйте і складіть моделі задач "раціонального використання ресурсів" і "раціону" в загальному вигляді.

Задачами линейного программирования называются оптимизационные задачи, в которых ограничения, представленные в виде равенств или неравенств, и целевая функция линейна. ЗЛП обладают особенностью, что ф-ия цели, функ-ые ограничения и прямые ограничения всевходящие в них неизвестные находятся в первой степени. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

целевая функция: z = c1x1 + c2x2 + ... + cnxn → max(min); (1)

ограничения:

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,

a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2,

am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm; (2)

требование неотрицательности: xj ≥ 0, (3)

При этом aij, bi, cj ( ) - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3). Систему ограничений (2) называют функциональными ограничениями задачи, а ограничения (3) - прямыми.

Задача рационального использования ресурсов Экономическая постановка: Предприятие выпускает n видов продукции, используя m видов ресурсов. Известна матрица удельных расходов ресурсов А=||аij|| (i=1,m; j=1,n), где аij – кол-во единиц j-го вида продукции. Запасы ресурсов выражаются величиной bi (i=1,m),а прибыль cj (j=1,n).Необходимо составить план производства изделий из имеющихся ресурсов, обеспечивающих максимальную прибыль предприятию. Математическая модель. Обозначим искомый планируемый выпуск прод-и j-го вида хj(j=1,n).Тогда целевая функция, выражающая максимизировать суммарную прибыль будет иметь вид: z = c1x1 + c2x2 + ... + cnxn ( max) (1.1) Ограничения, отражающие тот факт, что расходы ресурсов не могут превышать их запасы, имеют вид: (2) (только со знаком ≤) На переменные накладываются такие условия неотрицательности: х1≥0, х2≥0….,хn≥0.(1.3) Чтобы решить задачу, нужно определить неотрицательные значения переменных х1, х2….,хn, удовлетворяющие системе основных ограничений(2) и доставляющие максимум целевой функции (1.1)

Задача составления рациона. Экономическая постановка: Для откорма животных можно использовать n видов кормов,которые содержат m видов питательных веществ. Содержание каждого питательного вещества в единице каждого вида корма задается матрицей А=||аij|| (i=1,m; j=1,n), где аij – содержание i-го питательного вещества в единице j-го вида корма. Необходимо составить суточный рацион, удовлев-ий требованиям питательности и минимальной стоимости. Математическая модель. Обозначим кол-во кормов, направляемых животным, х1, х2….,хn. Тогда целевая фун-ия, выражающая минимизировать ст-ть рациона, имеет вид: z = c1x1 + c2x2 + ... + cnxn (min).(2.1) Ограничения, отражающие требования питательности: (2)(только со знаком ≥). На переменные накладываются такие условия неотрицательности: х1≥0, х2≥0….,хn≥0 (2.3). Решение задачи- набор значений переменных х1, х2….,хn, удовлев-ий (2) и (2.3) и достовляющий минимум целевой ф-ии (2.1)

2. Означення канонічного вигляду ЗЛП. Теореми про заміну нерівностей рівняннями. Відповідно сформульованим теоремам, перетворіть задачі "раціонального використання ресурсів" і "раціону" і надайте економічний зміст додатковим змінним і коефіцієнтам цільової функції при них.

ЗЛП называется заданной в каноническом виде, если её система основых ограничений представлена уравнениями. Чтобы привести ЗЛП к канон. виду, необходимо в системе осн. огран-ий перейти от неравенств к уравнениям, введя дополнительные переменные на основании теорем о замене неравенств уравнениями.Теорема1. Неравенство

g(х1, х2….,хn) ≤b (1), эквивалентно системе g(х1, х2….,хn)+хn+1 =b

хn+1≥0

Теорема2 Неравенство g(х1, х2….,хn) ≥ b (1), эквивалентно системе g(х1, х2….,хn)-хn+1 =b

хn+1≥0

Приведем к канон-ому виду матем. модель задачи использ-ия ресурсов. Так как в системе осн. ограничений m неравенств и в каждое из них неоходимо водитьдополн-ую переменную, то всего их будет m: хn+1- в первом; хn+2-во 2-ом и т.д. Матем-ая модель приобретает вид: z = c1x1 + c2x2 + ... + cnxn+0 хn+1 +0 хn+2+…+0 хn+ m ( max)

a11x1 + a12x2 + ... + a1nxn + хn+1 =b1,

a21x1 + a22x2 + ... + a2nxn++ хn+2 =b2,

am1x1 + am2x2 + ... + amnxn+ + хn+ m = bm;

х1≥0, х2≥0….,хn≥0; хn+1≥0; хn+2≥0; хn+ m ≥0

Аналогично приводится к каноническому виду матем—ая модель задачи состовления рациона:

z = c1x1 + c2x2 + ... + cnxn+0 хn+1 +0 хn+2+…+0 хn+ m (min )

a11x1 + a12x2 + ... + a1nxn - хn+1 =b1,

a21x1 + a22x2 + ... + a2nxn+- хn+2 =b2,

am1x1 + am2x2 + ... + amnxn+ -хn+ m = bm;

х1≥0, х2≥0….,хn≥0; хn+1≥0; хn+2≥0; хn+ m ≥0