20. Математическая модель задачи формирования оптимального штата фирмы (можно на собственном примере).

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

21. Общая (или на собственном примере) математическая модель целочисленной задачи о ранце.

Речную баржу с объемом трюма V и грузоподъемностью Р нагружают n различными видами груза. Один груз вида i имеет объем v_i, вес p_i и стоимость c_i. Необходимо из всех грузов отобрать на баржу такие, суммарная стоимость которых будет максимальной, и при этом будут соблюдены ограничения на вместимость и грузоподъемность баржи.

F=∑c_ix_i (max)

∑v_ix_i≤V

∑p_ix_i≤P

x_i ≥0 – целые числа, i = 1,…,n

22.Общая (или на собственном примере) математическая модель целочисленной задачи закрепления самолетов за воздушными авиалиниями.

Авиакомпания осуществляет авиаперевозки по n маршрутам и располагает парком самолетов m типов. Количество самолетов каждого типа, имеющегося у авиакомпании равно N_i. Ежемесячно один самолет может осуществить по маршруту j авиаперевозки в объеме а_ij. Ежемесячные эксплуатационные расходы, приходящиеся на один тип самолета составляют с_ij. Ежемесячный требуемый объем перевозок по маршруту j составляет не менее b_j.

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

F=∑∑c_ijx_ij

∑x_ij=N_i

∑a_ijx_ij≥b_j

x_ij≥0 – целые числа, i=1,…,m. j=1,…,n

23.Общая (или на собственном примере) математическая модель задачи о назначениях.

Необходимо назначить n работников на n работ таким образом, чтобы суммарная эффективность выполнения всеми работниками всех работ была максимальной, при условии, что одна работа может выполняться только одним работником и один работник может выполнять только одну работ. Эффективности a_ij.

Факт назначения i-го работника на работу с номером j описывается двоичной переменной xij, которая может принимать только два значения

1- ели работник назначен на работу

x_ij =

0 – если работник не назначен на работу.

F=∑∑a_ijx_ij (max\min)

x_1j+x_2j+…+x_nj=1, i=1,…,n – выполнение работы только одним из работников

x_i1+x_i2+…+x_in=1, j=1,…,n – выполнение работником только одной из работ

24.Приведите общую (или на примере) математическую модель задачи дробно-линейного программирования.

∑c_kx_k

F=------------ (max\min)

∑d_kx_k

∑a_ikx_k≤b_i (≥,=), i=1,…,n

x≥0

∑d_kx_k ≠ 0

∑d_kx_k>0

Новая переменная: y₀=1\∑d_kx_k

F=y0∑ckxk=∑c_kx_ky₀

y_k = x_ky₀

F=∑c_kx_k (max\min)

∑a_ikx_k≤b_iy₀

∑a_ikx_ky₀≤b_iy₀ ∑a_ik≤b_iy₀, i=1,…,m

F=∑c_ky_k (max\min)

∑a_iky_k – b_iy₀ ≤ 0, i=1,…,m

∑d_ky_k=1

y_k,y₀ ≥0

x_k=y_k\y₀