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

Министерство образования и науки Российской Федерации

ФГБОУ ВПО Тульский государственный университет

РЦПК

Кафедра «Финансы и менеджмент»

КУРСОВАЯ РАБОТА

«Методы оптимальных решений»

Выполнил: студент гр. Б760742 Демидова Т.М.

Проверил: доц.кафФиМ Гучек Н. Е.

Тула 2017г.



Задача

Организация имеет возможность выпускать три вида изделий П1, П2, П3, При их изготовлении используется три вида ресурсов Р1, Р2, Р3. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход ресурса i-го вида (i=1,2,…,m) на единицу изделия j-го вида (j=1,2,…,n) составляет aijден. ед. Цена единицы продукции j-го вида равна сj. Требуется найти оптимальный план выпуска изделий, который обеспечивал бы организации максимальный доход.

Обязательные требования к решению задачи.

1. Построить экономико-математическую модель задачи распределения ресурсов.

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

3. Найти оптимальное решение прямой и двойственной задач линейного программирования двумя методамиА и Б, пояснить экономический смысл всех переменных, участвующих в решении.

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

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

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

7. Определить величину ?bs ресурса Рs, введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства ?br единиц ресурса Рr.

8. Оценить целесообразность приобретения ?bk единиц ресурса Рk по цене сk за единицу.

9. Установить, целесообразно ли выпускать новое изделие П4, на единицу которого ресурсы Р1, Р2, Р3 расходуются в количествах a14, a24, a34 единиц, а цена единицы изделия составляет с4денежных единиц.

10. Решить прямую и двойственную задачилинейного программирования в среде MicrosoftExсel, приложить отчеты.



1. Обоснование оптимального плана производства

Обозначение	Вариант 6	Обозначение	Вариант 6	Обозначение	Вариант 6	Обозначение	Вариант 6	Обозначение	Вариант 6
B1	3	А11	1	А21	2	А31	3	С1	3
B2	15	А12	3	А22	3	А32	1	С2	4
B3	4	А13	2	А23	1	А33	2	С3	1

Обозначения	Вариант 6	Обозначения	Вариант 6	Обозначения	Вариант 6	Обозначение	Вариант 6
r	1	k	3	А14	4	С4	35
?br	0,2	?bk	0,2	А24	2
s	2	?bk	15	А34	3

2. Построение экономико-математической модели задачи распределения ресурсов

Введем переменные: х1- объем производства продукции первого вида; х2 - объем производства продукции второго вида; х3 - объем производства продукции третьего вида.

Норма затрат Ресурсы	Виды изделий	Запас ресурсов	Скрытые цены ресурсов
					yi	yi*
	1	3	2	3
	2	3	1	15
	3	1	2	4
Цена единицы изделия	3	4	1	fmax(х)	gmin(у)
План выпуска	xj
	xj*

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

где n - количество видов продукции.

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

экономический математический модель ресурс

где m - количество ресурсов.

Также должно выполняться условие не отрицательности переменных:

Таким образом, экономико-математическая модель прямой задачи линейного программирования (ПЗЛП) варианта 6 имеет вид:

при ограничениях:

Данная ПЗЛП имеет стандартную форму записи, поскольку в задаче на максимум все функциональные (ресурсные) ограничения имеют знаки «меньше или равно».

Построение двойственной задачи к задаче распределения ресурсов

Целевая функция ДЗЛП представляет собой совокупные затраты второго предприятия на приобретение всех ресурсов первого предприятия, при этом второе предприятие стремиться, чтобы его затраты на приобретение ресурсов у первого предприятия были минимальными:

.

Ограничениями ДЗЛП является система неравенств, отражающая условия, при которых первому предприятию будет выгодно продать свои ресурсы вместо производства из них продукции, то есть при равенстве или превышении суммы, полученной от второго предприятия, над суммой дохода, полученной от реализации продукции:

.

Должно выполняться условие не отрицательности переменных:

.

Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу. Для варианта 0 матрица коэффициентов при переменных в системе ограничений ПЗЛП имеет вид:



.

Тогда транспонированная матрица, отражающая коэффициенты при переменных в системе ограничений ДЗЛП, имеет вид:

.

Таким образом, экономико-математическая модель ДЗЛП варианта 6 имеет вид:

