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

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

Современные условия рыночной экономики предъявляют к методам прогнозирования очень высокие требования. Правильный прогноз играет важнейшую роль в судьбе любого предприятия.

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

Целью предпринимаемого исследования является составление оптимального плана выпуска продукции, при котором фирма будет иметь максимальную прибыль. Также необходимо оценить каждый из видов сырья, используемых для производства. Оценки, приписываемые каждому из видов сырья, должны быть такими, чтобы оценка всего используемого сырья была минимальной, а суммарная оценка сырья, используемого на производство единицы продукции каждого вида,- не меньше цены единицы продукции данного вида. Область математики, разрабатывающая теорию и численные методы решения задач по нахождению максимального значения линейной функции (в нашем случае определение максимальной прибыли) многих переменных (четыре различных вида продукции) при наличии линейных ограничений (запасы сырья ограничены) называется линейным программированием. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом. Он гарантирует, что за конечное число шагов оптимальный план будет обязательно найден. Составив математическую модель задачи и воспользовавшись симплекс-методом для ее решения, определим оптимальный план выпуска продукции, максимальную прибыль от ее реализации, оценим каждый из видов сырья, что позволит фирме в дальнейшем развиваться с наибольшей экономической выгодой.

1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1 Понятие симплекс-метода

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

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение целевой функции при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение целевой функции. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима. [5]

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные х1, х2, ..., хr. Тогда наша система уравнений может быть записана как

Размещено на http://www.allbest.ru/

(1)

Переменные x1, x2,…, xr называются базисными, а весь набор {x1, x2,…, xr} - базисом, остальные переменные называются свободными, система ограничений (1) называется системой, приведенной к единичному базису. [2]

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения и являются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные х1, х2, ..., хr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ? 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение f самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции f не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Его идея состоит в следующем.

Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.

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

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

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

Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения. При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода. [5]

Если ограничительные условия заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных переменных - так называемых балансовых (выравнивающих). Так, например, в неравенстве
a1x1+ a2x2+…+ anxn ? b достаточно добавить в левую часть некоторую величину xn+1 ? 0 и получится равенство a1x1+ a2x2+…+ anxn+ xn+1=b.

Если переменная xl не подчинена условию неотрицательности, то её заменяют разностью двух неотрицательных переменных: xl = ul- vl, где ul, vl ? 0.

Задача минимизации функции f может быть сведена к задаче максимизации функции _f. [1]

1.2 Реализация симплекс-метода с помощью симплекс-таблиц

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

f = г0+ гr+1 xr+1+…+ гn xn > max, min

xi ? 0, i = 1,2, …, n.

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные x1, x2, ..., xr и что при этом b'1, b'2,..., b'r ? 0 (соответствующее базисное решение является опорным).

Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т.е. задача записывается в виде системы равенств:

Далее эта система оформляется в виде симплекс-таблиц:

Таблица 1

Базисные переменные

Свободные члены

x1

х2

…

…

xr

xr+1

xr+2

…

…

xn

x1

b'1

1

0

…

…

0

-a1,r+1

-a1,r+1

…

…

-a1n

х2

b'2

0

1

…

…

0

-а2,r+1

-а2,r+1

…

…

-а2n

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

xr

b'r

0

0

…

…

1

-ar,r+1

-ar,r+2

…

…

-arn

f

г0

0

0

…

…

0

-гr+1

-гr+2

…

…

-гn

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

Первая симплекс-таблица подвергается преобразованию, суть которого заключается в переходе к новому опорному решению.

Алгоритм перехода к следующей таблице:

Просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов y0) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при решении задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

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

Среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, так же, как и строка, в которой он находится. [5] Если на каком-либо этапе расчета возникает неопределенность в выборе разрешающей строки, т.е. оказывается несколько равных минимальных отношений, то следует выбирать ту строку, для которой отношение элементов следующего столбца к разрешающему является наименьшим. Если при этом снова оказываются равные минимальные отношения, то составляют отношения элементов следующего столбца, и так до тех пор, пока разрешающая строка не определится однозначно; [1]

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

Разделим каждый элемент разрешающей строки на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.

Строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

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

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

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

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

Размещено на http://www.allbest.ru/

Схема 1

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

