Разработка производственных и управленческих решений

— 9 ;

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А.Н. Туполева

ФИЛИАЛ «ВОСТОК»

Расчетно-графическая работа

по дисциплине

«Разработка производственных и управленческих решений»

Вариант 17

Выполнил: ст. гр. 21 404

Овчинникова О.В.

Проверил: Гашева М.В.

Чистополь 2009

Решение задачи симплексным методом

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

Исходные данные:

Предприятие занимается производством 2 видов продукции 1 и 2, для их производства требуется 3 вида сырья. На изготовление единицы изделия 1 требуется сырья каждого вида кг, а для изделия 2- кг. Стоимость единицы изделия 1 -, а для 2- т.р. Необходимо составить такой план производства изделий, при котором прибыль от производства и реализации данной продукции будет максимальной. На предприятии имеется сырья в количестве .

Решение:

Составим экономико-математическую модель задачи. Для этого обозначим — количество изделий А. — количество изделий В. Эта задача является задачей оптимального использования сырья, поэтому система организации имеет вид:

+?606

9+27?606

15+15?802 (1)

15+3?840

Где справа стоит количество каждого вида сырья, которые не может быть превышено в процессе производства изделий.

?0, ?0 (2)

Целевая функция представляет собой общую стоимость произведенной продукции.

С=5+6х₂ => макс. (3)

Для решения задач симплекс методом приводят ее к каноническому виду, введя дополнительные балансовые переменные х₃, х₄, х₅, которые означают остатки сырья соответственно 1,2, 3 типов, при этом неравенство преобразуется в уравнение, т. е. левая часть сбалансирована с правой.

9+27+ х₃ ?606

15+15+ х₄ ?802 (4)

15+3+х₅ ?840

х₃, х₄, х₅— остатки 1,2,3 вида сырья.

х₁, х_2,х₃, х_4,х₅? 0 (5)

С=5+6х₂ +0х₃+0х₄+0х₅ => макс. (6)

Систему (4) можно записать в другом виде:

р₁х₁+р₂х₂+р₃х₃+р₄х₄+р₅х₅=р₀

р₁ р₂ р₃ р₄ р₅ р₀

Здесь векторы р₃р₄р₅ имеют предпочтительный вид, т. е являются единичными в одном из компонентов и нулевыми во всех остальных компонентах. Р₀— называется столбцом свободных членов системы ограничений, для решения системы (4)-(6) симплекс методом необходимо иметь опорный план, т. е. допускаются решения системы (4), для этого надо разделить на 2 группыбазисные и свободные. Сначала выбираем базисные, в качестве их выбирают векторы, имеющие предпочтительный вид, т. е в данном случае р₃р₄р_5.им соответствуют базисные переменные х₃, х₄, х₅системы (4). Остальные переменные х₁, х₂— будут свободными, при получении базисного решения все свободные переменные =0. Подставив в (4) х₁=х₂=0, получаем остальные компоненты опорного плана х₃=606, х₄=802,х₅=840. В векторном виде этот опорный план выглядит так: х₀=(0,0,606,802,840). Подставив компоненты х₀ в целевую функцию (6) получаем значение целевой функции=0. С (х₀)=0.

1 симплексная таблица (опорный план в виде симплекс таблицы)

Переход к новому опорному плану, выбор разрешающего столбца:

С_К=минС_j(c_{j=мин {-5; -6 }=-6=С2=К=2}

Выбор разрешающей строки:

b_l/ a_lk=min {b_i/a_i2(a_i2>0)} min{606/27;802/15;840/3}={22;53;280} =22=b₁/a₁₂=l=1

Генеральный элемент: a_lk=а₁₂=27

Переход к новой симплексной таблице:

B₁= b₁/ а₁₂=606/27=22

c=C-c_kb_с=c-c₂b₁=0-(-6)*22=132

a_lj=a_lj/a_lk

9/27=1/3

27/27=1

=1/27

=0/27=0

0/27=0

— 5-(-6)*1/3=-3

— 6-(-6)*1=0

0-(-6)*1/27=2/9

0-(-6)*0=0

0-(-6)*0=0

=802−15*22=472

=840−3*22=774

15−15*1/3=10

15−15*1=0

0−0*1/27=0

1−1*0=1

0−0*0=0

15−15*1/3=10

3−3*1=0

0−0*1/27=0

0−0*0=0

1−1*0=1

Вторая симплексная таблица

Переход к новому опорному плану, выбор разрешающего столбца:

С_К=минС_j(c_{j=мин {-3; 0}=—3=С1=К=1}

Выбор разрешающей строки:

b_l/ a_lk=min {b_i/a_i1(a_i1>0)}min{22/1/3;472/10;774/10}={66;47;77}=47=b₂/a₂₁=l=2

Генеральный элемент: a_lk=а₂₁=10

Переход к новой симплексной таблице:

B₂= b₁/ а₂₁=472/10=47

c=C-c_kb_с=c-c₂b₁=0-(-3)*47=148

a_lj=a_lj/a_lk

10/10=1

0/10=0

=0/10=0

=1/10

0/10=0

— 3-(-3)*1=0

0-(-3)*0=0

2/9-(-3)*0=2/9

0-(-3)*1/10=0+3/10=3/10

0-(-3)*0=0

=6

=774−10*47=304

1/3−1/3=0

1−1*0=1

1/27−1/27*0=1/27

0−0*1/10=0

0−0*0=0

10−10*1=0

0−0*0=0

0−0*0=0

0−0*1/10=0

1−1*0=1

Третья симплексная таблица

Проверка опорного плана на оптимальность:

С_К=min<0)=min (0;0;2/9;3/10;0)=0

Полученный план оптимален.

В векторном виде опорный план выглядит:

=(47;6;0;0;304)

С ()=148

Экономическая интерпретация задачи:

Объём производства будет оптимальным при достижении максимальной прибыли-148 д.ед., и при объёме производства товара-6 шт. и 47 шт.