при ограничениях

3. Решение прямой и двойственной задач линейного программирования

Для ПЗЛП каноническая форма записи имеет вид:

Для перехода к канонической форме записи ПЗЛП варианта 6 следует добавить дополнительные переменные х4, х5, х6, в соответствующие неравенства со знаком «+», поскольку они отражают возможный остаток неиспользованных ресурсов:

Для ДЗЛП каноническая форма записи имеет вид:

Для перехода к канонической форме записи ДЗЛП варианта 6 следует добавить дополнительные переменные y4, y5, y6, в соответствующие неравенства со знаком «», поскольку они отражают возможное превышение затрат на приобретение ресурсов над ценой реализации продукции (возможный убыток от производства продукции):



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

Во взаимодвойственных задачах линейного программирования первоначальным переменным ПЗЛП соответствуют дополнительные переменные ДЗЛП и аналогично первоначальным переменным ДЗЛП соответствуют дополнительные переменные ПЗЛП.

Установим соответствие переменных прямой и двойственной задачи для варианта 0:

х1 y4	х2 y5	х3 y6	х4 y1	х5 y2	х6 у3

Одновременное решение ПЗЛП и ДЗЛП с помощью симплекс-таблиц

сi	сj	3	4	1	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	1	3	2	1	0	0	3
0	x5	2	3	1	0	1	0	15
0	х6	3	1	2	0	0	1	4
j

Заполняем индексную строку:

1 = 01 + 02 + 02 - 3 = -3;

2 = 01 + 03 + 03 - 4 = -4;

3 = 03 + 01 + 02 - 1 = -1;

4 = 0; 5 = 0; 6 = 0;7= 03 + 015 + 04 = 0.

сi	сj	3	4	1	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	1	3	2	1	0	0	3
0	x5	2	3	1	0	1	0	15
0	х6	3	1	2	0	0	1	4
j	-3	-4	-1	0	0	0	0

В рассматриваемом случае первое опорное решение не оптимальное, поскольку имеются три отрицательные оценки 1 = - 3, 2 = - 4, 3 = - 1.

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

Такой переменной является переменная из столбца с наибольшей по абсолютной величине оценкой 2 = 3, т.е. переменная х2.

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	1	3	2	1	0	0	3
0	x5	2	3	1	0	1	0	15
0	х6	3	1	2	0	0	1	4
j	-3	-4	-1	0	0	0	0

В столбце оценочных отношений min{bi/hij} отражены отношения свободных членов к элементам из разрешающего столбца, минимальным является отношение 4/1, соответствующее строке переменной х6, следовательно, эта строка - разрешающая, а переменная х6 выводится из базисных переменных:

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	1	3	2	1	0	0	3	3/3
0	x5	2	3	1	0	1	0	15	15/3
0	х6	3	«1»	2	0	0	1	4	4/1
j	-3	-4	-1	0	0	0	0	-

На пересечении ключевой строки и ключевого столбца находится ключевой элемент «1».

Заполним симплекс-таблицу второго шага для варианта 6. Вместо переменной х6 вводим в базис переменную х2, в целевой функции ей соответствует коэффициент 3, который вносится в соответствующую клетку столбца сi.

В строке, соответствующей переменной х2 переписываем элементы из ключевой строки предыдущей таблицы, предварительно разделив их на ключевой элемент «1»:

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4
0	x5
3	х2	1/3	1	2/4	0	0	1/4	3
j								-

Заполняем столбцы для базисных переменных х2, х4, х5:

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4		0		1	0
0	x5		0		0	1
3	х2	1/3	1	2/4	0	0	1/4	3
j		0		0	0			-



Остальные клетки заполняем по правилу прямоугольника, отмечая, что ключевой элемент «1» находится в третьей строке и втором столбце предыдущей таблицы:

= ;

= ;

= ;

= ;

= ;

= ;

= ;

=

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	2/1	0	-3/1	1	0	-3/1	2
0	x5	1	0	-2	0	1	-1	3
3	х2	1/3	1	2/4	0	0	1/4	3
j		0		0	0			-

Находим оценки переменных:

1 = 0(2/1) + 01 + 4(1/3) - 3 = - 6;

3 = 0(-3/1) + 0(-2) + 4(2/4) - 1 = 7;