Теперь следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте y0 (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму. [5]

1.3 Смысл двойственной задачи линейного программирования

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

f =c1x1 + c2x2 +…+ cnxn>max(4)

при условиях:a11x1 + a12x2 +…+ a1nxn ? b1

a21x1 + a22x2 +…+ a2nxn ? b2

…(5)

am1x1 + am2x2 +…+ amnxn ? bm

xj ? 0 (j = 1, 2,…m, m ? n).

Задача, состоящая в нахождении минимального значения функции

f*=b1y1 + b2y2 +…+ bmym>min(6)

при условиях:a11y1 + a12y2 +…+ am1ym ? c1

a12y1 + a22y2 +…+ am2ym ? c2

…(7)

a1ny1 + a2ny2 +…+ amnym ? cm

yi ? 0 (i = 1, 2, … k ? m)

называется двойственной по отношению к задаче (4) - (5). Задачи (4) - (5) и (6) - (7) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной- на минимум.

(8)

2. Матрица

составленная из коэффициентов при неизвестных в системе ограничений (5) исходной задачи, и аналогичная матрица

(9)

в двойственной задаче получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов - строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе (5) исходной задачи, а число ограничений в системе (7) двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (6) двойственной задачи являются свободные члены в системе (5) исходной задачи, а правыми частями в соотношениях системы (7) двойственной задачи - коэффициенты при неизвестных в целевой функции (4) исходной задачи.

5. Если i-е соотношение в системе (5) исходной задачи является неравенством, то j-я переменная двойственной задачи yj ? 0. В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (5) прямой задачи и соотношения (7) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Если одна из задач двойственной пары (4) - (5) или (6) - (7) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т. е. f max = f*min.

Если же целевая функция одной задачи из двойственной пары неограниченна (для исходной - сверху, для двойственной - снизу), то другая задача вообще не имеет планов. [3]

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1 Описание производственной ситуации

Фирма по изготовлению мебели для производства 4 видов изделий (комоды, столы, стулья и кресла) должна использовать 3 вида дерева (дуб, сосна, кедр), запасы которых на планируемый месяц составляют соответственно 3000, 3360 и 7120 м2. В приведенной ниже таблице 2 даны технологические коэффициенты, т.е. расход каждого вида древесины на изготовление единицы продукции, прибыль от реализации изделия каждого вида, а также количество часов, затрачиваемых на производство одной единицы продукции каждого вида. Сотрудники предприятия за планируемый месяц должны отработать не менее 5040 часов.

Таблица 2

Виды материала	Запасы древесины, м2	Технологические коэффициенты
		Комод	Стол	Стул	Кресло
Дуб	3000	0	1	0	2
Сосна	3360	0	4	1	3
Кедр	7120	3	1	1	1
Кол-во часов		2	3	1	4
Прибыль от реализации, руб.		400	600	200	1000

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

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

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

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

2.2 Математическое описание ситуации

Обозначим через x1 , x2 , x3 , x4 количество единиц соответствующих изделий: Комоды, столы, стулья и кресла. Тогда можно записать экономико-математическую модель задачи.

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

Найти максимум функции

f=400x1+600x2+200x3+1000x4>max,

при выполнении системы ограничений:

x2+2x4 ? 3000

4x2+x3+3x4 ? 3360

3x1+x2+x3+x4 ? 7120

2x1+3x2+x3+4x4 ? 5040,

где x1 , x2 , x3 , x4 ?0.

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

Найти минимум функции

f=3000x5+3360x6+7120x7+5040(-x8+x9)>min - общая оценка сырья, используемого на производство продукции,

при выполнении системы ограничений:

3х7+2(-х8+х9) ? 400

х5+4х6+х7+3(-х8+х9) ? 600

х6+х7+(-х8+х9) ? 200

2х5+3х6+х7+4(-х8+х9) ? 1000

- двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида (обоснование введения именно таких двойственных оценок описано в пункте 2.3).

2.3 Решение задачи

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

Обратим систему ограничений-неравенств в систему уравнений. Для этого введем 4 переменные x5, x6, x7, x8 ? 0 получим:

x2+2x4+x5 = 3000

4x2+x3+3x4+x6 = 3360

3x1+x2+x3+x4+x7 = 7120

2x1+3x2+x3+4x4-x8 = 5040

Система ограничений предлагает только 3 допустимых базисных переменных x5, x6, x7 - они входят только в одно уравнение соответственно в 1-е, 2-е, и 3-е с коэффициентом 1. В 4-е уравнение добавляем искусственную переменную x9 ? 0. Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это x5, x6, x7 и x9. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции. [4] Итак, имеем:

f=400x1+600x2+200x3+1000x4>max,

x2+2x4+x5 = 3000

4x2+x3+3x4+x6 = 3360

3x1+x2+x3+x4+x7 = 7120

2x1+3x2+x3+4x4-x8+ x9 = 5040.

Данная система является системой с базисом, в которой x5, x6, x7 и x9 базисные переменные, а x1, x2, x3, x4 и x8 свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

Таблица 3

	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	0	2	1	0	0	0	0	3000	1500
0	x6	0	4	1	3	0	1	0	0	0	3360	1120
0	x7	3	1	1	1	0	0	1	0	0	7120	7120
0	x9	2	3	1	4	0	0	0	-1	1	5040	1260
Оценка	-400	-600	-200	-1000	0	0	0	0	0	0

В строке индексных оценок таблицы 3 имеются отрицательные значения, следовательно, решение можно улучшить. Среди коэффициентов этой строки (исключая столбец свободных членов b) выбирается наименьшее отрицательное число (-1000). Данный столбец является разрешающим.

Определяем разрешающую строку. Для этого находим наименьшее из отношений свободных членов к положительным коэффициентам разрешающего столбца (1120).

Таким образом, отыскивается разрешающий элемент таблицы, расположенный на пересечении разрешающих столбца и строки (3).

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

Таблица 4

	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	3	- 1/3	2/3	0	0	- 1/3	1	0	0	6000	2000
0	x9	2	-2 1/3	- 1/3	0	0	-1 1/3	0	-1	1	560	280
Оценка	-400	733 1/3	133 1/3	0	0	333 1/3	0	0	0	0

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

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

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

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

Схема 2

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

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

Таблица 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	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

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

Таблица 6

	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 является последней.

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

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

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

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

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

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

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

Таким образом, положительную двойственную оценку имеют лишь те виды сырья (сосна, кедр), которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1м2. Так, увеличение количества сырья 2-го вида (брезент) на 1 м2 приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 288 8/9 руб. и станет равной 1920000+288 8/9=1920288 8/9 руб. При этом числа, стоящие в столбце х6 таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий 4-го вида (кресла) на 1/3 ед. и сокращения выпуска изделий 1-го вида (комоды) на 1/9 ед. Вследствие этого использование сырья 1-го вида (дуб) увеличится на 2/3 м2, а время для изготовления такого объема продукции увеличится на 1 1/9 часа. Точно так же увеличение на 1 м2 сырья 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 м2 сырья 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/

Размещено на Allbest.ru

...