Симплекс метод

Таблица 4.

В новой таблице 4 все элементы разрешающего столбца = 0, кроме разрезающего элемента, он всегда равен 1.

Столбец, у которого в разрешающей строке имеется 0,в новой таблице будет таким же.

Строка, у которой в разрешающем столбце имеется 0,в новой таблице будет такой же.

В остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

 

 

 

Схема 2.

В строке индексных оценок имеются отрицательные значения, следовательно, решение не является оптимальным.

При составлении новой  таблицы переменная х₉ попадет в разряд свободных, а переменная х₁ станет базисной.

 

	cj	400	600	200	1000	0	0	0	0	0	0
cбазис	базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	b	δ
0	x5	0	-1 2/3	- 2/3	0	1	- 2/3	0	0	0	760
1000	x4	0	1 1/3	1/3	1	0	1/3	0	0	0	1120
0	x7	0	3 1/6	1 1/6	0	0	1 2/3	1	1 1/2	-1 1/2	5160	3440
400	x1	1	-1 1/6	- 1/6	0	0	- 2/3	0	- 1/2	1/2	280
Оценка		0	266 2/3	66 2/3	0	0	66 2/3	0	-200	200	1232000

Таблица 5.

В строке индексных оценок имеются отрицательные значения, следовательно, продолжаем улучшать решение.

	cj	400	600	200	1000	0	0	0	0	0	0
cбазис	базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	b	δ
0	x5	0	-1 2/3	- 2/3	0	1	- 2/3	0	0	0	760
1000	x4	0	1 1/3	1/3	1	0	1/3	0	0	0	1120
0	x8	0	2 1/9	7/9	0	0	1 1/9	2/3	1	-1	3440
400	x1	1	- 1/9	2/9	0	0	- 1/9	1/3	0	0	2000
Оценка		0	688 8/9	222 2/9	0	0	288 8/9	133 1/3	0	0	1920000

Таблица 6.

Т.к. строка индексных оценок не содержит отрицательных значений, данная таблица 6 является последней.

Оптимальным будет решение  (2000; 0; 0; 1120; 760; 0; 0; 3440; 0), при котором  f_max =1920000.

Это означает, что

Прямая задача:

Для получения наибольшей прибыли, равной 1920000 руб., предприятие должно выпустить 2000 единиц продукции 1-го вида (комоды) и 1120 единиц продукции 4-го вида (кресла), продукцию 2-го и 3-го видов (стулья и столы) в данных условиях производить не выгодно.

 

 

Двойственная  задача:

При этом плане сырье 2-го и 3-го типов (сосна и кедр) будет использовано полностью, а 760 м² сырья 1-го типа (дуб) останутся неизрасходованными. Из таблицы 6 также видно, что оптимальным решением двойственной задачи является х₅=0; х₆=288 8/9; х₇=133 1/3; (-х₈+х₉)=0.

Переменные х₆ и х₇ обозначают условные двойственные оценки единицы сырья, соответственно 2-го и 3-го видов. Эти оценки отличны от нуля, а сырье 2-го и 3-го видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья 1-го вида равна нулю (х₅=0). Этот вид сырья не полностью используется при оптимальном плане производства продукции (остаток 760 м²). Двойственная оценка (-х₈+х₉)=0 показывает, что сотрудники предприятия отработают на 3440 часов больше минимально допустимого значения (по условию задачи: сотрудники предприятия за планируемый месяц должны отработать не менее 5040 часов).

Таким образом, положительную  двойственную оценку имеют лишь те виды сырья (сосна, кедр), которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1м². Так, увеличение количества сырья 2-го вида (брезент) на 1 м² приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 288 8/9 руб. и станет равной             1920000+288 8/9=1920288 8/9 руб. При этом числа, стоящие в столбце х₆ таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий 4-го вида (кресла) на 1/3 ед. и сокращения выпуска изделий 1-го вида (комоды) на 1/9 ед. Вследствие этого использование сырья 1-го вида (дуб) увеличится на 2/3 м², а время для изготовления такого объема продукции увеличится на 1 1/9 часа. Точно так же увеличение на 1 м² сырья 3-го вида (кедр) позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 133 1/3 руб. и составит         1920000+133 1/3 =1920133 1/3 руб. Это будет достигнуто в результате увеличения выпуска изделий 1-го типа (комоды) на 1/3 ед., причем время, затраченное на производство этого объема продукции возрастет на 2/3 часа. [3]

Продолжим рассмотрение оптимальных двойственных оценок. Вычисляя минимальное значение целевой функции двойственной задачи:

          f _min =3000*0+3360*288 8/9+7120*133 1/3+5040*0=1920000,

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

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

   400+2*0 = 400

0+1155 5/9+133 1/3+3*0 > 600

288 8/9+133 1/3+0 > 200

2*0+866 2/3+133 1/3+4*0 = 1000

Второе и третье ограничения  двойственной задачи выполняются как строгие неравенства. Это означает, что двойственные оценки сырья, используемого на производство одного изделия 2-го и 3-го видов (стулья, кресла), выше цены этого изделия и, следовательно, выпускать изделия этих видов невыгодно. Их производство и не предусмотрено оптимальным планом прямой задачи. Первое и четвертое ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий 1-го и 4-го видов (комоды, кресла), равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

ЗАКЛЮЧЕНИЕ

В ходе курсовой работы были решены следующие основные задачи: составлен оптимальный план выпуска продукции, при котором фирма будет иметь максимальную прибыль; произведены оценки каждого из видов сырья, используемых для производства.

В результате проведенных  исследований было установлено, что  для получения наибольшей прибыли, равной 1920000 руб., предприятие должно выпустить 2000 единиц продукции 1-го вида (комоды) и 1120 единиц продукции 4-го вида (кресла), продукцию 2-го и 3-го видов (столы и стулья) в данных условиях производить не выгодно.

При полученном оптимальном плане сырье 2-го и 3-го типов (сосна и кедр) будет использовано полностью, а 760 м² сырья 1-го типа (дуб) останутся неизрасходованными.

Двойственные оценки сырья, используемого на производство одного изделия 2-го и 3-го видов (столы, стулья), выше цены этого изделия и, следовательно, выпускать изделия этих видов невыгодно. Их производство и не предусмотрено оптимальным планом. Двойственные оценки сырья, используемого для производства единицы соответственно изделий 1-го и 4-го видов (комоды, кресла), равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

Сравнивая результаты, полученные при решении прямой и двойственной задач, можно с уверенностью говорить, что найденный план действительно является оптимальным; а, следовательно, мы решили важную задачу, стоявшую перед фирмой.

 

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Акулич И.Л. Математическое программирование в примерах и задачах. М., 1986.
2. Грешилов А.А. Прикладные задачи математического программирования. М., 1990.
3. Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2002. - 208 с.: ил. - (Серия "Краткий курс").
4. Хемди А. Таха. Введение в исследование операций. Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007.
5. Электронный учебник. Математические методы. © 2005 ВТК  
   Автор: Попова Н.В. Разработчик: Родионова И.В. http://matmetod-popova.narod.ru/