6 = 0(-3/1) + 0(-1) + 4(1/4) - 0 = 5;

7= 02 + 03 + 43 = 12.

сi	сj	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	2/1	0	-3/1	1	0	-3/1	2
0	x5	1	0	-2	0	1	-1	3
20	х2	1/3	1	2/4	0	0	1/4	3
j	-6	0	7	0	0	5	12	-

Находим оценки переменных:

1 = 0(2/1) + 01 + 4(-3/1) - 3 = - 6;

3 = 0(2/4) + 0(-2) + 4(-1) - 1 = 7;

6 = 0(1/3) + 0(2/4) + 3(1/4) - 0 = 5;

7= 02 + 03 + 43 = 12.

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	2/1	0	-3/1	1	0	-3/1	2
0	x5	1	0	-2	0	1	-1	3
20	х2	1/3	1	2/4	0	0	1/4	3
j	-6	0	7	0	0	5	12	-

Второе опорное решение имеет вид:

= (0, 6, 0, 2, 3, 0), = 12

Однако это решение не оптимальное, поскольку оценка 1 = - 6 <0.

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

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	2/1	0	-3/1	1	0	-3/1	2
0	x5	1	0	-2	0	1	-1	3
20	х2	1/2	1	2/4	0	0	1/4	3
j	-6	0	7	0	0	5	12	-

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

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	2/1	0	-3/1	1	0	-3/1	2	2/(2/1)
0	x5	1	0	-2	0	1	-1	3	3/1
20	х2	1/2	1	2/4	0	0	1/4	3	2/(1/2)
j	-6	0	7	0	0	5	12	-

Минимальными являются два отношения в первой строке 2/(2/1) = 1 и во второй строке 3/1 = 1, поэтому в качестве разрешающей можно выбрать любую из них. Выбираем вторую строку, соответствующую переменной х5, следовательно, переменная х5 выводится из базисных переменных. На пересечении разрешающих строки и столбца находится разрешающий элемент «1»:



сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	2/1	0	-3/1	1	0	-3/1	2	2/(2/1)
0	x5	«1»	0	-2	0	1	-1	3	3/1
20	х2	1/2	1	2/4	0	0	1/4	3	2/(1/2)
j	-6	0	7	0	0	5	12	-

Переходим к третьему шагу симплекс-метода.

Заполним симплекс-таблицу третьего шага для варианта 6. Вместо переменной х5 вводим в базис переменную х1, в целевой функции ей соответствует коэффициент 16, который вносится в соответствующую клетку столбца сi.

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	0	0	-3/1	1	-1/8	-2/8	0
16	x1	1	0	-2	0	1	-1	1
20	х2	0	1	2/4	0	1/8	3/8	3
j	0	0	4	0	3/2	4/2	14	-

Поскольку все оценки положительные j, то полученное опорное решение является оптимальным: = (4, 4, 0, 0, 0, 0), а максимальное значение целевой функции равно = 14.

сi	сj	3	4	1	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	0	0	-3/1	1	-1/8	-2/8	0
16	x1	1	0	-2	0	1	-1	1
20	х2	0	1	2/4	0	1/8	3/8	3
j	0	0	4	0	3/2	4/2	14
yi	y4	y5	y6	y1	y2	y3

Таким образом, = (0, 3/2, 7/2, 0, 0, 4), поскольку y1x4, y2x5, y3x6, y4x1, y5x2, y6x3. Значение целевой функции = 14.

Экономический смысл всех переменных, участвующих в решении

Компоненты оптимального решения ПЗЛП
План производства	Остатки ресурсов, единиц
Превышение затрат на ресурсы над ценой реализации (возможный убыток от производства продукции)	Объективно обусловленные оценки ресурсов (теневые, условные, скрытые цены ресурсов)
Компоненты оптимального решения ДЗЛП

Экономический смысл переменных:

x1*, x2*, x3* -основные переменные - оптимальный план производства;

x4*, x5, x6* - дополнительные переменные - остатки ресурсов;

y1, y2, y3 -основные переменные - скрытые цены;

y4, y5, y6 -дополнительные переменны - превышение затрат на ресурсы над ценой реализации (возможный убыток от производства продукции).

Наличие пары нулевых переменных x4* = 0 и y1 = 0 свидетельствует, что двойственная задача имеет альтернативные решения.

