1) X1,x2…,XI-кол-во заготовок, раскроенных по iому способу

2) F=c1*x1+c2*x2+….+cn*xnmin – по отдходам

F=1+x2+…+xn -min–по кол-ву использованных заготовок

3) >=(=)bi, гдеi=1,2,…,n

+ xj>=0,целые

31. Транспортная задача (математическая модель). Пример. Общая постановка транспортной задачи линейного программирования. Условия баланса транспортной задачи. Открытая и закрытая транспортная задача. Фиктивный поставщик и фиктивный потребитель.

Однородный груз, сосредоточенный в mпунктах отправления (А₁, А₂,…,А_m) в количествах a₁, a₂,…,a_mсоответственно, необходимо перевезти в nпунктов назначения B₁, B₂,…,B_n. Причем спрос в каждом пункте составляет b₁, b₂,…,b_n. Известны стоимости перевозок c_ij– транспортные тарифы из каждого iв j. Стоимости задаются матрицей.

Требуется составить такой план перевозок, т.е. определить объемы перевозок груза из каждого пункта отправления в каждый пункт назначения.

1. Запасы груза из каждого пункта должны быть полностью вывезены

2. Спрос в каждом пункте должен быть удовлетворен

3. Суммарная стоимость перевозок должна быть минимальной

Целевая функция (F) выражает суммарные затраты перевозки грузов.

F = Σ_iΣ_jc_ijx_ij –> min

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

1. Ограничения, выражающие полный вывоз груза из пункта отправления

Σ_jx_ij = a_i, i = 1,2,3,…,m

2. Ограничения, удовлетворяющие спрос в каждом пункте назначения

Σ_ix_ij = b_j

X_ij ≥ 0

Условия баланса:

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

Σ_ia_i=Σ_jb_j

Задача, в которой условие баланса выполняется, называется сбалансированной или закрытой. В противном случае – открытой/несбалансированной.

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

Если суммарное предложение меньше суммарного спроса, добавляется фиктивный поставщик, предложение которого равно разности суммарного спроса и предложения.

32. Задачи, сводящиеся к транспортной задаче линейного программирования. Задача формирования оптимального штата фирмы. Пример.

К транспортной задаче можно свести распределение работников по работам, формирование оптимального штата фирмы и другие.

Формирование штата фирмы:

Задача формирования штата фирмы	Транспортная задача
Претенденты на вакантные должности	Перевозимый груз
Количество претендентов в группе	Запас груза у поставщика
Количество свободных штатных мест	Спрос на груз у данного потребителя
Стоимость обучения одного претендента из i-той группы для занятия j-й должности	Стоимость перевозки единицы груза от i-го поставщика к j-му потребителю (тарифы перевозок)
Переменные модели (управляемые факторы) xij–количество претендентов из i-й группы назначенных на j-ю должность	xij–количество груза перевозимого от i-го поставщика к j-му потребителю

Целевая функция: минимизировать затраты на обучение сотрудников.

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