Задача о рационе.

Фермер имеет в своем распоряжении n-видов кормов для кормления домашних животных, каждый из которых содержит m-видов различных питательных веществ. Известно, что единица каждого вида кормов содержит определенное количество единиц каждого вида питательных веществ и имеет конкретную стоимость.

Требуется составить такой рацион, который бы удовлетворял потребность во всех питательных веществах, и имел бы наименьшую стоимость.

Транспортная задача.

Определить оптимального план перевозок однородного продукта из пунктов отправления в пункты назначения при известных тарифах, запасах в пунктах отправления и потребностях в пунктах назначения.

Раздел 1. Линейное программирование.

Предметом изучения данного раздела являются линейные экстремальные задачи, в которых целевая функция и функция ограничения линейны.

Определение: общей задачей линейного программирования называется задача, состоящая в нахождении максимального значения целевой функции.

1. Z= c_jx_j max при условии

2. a_ijx_j{ } b_i(i= )

3. x_j 0 (j n)

где a_ij; b_i; c_j – заданные постоянные величины,

1. целевая функция задачи (линейная форма)

2. ограничение задачи (типа равенства или неравенства)

3. условие неотрицательности переменной

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

Определение канонической формы задач.

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

1) функция цели исследуется на максимум или минимум 2) ограничение задачи только типа неравенства (в одну сторону)

3) все переменные неотрицательны (x_j ≥ 0)

4) элементы столбца правых частей положительны (b_i>0 i= )

Определение: совокупность n-чисел (x₁……x_n), удовлетворяющих ограничению задачи, назовем допустимым решением или планом задачи. План X^*=(X …X ) называется оптимальным, если на нем целевая функция принимает максимальное (минимальное) значение.

Основные свойства решения задач лп

Рассмотрим различные формы представления задачи линейного программирования:

1. В екторная форма записи:

Z=CXmax

A₁X₁+…+A_nX_n B

X 0

где C=(C₁…C_n) – вектор коэффициента целевой функции (строка коэффициента);

X=(Х₁…….Х_n) – вектор-строка переменных задач;

CX – скалярное произведение векторов, равное сумме произведений их соответствующих компонентов,т.е. СХ = С₁Х₁ +….+ С_nХ_n;

A₁…A_n – векторы условий, но векторы-столбцы при соответствующих переменных;

B – вектор - столбец ограничения или вектор правых частей.

2. М атричная форма

Z=CX max

AX B

X 0

A – матрица условий, составленная из столбцов-векторов A₁…A_n,

X2

3)Геометрическая интерпретация

Z=C₁X₁+…..+C_nX_n max

a₁x₁+….+a_n x_n b_i

……………..

X1

A_m x₁+……+a_mnx_n b_m

x_1….. x_n 0

Геометрическую интерпретацию даем только в случае двух переменных. Тогда выражение Z=C₁X₁+C₂X₂ в зависимости от значения Z представляет собой семейство параллельных прямых, которые в точке (0,0) Z=0, и с увеличением Z прямые «приближаются» к границам области допустимых решений, которые определяются заданными неравенствами. Максимальное значение целевой функции достигается в одной (или нескольких) граничных точках области допустимых решений.

Необходимые сведения берутся из линейной алгебры.

Вектор – упорядоченный набор из n-действительных чисел, которые называются координатами вектора.

Векторы равны, когда они имеют одинаковую размерность и соответствующие координаты совпадают.

Вектор B , равный α₁A₁+…+α_nA_n, является линейной комбинацией векторов A₁…A_n, если существуют такие числа a₁…a_n, одновременно не равные нулю, при которых это равенство выполняется.

Система векторов A₁…A_n называется линейно зависимой, если существуют такие числа a_1,…,a_m 0(одновременно не равные нулю) и такие что выполняется равенство: (*) 0=a₁A₁+…a_mA_m , где 0 – нуль-вектор (все его компоненты равны нулю).

Через Rⁿ обозначим множество всех векторов размерности n c операциями сложения векторов и умножения их на число. В дальнейшем рассмотрим только векторы одинаковой размерности.

Если равенство (*) выполняется только в случае, когда все a_1,…a_n равны нулю, то система векторов A₁…A_n линейно независима.

Содержательно: система векторов линейно независима, если никакой ее вектор нельзя представить в виде линейной комбинации остальных векторов системы.

Базис – максимально линейно-независимая система векторов в пространстве. Любой базис содержит в пространстве Rⁿ n-векторов. Единичный базис – система, состоящая из n различных единичных векторов E₁……E_n (i-й единичный вектор, у которого на i месте 1, а остальные компоненты равны 0).