1. Предмет и задачи курса. Экономико-математическая модель задачи линейного программирования. Пример.

Математическое программирование – дисциплина, занимающаяся изучением экстремальных задач (max/min), разработкой методов их решения.

Математическое программирование делится на задачи линейного и нелинейного программирования (целочисленное, выпуклое, динамическое, параметрическое). Многие инженерно-экономические задачи можно с достаточной степенью точности описать с помощью линейной целевой функции и системы линейных ограничений. Раздел, изучающий такие задачи, называется линейным программированием.

Этапы линейного программирования:

1. постановка задачи (словесная формулировка), формулировка условий задачи, выбор критериев оптимальность

2. сбор необходимых данных, составление исходной матрицы

3. построение экономико-математической модели

4. решение задачи одним из математических методов

5. анализ полученных результатов

Экономико-математическая модель.

Для производства 3 видов изделий (A,B,C) используется 3 вида различного сырья в количестве 180, 210, 244 единицы. Нормы затрат каждого вида сырья на производство единицы продукции данного вида приведены в таблице:

I	4	2	1
II	3	1	3
III	1	2	5

Цена от реализации изделий:

A	B	C
10	14	12

Определить план выпуска продукции, при котором прибыль максимальна. Составить математическую модель.

Решение: пусть предприятие производит x₁ изделий вида А, x₂ изделий вида B и x₃ изделий вида С. Так как производство ограничено имеющимся сырьем и количеством изготовляемых изделий, то должны выписываться условия:

4х₁+2х₂+х₃

3х₁+х₂+3х₃

х₁+2х₂+5х₃

все x0,

Z = 10x1+14x2+12x3 (max).

Методы решения:

1. графический (быстро и наглядно решает простейшие задачи)

2. симплекс-метод (универсальный метод)

3. метод потенциалов (им решаются транспортные задачи)

Необходим контроль, анализ решений, корректировка оптимального плана.

2. Общая постановка задачи линейного программирования. Каноническая форма задачи линейного программирования.

Найти совокупность значений x₁, x₂, … , x_n, удовлетворяющим условию и доставляющим функции Z экстремальное значение.

n

∑aijxj (<=, =>,=)bi - ограничения (1,1)

i=1

xj=>0 - условия неотрицательности (1,2)

i=1,m

j=1,n

n

Z = ∑cjxj - целевая функция (1,3)

i=1

Совокупность значений переменных x₁, x₂, … , x_n, удовлетворяющих условиям 1.1-1.3 называется допустимым планом. Оптимальным планом называется такое решение, при котором целевая функции достигает экстремума.

Канонический вид задачи линейного програмирования:

а₁₁х₁+ а₁₂х₂+ …+а_1jх_j+..+a_1nx_n=b₁

а₂₁х₁+ а₂₂х₂+…+ а_2jх_j+..+a_2nx_n=b₂

а_i1х₁+ а_i2х₂+…+ а_ijх_j+..+a_inx_n=b_i

а_m1х₁+ а_m2х₂+…+ а_mjх_j+..+a_mnx_n=b_m

все x_i =>0, i=1,n j=1,m

Z=c₁x₁+c₂x₂+…+c_nx_n (max)

Приведение задачи к каноническому виду:

1. переход от ограничений-неравенств к ограничениям-равенствам (ограничение-неравенство вида сводится к ограничению-равенству добавлением к его левой части дополнительной (балансовой) неотрицательной переменной, а вида - вычитанием)

2. замена переменных, которые не подчинены условию неотрицательности

3. переход задачи min к max (Z = Z)