Реферат: Линейное и динамическое программирование

Как видно, после графического решения (График 2) программа расшивки приобретает вид:

t₁ =21, t₂ =0, t₃ =0

С новым количеством ресурсов: 198+21 219

b' = 96+0 = 96

228+0 228

у предприятия будет новая производственная программа.

Найдем h'=Q^-1 b'

⁵ /₂₈ 0 -¹ /₇ 219 30 -x₃

-⁴ /₇ 1 -¹ /₇ 96 = 0 -x₆

-³ /₂₈ 0 ² /₇ 228 33 -x₁

Теперь новая производственная программа имеет вид: X'_{о pt} =(33;0;30;0). При этом второй ресурс был использован полностью.

219

При наличии ресурсов b' = 96 производство наиболее выгодно, так как

228

достигается max прибыль с использованием всех ресурсов. Также обратим внимание на то, что производство продукции 1–го вида при заказе дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а производство продукции 3–го вида – увеличить на единицу.

ΔL_max =(Y,t)=6·21=126, где Y=(6;0;5); t(21;0;0)

L'_max = ΔL_max + L_max =126+2328=2454.

Этот результат можно проверить, подставив значения х₁ и х₃ в первоначальную целевую функцию: L'_max =48x_l +30x₂ +29x₃ +10x₄ =31·37+41·21=1147+861=2454.

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

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a₁ , а₂ ,..., а_m единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b₁ , b_2, ,…, b_n единиц. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения равна c_ij и известна для всех маршрутов. Необходимо составить план перевозок, при кото­ром запросы всех пунктов потребления были бы удовлетворены за счет имею­щихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через x_ij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребле­ния

математическая модель транспортной задачи будет выглядеть так:

найти план перевозок

X=(x_ij ), x_ij ³0, iÎN_m , jÎN_n

минимизирующий общую стоимость всех перевозок

при условии, что из любого пункта производства вывозится весь продукт

, iÎN_m

и любому потребителю доставляется необходимое количество груза

, jÎN_n

Для решения транспортной задачи чаще всего применяется метод потен­циалов. Пусть исходные данные задачи имеют вид

А(а₁ ,а₂ ,а₃ )=(40;45;70); В(b₁ ,b₂ ,b₃ )=(48;30;29;40); 3 6 4 3

С= 2 3 1 3

6 5 1 4

Общий объем производства Sa_i =40+45+70=155 больше, чем требуется всем потребителям Sb_j =48+30+29+40=147, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 155-147=8 единиц, причем тари­фы на перевозку в этот пункт условимся считать равными нулю, помня, что пе­ременные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.