Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

3)свободные члены одной задачи становятся коэффициентами целевой функции двойственной задачи;

4)тип неравенств меняется (≤ на ≥ и наоборот);

5) каждый столбец одной задачи порождает строку ограничений другой задачи и наоборот. В матрично-векторном виде обе задачи выглядят так:

исходная задача двойственная задача

L=(c,x)max Z=(b,y)min

Ax≤b, x≥0 Ya≥c, y≥0,

L(x₁,x₂,x₃,x₄)=48x_l+30x₂+29x₃+10x₄ max Z(y₁,y₂,y₃,y₄)=198y_l+96y₂+228y₃  min

3х₁+2х₂+4х₃+3х₄≤198 3y₁+2y₂+6y₃≥48

2х₁+3х₂+1х₃+2х₄≤96 2y₁+3y₂+5y₃≥30

6х₁+5х₂+1х₃+0х₄≤228 4y₁+ y₂ + y₃≥29

x_j≥0, jєN₄ 3y₁+2y₂≥10

y_j≥0, jєN₃

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений X(x_1, x_2, x_3, x₄) и Y(y_1, y_2, y₃) пары двойственных задач необходимо и достаточно выполнение условий:

x₁(3y₁+2y₂+6y₃-48)=0 y₁ (3х₁+2х₂+4х₃+3х₄)-198=0

x₂(2y₁+3y₂+5y₃-30)=0 y₂ (2х₁+3х₂+1х₃+2х₄)-96=0

x₃(4y₁+1y₂+1y₃-29)=0 y₃ (6х₁+5х₂+1х₃+0х₄)-228=0

x₄(3y₁+2y₂+0y₃-10)=0

В решении исходной задачи х₁>0, х₃>0, поэтому

3y₁+2y₂+6y₃-48=0

4y₁+1y₂+1y₃-29=0

Учитывая, что второй ресурс был избыточным и, согласно теореме двойственности его оценка равна нулю – y₂=0, то приходим к системе:

3y₁+6y₃-48=0

4y₁+1y₃-29=0

из которой следует, что y₁=6; y₃=5.

Таким образом получили двойственные оценки ресурсов: y₁=6; y₂=0; y₃=5; общая оценка всех ресурсов Z=198y₁+228y₃=2328.

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

Таблица N 3

Решение одной из пары двойственных задач можно найти, зная только ответ к другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение одной из пары двойственных задач на компонентах оптимального решения есть строгое неравенство, то оптимальное значение i-й переменной другой задачи равно 0, или, что то же самое - если оптимальное значение j-й переменной одной задачи строго положительно, то j-e ограничение другой из пары двойственных задач на компонентах оптимального решения есть равенство.

Важен экономический смысл двойственных оценок. Двойственная оценка, например, третьего ресурса у₃=5 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли на 5 единиц.

Расшивка "узких мест" производства

Таблица N 3

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть Т=( t₁,t₂,t₃) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H+Q^-lТ≥0, где Н - значения базисных переменных в последней симплексной таблице, а Q^-1 - обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т, максимизирующий суммарный прирост прибыли W=6t₁+5 t₃ при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции), предполагая, что можно получить дополнительно не более 1/3 первоначального объема ресурсов каждого вида.

24 ²/₇ 0 -¹/₇ t₁ 0

4 + -⁴/₂₁ 1 -⁵/₂₁ 0 ≥ 0

34 -¹/₂₁ 0 ⁴/₂₁ t₃ 0

t₁ 198

0 ≤ ¹/₃ 96

t₃ 228

t₁≥0, t₃≥0.

W=6t₁+5t₃ max

^-2/₇ t₁ + ¹/₇ t₃ ≤ 24

⁴/₂₁ t₁ + ⁵/₂₁ t₃ ≤ 4

¹/₂₁ t₁ - ⁴/₂₁ t₃ ≤ 34

t₁≤¹⁹⁸/₃, t₃≤²²⁸/₃.

t₁≥0, t₃≥0.

Как видно, после графического решения (График 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

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

Первое базисное допустимое решение легко построить по правилу "севе­ро-западного угла".

Т аблица 1

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	40 3	6	4	* 3	0	p1=0
a2=45	8 2	30 3	7 1	3	0	p2=-1
a3=70	6	5	22 1	40 4	8 0	p3=-1
	q1=3	q2=4	q3=2	q4=5	q5=1

Обозначим через (p₁, p₂,…, p_m, q₁, q₂,…, q_n) вектор симплексных множителей или потенциалов. Тогда _ij=A_ij-c_ij , iN_m, jN_n, откуда следует

Характеристики

Список файлов реферата