Анализ решения ПЗЛП

Подставим оптимальные значения переменных x* в исходную систему ограничений ПЗЛП:

1) 1х1 + 3х2 + 2х3 3

2) 2+ 31 + 20 = 15

15 = 15, следовательно, х4 = 0, ресурс Р1 используется полностью;

2) 2х1 + 3х2 + 1х3 15

13 + 24 + 30 = 15

15 = 15, следовательно, х5 = 0, ресурс Р2 используется полностью;

3) 3х1 + 1х2 + 2х3 4

14 + 34 + 10 = 4

4 = 4, следовательно, х6 = 0, ресурс Р3 используется полностью.

Анализ решения ДЗЛП

Подставим оптимальные значения переменных у*в исходную систему ограничений ПЗЛП:

1) 2у1 + 3у2 + 1у3 3

20 + 3(1/2) + 2(3/2) = 3

3 = 3, следовательно, у4 = 0, убытки от производства первого вида продукции П1, которая вошла в оптимальный план производства отсутствуют;

2) 3у1 + 1у2 + 2у3 4

30 + 4(3/2) + 4(2/1) = 4

4 = 4, следовательно, у5 = 0, убытки от производства второго вида продукции П2, которая вошла в оптимальный план производства отсутствуют;

3) 2у1 + 1у2 + 3у3 1

20 + 3(2/1) + 5(3/2) = 12

12 1 на 4, следовательно, у6 = 4, убытки от производства третьего вида продукции П3, которая не вошла в оптимальный план производства, в случае ее производства будут составлять 4 ден. ед. с каждого изделия третьего вида.

Для исследования границ изменения первого вида ресурса Р1 из последней симплекс-таблицы составляют систему неравенств для базисных переменных ПЗЛП, используя элементы из столбца свободных членов bi и столбца, соответствующего переменной у1. Коэффициенты из столбца «у1» умножают на искомое изменение b1 запаса ресурса Р1:

.

Учитывая, что b1 = 3, допустимый интервал изменения границ первого вида ресурса составит .

Аналогично, определяем допустимый интервал изменения границ второго вида ресурса Р2:

.

Учитывая, что b2 = 15, допустимый интервал изменения границ второго вида ресурса составит или .

Аналогично, определяем допустимый интервал изменения границ третьего вида ресурса Р3:

.

Учитывая, что b3 = 4, допустимый интервал изменения границ третьего вида ресурса составит или .

Для первого вида продукции П1, которая попала в план производства, из последней симплекс-таблицы составляют систему неравенств для базисных переменных ДЗЛП (они соответствуют свободным переменным ПЗЛП), используя элементы из строки j и строки, соответствующей переменной х1. Коэффициенты из строки «х1» умножают на искомое изменение с1 цены продукции П1

.

Учитывая цену первого вида продукции с1 = 3, интервал устойчивости изменения цен составит или .

Для второго вида продукции, также попавшего в план производства, система неравенств примет вид:

.

Учитывая цену второго вида продукции с2 = 4, интервал устойчивости изменения цен составит или .

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

В рассматриваемом случае: r = 1; ?br = 0,2; s = 2.

Для взаимозаменяемых ресурсов (коэффициент взаимозаменяемости >0, но отличен от бесконечности) количество ресурса ?bi вида i, необходимое для замены выбывающего количества ?bkресурса k, определяется по формуле:

.

Таким образом

Следовательно, замена первого ресурса невозможна.

В противном случае приобретение дополнительного количества ресурса нецелесообразно.

В рассматриваемом случае: ?bk = 0,2; k = 3, ck = 15.

Поскольку < 2, то приобретение дополнительного количества ресурса не целесообразно.

.

Расчет затрат осуществим по формуле

ден. ед.

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

1х1 + 3х2 +2х3 = 3

2х1 + 3х2 + 1х3 = 15

3х1 + 1х2 + 2х3 = 4

В столбцеС отражены значения переменных, при которых значение функции принимает максимальную величину:

х1 = 1, х2 = 3, х3 = 2.

На листе «Отчет по результатам» появится следующая информация, отражающая результаты расчета:

Повторяя все действия для двойственной задачи, получим следующий отчет по результатам:



Б. Двойственный симплекс-метод

