7. Примеры экономических ситуаций сводящихся к задачам линейного программирования. Оптимизационная задача загрузки оборудования

Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить N₁, N₂,…, N_n единиц продукции Р₁, Р₂, .., Р_n Продукция производится на станках S₁, S₂, ..., S_m. Для каждого станка известны производительность а_ij (т.е. число единиц продукции P_j, которое можно произвести на станке S_i) и затраты b_ij на изготовление продукции P_j на станке S_i в единицу времени.

Необходимо составить такой план работы станков (т.е. так распределить выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными.

Составим экономико-математическую модель задачи. Обозначим x_ij - время, в течение которого станок S_i занят изготовлением продукции P_j .

	P1	P2	…	Pn
S1		b11 / a11	b12 / a12		b1n / a1n
S2		b21 / a21			b2n / a2n
Sm		bm1 / am1			bmn / amn
Кол-во		N1	N2	…	Nn

Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства: (1)

Для выполнения плана по номенклатуре необходимо, чтобы выполнялись следующие равенства:

(2)

Кроме того x_ij>=0.

Затраты на производство всей продукции выразятся функцией:

F= b₁₁x₁₁ + b₁₂x₁₂ +...+ b_mnx_mn

Экономико-математическая модель задачи: Найти такое решение X=(x₁₁, x₁₂,…, x_mk) удовлетворяющее системам (1) и (2) и условию неотрицательности переменных, при котором функция затрат принимает минимальное значение.

8. Примеры экономических ситуаций сводящихся к злп. Оптимизационная задача транспортировки грузов.

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

– Метод потенциалов;

– Метод северо-западного угла;

– Симплекс метод для решения транспортных задач и др.

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

Пример. Пусть некое предприятие решило оптимизировать свои систематические транспортные расходы по поставке груза в собственные каналы распределения. В структуру предприятия входят m поставщиков и n потребителей. Обозначим через: M_i мощность поставщиков, N_j - спросы потребителей, c_ij - коэффициенты затрат на перевозку единицы груза для каждой пары "поставщик - потребитель".

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

Решение. Искомый объем перевозки от i-го поставщика к j-му потребителю обозначим через х_ij и назовем поставкой клетки (i,j) Например, х₁₂ — искомый объем перевозки от 1-го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д.

Поставщики	Мощность поставщиков	Потребители и их спрос
		1	2	…	n
		N1	N2	…	Nn
1	M1	c11 x11	c12 x12		c1n x1n
2	M2	c21 x21	c22 x22		c2n x2n
m	Mm	cm1 xm1	cm2 xm2		cmn xmn

Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х_ij. Так, например, объем груза, забираемого от 1-го поставщика, должен быть равен мощности этого поставщика — M1 единицам, т.е. х₁₁ + х₁₂ + … + х₁n = M₁ (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

Система ограничений выглядит

– уравнение баланса по строкам;

– уравнение баланса по столбцам.

для любых xij>=0. Линейная функция:

Математическая формулировка задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений найти такое решение Х= (х₁₁, x₁₂, …, x_ij, ..., х_mn), при котором значение линейной функции минимально.

Особенности экономико-математической модели транспортной задачи:

– система ограничений есть система уравнений (т.е. транспортная задача задана в канонической формe);

– коэффициенты при переменных системы ограничений равны единице или нулю;

– каждая переменная входит в систему ограничений два раза.

Если , то такая задача называется закрытой. Иначе – открытой.