43 Примеры задач линейного программирования: выпуск продукции, рацион, транспортная, портфель ценных бумаг.
Выпуск продукции:
m-виды ресурсов
n-технологические способы
За единицу времени использования j-го технологического способа (j=1,2,..,n) расходуется aij единиц n-го ресурса, запас которого равен bi (i=1,2,…,m), и выпускается cj единиц продукции.
Требуется сформировать такой план работы предприятия, чтобы выпуск продукции был наибольшим, а расход каждого вида ресурса не превосходил его запаса.
Xj-время использования j-го технологического способа. Тогда:
X=(X1,…,Xj..., Xn)-план работы предприятия, в кот все переменные не отрицательны, те Xj ≥0, j=1,2,.,n.
CjXj-планируемое к выпуску кол-во продукции.
aij Xj -кол-во i-го ресурса, приходящееся на испо-ие j-го техн-го способа
aij Xj- общий расход i-го ресурса не должен превышать его запасов на предприятии,
aij Xj≤b
Постановка задачи:
F(x)= CjXj (max),
aij Xj aij Xj
aij Xj ≤b, i=1, 2…,m.
Xj ≥0, j=1,2,.,n.
Задача планирования рац питания:
n-вид продуктов
В единице продукта j-го вида (j=1,2,…,n) содержится aij Xj единиц i-го химического элемента. (i=1,2,…,m), необходимого для организма.
bi-дневная норма потребления i-го хим вещ-ва
Сj-цена ед-цы j-го продукта
Необходимо составить рацион так, чтобы затраты на покупку продукта были минимальными при условии, что в продуктах содержится хим веществ не меньше дневной нормы.
Xj-кол-во ед-ц j-го продукта в дневном рационе.
aij Xj-кол-во i-го химического вещества
общее кол-ва i-го хим вещества не должно быть меньше дневной нормы потребления-
aij Xj ≥ b
Стоимость всего набора X=(x1,…, xj,xn) продуктов равна F(x)= CjXj
Постановка задачи:
F(x)= CjXj (min),
aij Xj ≥ b, i=1, 2…,m.
Xj ≥0, j=1,2,.,n.
Задача планирования транспортных перевозок:
В m пунктах производится однородный продукт в количествах a1, a2, …ai,…,am единиц,
Который необходимо
перевезти в другие n
пунктов, в которых этот продукт
потребляется в количествах b1,
…b2,
…bj,…bn
единиц.
Стоимость перевозки одной ед-цы продукта
из i(i=1,2,…m)
пункта произ-ва в j(j=1,2,…,m)
пункта произ-ва в j(j=1,2,…,n)
пункт потребления равна cij
денежных ед-ц,
а производится продукта больше, чем
потребляется:
ai
≥
bj.
Требуется сформировать план перевозок продукта, при котором все потребности в продукте будут удовлетворены с наименьшими затратами на перевозку.
Определим вектор X=(XII,…, Xij, …,Xmn) как план перевозок между поставщиками и потребителями, где Xij –кол-во ед-ц продукта, которое перевозится из пункта производства i в пункт потребления j, и при чем либо перевозка имеется, либо она отсутствует, те. Xij ≥0, i=1, 2, …m; j=1,2,…n.
Тогда: f(X)= cij xij –суммарная стоимость всех перевозок;
Из i пункта производства вывозится единиц продукта не более, чем производится, те XIj+…+Xij…+Xmj≥bj, j-1,2,…n.
Математическая постановка задачи:
F(x)=
CijXij
(min),
(I, j-коэфф-ты, кот не удалось прописать)
Портфель акций
Инвестор решил вложить 1800 д. е. в акции двух компаний: в топливно-нефтяную компанию (ТНК) и в компанию по производству компьютеров (КПК). Стоимости акций этих компаний соответсвенно равны 4 д. е. и 8 д. е. При этом обещают, что прибыль от 1 д. е., инвестированная в акции ТНК, будет равна 0,115 д. е., а от 1 д. е., инвестированной в акции КПК, будет равна 0,12 д. е. за год.
На рынке продажа продукции компании ТНК более устойчива, чем компании КПК. Поэтому инвестор решает приобрести акций ТНК не меньше, чем акций КПК.
Однако ТНК продает каждому будущему акционеру не более 325 своих акций, в то время как КПК продает свои акции в количествах не менее 60 штук.
Формализуйте условия вложения денег в акции указанных компаний с учетом того, что инвестор желает получить при этом наибольшую прибыль.
Изобразите на плоскости множество инвестиционных возможностей.
Найдите инвестиционные возможности, которые соответствуют желаниям инвестора.
Решение: Предположим инвестор приобретает х1 акций ТНК и х2 акций КПК. Тогда множество инвестиционных возможностей можно записать в виде
W = { X (x1, x2) ϵ R2 : 0 ≤ x1 ≤ 325,60 ≤ x2, x2 ≤ x1, 4x1 + 8x2 ≤ 1800}, а прибыль от такой сделки в виде функции f (x1, x2) = 0,115( 4x1) + 0,12 (8x2).
Математическая постановка задачи:
Найти наибольшее значение функции f (x1, x2) = 0,115( 4x1) + 0,12 (8x2) на множестве W. Рис. 4
Через это множество перпендикулярно вектору градиента Г = (0,46; 0,96) функции f (x1, x2) = 0,115( 4x1) + 0,12 (8x2) проводим прямую линию L, задаваемую уравнением 0,46x1 + 0,968x2 + γ0 = 0. Перемещая эту прямую в направлении вектора градиента, находим точку Х0(150, 150), в которой функция f (x1, x2) достигает наибольшего значения.