1. Выражение базисных переменных ПЗЛП и ДЗЛП через свободные.

Выразим базисные переменные ПЗЛП и ДЗЛП через свободные:

2.Определение исходного решения прямой и двойственной задач и проверка его на оптимальность.

Симплексная таблица двойственного симплекс-метода для варианта 6 имеет следующий вид:



	yбаз	y4	y5	y6
yсв	Xсв xбаз	- x1	- x2	- x3	bi
y1	x4	1	3	2	3
y2	x5	2	3	1	15
y3	x6	3	1	2	4
cj		- 3	- 4	- 1	0

Решение ПЗЛП выписывается по строкам, значения базисных переменных берутся из столбца bi, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: = (0, 0, 0, 3, 15, 4), = 0.

Решение ДЗЛП выписывается по столбцам, значения базисных переменных берутся из строки cj, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: = (0, 0, 0, 3, 4, 1), = 0.

Данное решение не является оптимальным, поскольку решение не допустимое (не выполнено условие неотрицательности переменных), ему соответствуют отрицательные элементы в строке . Поэтому следует провести замену переменных в базисе.

В рассматриваемом примере в строке три отрицательных элемента

	yбаз	y4	y5	y6
yсв	Xсв xбаз	- x1	- x2	- x3	bi
y1	x4	1	3	2	3
y2	x5	2	3	1	15
y3	x6	3	1	2	4
cj		- 3	- 4	- 1	0

Можно выбрать любой из них, поэтому выбираем «3», а над ним выбираем элемент из первой строки «3». Следовательно, первая строка - разрешающая (выделена жирным шрифтом).

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

	yбаз	y4	y5	y6
yсв	xсв xбаз	- x1	- x2	- x3	bi
y1	x4	1	«3»	2	3
y2	x5	2	3	1	15
y3	x6	3	1	2	4
cj		- 3	- 4	- 1	0
					-

Заполнение нижних частей клеток для разрешающей строки и разрешающего столбца варианта 6:

	yбаз	y4	y5	y6
yсв	xсв xбаз	- x1	- x2	- x3	bi
y1	x4	1 2	«3» 1	2 2	3
y2	x5	2	3 -4	1	15
y3	x6	3	1 -4	2	4
cj		- 3	- 4 4	- 1	0

Заполнение нижних частей для остальных клеток.



клетка на пересечении второй строки и первого столбца:

1	«3»
3	2

32 12 = 4;

клетка на пересечении третьей строки и первого столбца:

1	«3»
2	2

23 24 = 2;

клетка на пересечении четвертой строки и первого столбца:

2	«3»
- 3	- 4

33 2(4) = 5;

клетка на пересечении второй строки и третьего столбца:

«3»	2
4	3

33 42 = 1;

клетка на пересечении третьей строки и третьего столбца:

«3»	2
4	5

23 42 = 3;

клетка на пересечении четвертой строки и третьего столбца:

«3»	2
- 4	- 1

13 (-4)2 = 14;

клетка на пересечении второй строки и четвертого столбца:

«3»		4
4		15

153 44 = 15;

клетка на пересечении третьей строки и четвертого столбца:

«3»		4
4		15

243 420 = 8;

клетка на пересечении четвертой строки и четвертого столбца:

«3»		4
- 3		0

03 (3) 3= 15.

Таким образом, получаем следующую таблицу

	yбаз	y4	y5	y6
yсв	xсв xбаз	- x1	- x2	- x3	bi
y1	x4	1 2	«3» 3	2 2	3 3
y2	x5	2 10	3 -3	1 1	15 15
y3	x6	3 -3	1 -1	5 7	4 -8
cj		- 3 -8	- 3 3	- 1 -14	0 40

Построение новой симплекс-таблицы.

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

	yбаз	y4	y1	y6
yсв	xсв xбаз	- x1	- x4	- x3	bi
y5	x2	1/3	3/1	2/3	3/3
y2	x5	1/3	-3/2	2/3	4/3
y3	x6	-1/3	-4/1	2/3	-6/3
cj		-8/3	-3/3	-14/1	40

