Задача о раскрое материалов.

Рассмотрим простейшую модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.

Модель задачи раскроя по одному измерению длинномерных материалов (прутков, труб, профильного проката и др.) может быть сформулирована так. Пусть имеется N штук исходного материала, длина каждой равна l. Нужны заготовки m видов, длины которых равны l_i ( i =  ); b_i — потребность в заготовках каждого вида, a_ij — количество заготовок i-го вида, получаемых при раскрое единицы исходного материала по j-му ( j =  ) варианту, c_j — отходы при раскрое единицы исходного материала по j-му варианту. План задачи x = ( x₁, …, x_j, …, x_n ), где x_j — количество единиц исходного материала, планируемое к раскрою по j-му варианту.

Целевая функция — минимум отходов, получаемых при раскрое:

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

на число единиц исходного материала

на удовлетворение ассортиментного спроса потребителей

,

и условии неотрицательности:

.

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

Рассмотрим простейший вариант модели транспортной задачи, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям. Причем потребителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Однако от того, насколько рациональным будет прикрепление пунктов потребления к пунктам производства, существенно зависит объем транспортной работы, возникает задача о наиболее рациональном плане перевозок грузов, при котором потребности полностью удовлетворяются, вся продукция от поставщиков вывозится, а затраты на транспортировку минимальны.

Задача формулируется так. Имеется m пунктов производства, a_i ( i =  ) — объем выпускаемого продукта. Этот продукт нужно доставить n потребителям, где потребность составляет b_j ( j =  ) единиц. Причём .

Введем условные обозначения:

c_ij — затраты на перевозку единицы продукта из i-го пункта производства в j-ый пункт потребления, x_ij — количество продукта, перевозимое из i-го пункта производства в j-ый пункт потребления.

Математическая модель транспортной задачи: целевая функция, описывающая транспортные затраты,

min

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

на возможности поставщиков — весь продукт из пунктов производства должен быть вывезен:

,

на спрос потребителей, который должен быть удовлетворен:

при условии неотрицательности переменных:

.

2.3. Линейные векторные пространства Основные понятия линейного векторного пространства.

В экономике приходиться изучать объекты, для задания которых необходим некий набор упорядоченных данных. Пусть, например, некоторый промышленный район производит станки, хлопчатобумажные ткани, автомобили, телевизоры и т. д. Для характеристики производства района, очевидно, потребуется упорядоченная система из n действительных чисел. В данном случае целесообразно будет обратиться к курсу аналитической геометрии.

О п р е д е л е н и е  1.  Совокупность всевозможных упорядоченных систем из n действительных чисел после введения в нее операций сложения и умножения на действительное число называется n-мерным векторным пространством.

При изучении систем векторов важную роль играет понятие линейной зависимости векторов.

О п р е д е л е н и е  2. Вектор В называется линейной комбинацией векторов A₁, A₂, ... , A_n , если существуют такие числа k₁, k₂, ... , k_n, при которых выполняется соотношение B = k₁ A₁ + k₂ A₂ + ... + k_n A_n .

О п р е д е л е н и е  3. Система векторов A₁, A₂, ... , A_r  (r > 1) называется линейно зависимой, если хотя бы один из векторов системы является линейной комбинацией остальных, и линейно независимой — в противном случае.  

Рассматривая линейно зависимую систему векторов A₁, A₂, ... , A_n , возьмем такую линейно независимую подсистему векторов A₁, A₂, ... , A_r  (r n), к которой невозможно присоединить ни одного вектора системы, не нарушив линейной независимости. Такая подсистема называется максимальной линейно независимой подсистемой данной системы векторов. Число векторов, входящих в любую максимальную линейно независимую подсистему векторов, называется рангом системы, а сами вектора составляют базис системы.

О п р е д е л е н и е  4. Базисом  n-мерного векторного пространства называется любая совокупность n линейно независимых векторов этого же пространства.

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

В качестве базиса удобно выбрать систему единичных векторов n-мерного векторного пространства:

(2.1)

Тогда компоненты любого n-мерного вектора можно считать координатами этого вектора в единичном базисе.