Решение ПЗЛП на втором шаге двойственного симплекс-метода также выписывается по строкам: = (0, 3/3, 0, 0, 14/1, 8/3), = 40, решение ДЗЛП выписывается по столбцам: = (3/3, 0, 0, 8/3, 0, 14/1), = 40. Данное решение также не оптимальное, поскольку в строке еще остались отрицательные элементы. Необходимо продолжить поиск оптимального решения.

В строке выбираем отрицательный элемент «8/3». Над ним выбираем положительный, предпочтительнее «10/3», поскольку первая строка была выбрана на предыдущем шаге метода, следовательно, вторая строка - разрешающая (выделена жирным шрифтом):

	yбаз	y4	y1	y6
yсв	Xсв xбаз	- x1	- x4	- x3	bi
y5	x2	1/3	3/1	2/3	3/3
y2	x5	«2/3»	-4/3	1/3	15/3
y3	x6	-3/1	-1/3	2/3	-4/3
cj		-8/3	3/3	-14/3	40
					-

Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки

Разрешающий столбец - первый, поскольку максимальное отношение соответствует ему.Разрешающий элемент «2/3» находится на пересечении разрешающей строки и разрешающего столбца.Заполнение нижних частей клеток осуществляется аналогично рассмотренному выше. Получаем следующую таблицу:

	yбаз	y4	y1	y6
yсв	Xсв xбаз	- x1	- x4	- x3	bi
y5	x2	3/1 -2/3	1/3 2	2/3 2	3/3 6/3
y2	x5	«2/3» 1	-3/4 -4/3	1/3 1/3	15/3 15/3
y3	x6	-3/2 2/3	-1/3 -4/3	2/1 4	-8/3 0
cj		-8/3 8/3	3/3 16/3	-14/3 44/3	40/3 144/3

Переходим к следующей симплекс-таблице. При этом во вторую строку включается пара переменных х1, у4, соответствующих разрешающему столбцу, а в первый столбец вводится пара переменных х5, у2, соответствующая разрешающей строке.

Клетки следующей таблицы заполняются элементами, полученными в результате деления соответствующих элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «3/2». Поскольку в нижних частях клеток таблицы все элементы положительные и разрешающий элемент также положительный, то в следующей таблице будет получено оптимальное решение и нет необходимости делить на две части клетки в последней таблице. Однако следует отметить, что в третьей строке в столбце bi есть нулевой элемент. Это свидетельствует о том, что двойственная задача имеет альтернативные решения:

	yбаз	y2	y1	y6
yсв	xсв xбаз	- x5	- x4	- x3	bi
y5	x2	1/3	3/5	3/2	4
y4	x1	3/8	2/5	1/8	4
y3	x6	1/2	8/5	4/3	0
cj		4/3	16/5	14/3	144

Оптимальное решение ПЗЛП: = (4, 4, 0, 0, 0, 0), = 144, оптимальное решение ДЗЛП: = (16/5, 4/3, 0, 0, 14/3), = 144.

Данное решение аналогично решению, полученному в соответствии с методом одновременного решения пары взаимодвойственных задач для ПЗЛП и совпадает с решением ДЗЛП в отношении значения целевой функции. Однако поскольку ДЗЛП имеет альтернативные решения, то полученное в результате расчета решение является альтернативным по отношению к полученному первым методом.



Список использованных источников

1. Васин А. А. Исследование операций : учеб.пособие для вузов / А.А. Васин, П.С. Краснощеков, В. В. Морозов.-- М. : Академия, 2008.-- 464 с.

2. Вентцель Е.С. Исследование операций : задачи, принципы, методология : учеб.пособие / Е.С. Вентцель.-- 5-е изд., стер. М. :Высш. шк., 2010 .-- 191 с.

3. Горбунова Р.И. Экономико-математические методы и модели : учеб.пособие / Р.И. Горбунова [и др.]; под ред. С.И. Макарова.-- М. : КНОРУС, 2007.-- 232с.

4. Исследование операций в экономике : учеб.пособие для вузов / Н.Ш. Кремер [и др.] ; под ред. Н. Ш. Кремера.-- 2-е изд., перераб. и доп.-- М. : Юрайт, 2010.-- 431 с.

5. Солодовников А.С. Математика в экономике : учебник для вузов. Ч.1 / А.С. Солодовников [и др.] .-- 2-е изд., перераб. и доп. -- М. : Финансы и статистика, 2007 .-- 384с.

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