Переход на пункт 3.

Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Тульский Государственный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

МУ_ККР_1часть.doc

Скачиваний:

Добавлен:

21.08.2019

Размер:

1.89 Mб

Скачать

☆

<<< < Предыдущая 12 / 32 3 > Следующая >>>

Построение новой симплекс-таблицы
1. Меняем местами переменные из разрешающей строки и разрешающего столбца.
2. Элементы из нижних клеток предыдущей симплекс-таблицы делим на верхний разрешающий элемент и записываем на соответствующие места в верхние клетки новой симплекс-таблицы.
Если в новой таблице в строке f₀(x) есть отрицательные элементы то переходим на пункт 1. (Нецелесообразно выбирать за разрешающую строку – те же строки, что и на предыдущих шагах).
Нахождение допустимого (одновременно оптимального) решения прямой задачи.
1. Если в новой таблице в строке f₀(x) нет отрицательных элементов, а в столбце свободных членов остались отрицательные элементы, то строка с отрицательным значением b_iвыбирается за разрешающую.
2. Переход на пункт 2.
Если в новой симплекс-таблице в строке f₀(x) и столбце b_iнет отрицательных элементов, то найденное решение является оптимальным.
Если в строке f₀(x) есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.
1. Столбец с нулевым элементом в строке f₀(x) выбирается за разрешающий.
2. Находится неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца.
3. Из полученных отношений выбирается минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден.
4. Переход на пункт 3.
Если в столбце b_i есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.
1. Строка с нулевым элементом в столбце b_iвыбирается за разрешающую.
2. Переход на пункт 2.
Конец.

1.3 Пример исследования задачи распределения ресурсов

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

Обозначения	Номер варианта
n	5
b₁	3
b₂	5
b₃	4
a₁₁	1
a₁₂	3
a₁₃	2
a₁₄	3
a₁₅	6
a₂₁	2
a₂₂	3
a₂₃	1
a₂₄	6
a₂₅	0
a₃₁	3
a₃₂	1
a₃₃	2
a₃₄	6
a₃₅	4
c₁	3
c₂	4
c₃	1
c₄	3
c₅	2
r	1
∆b_r	0,05
s	3
k	3
∆b_k	0,02
c_k	1,5
ℓ	6
a₁_ℓ	2
a_2ℓ	1
a_3ℓ	2
c_ℓ	45

Представим исходные данные таблицей 0.

Таблица 0 - Исходные данные

Норма затрат Ресурсы		Виды изделий					Кол-во ресурсов	Скрытые цены ресурсов
Норма затрат Ресурсы							Кол-во ресурсов	y_i	y_i*
		1	3	2	3	6	3		9/8
		2	3	1	6	0	5		0
		3	1	2	6	4	4		5/8
Цена единицы изделия		3	4	1	3	2	maxf₀(х)	ming₀(у)
План выпуска	x_j
План выпуска	x_j^*	9/8	5/8	0	0	0

3. Переход к канонической форме ПЗЛП с помощью введения дополнительных переменных x₆, x₇, x₈.

Переход к канонической форме ДЗЛП с помощью введения дополнительных переменных y₄, y₅, y₆, y₇, y₈.

Выражение базисных переменныx

Таблица 1 – Шаг 1 симплекс-метода

-6

-4

-3

-16

-4

-18

-1

-2

-3

-12

-2

Таблица 2 – Шаг 2 симплекс-метода

1/6

-1/2

1/3

-1/3

-3/2

1/6

1/2

-7/6

7/3

-1

-3

2/3

-2/3

-4/3

-8/3

-2

-3

-2

-1/3

1/3

-2

1/3

8/3

Таблица 3 – Шаг 3 симплекс-метода

-1/2

2/3

-1/2

-2/3

-1/3

1/3

-3/2

1/6

-1/3

-7/6

1/3

-7/3

-1

-4

2/3

-2

-3

-2/3

-2/3-

-2/3

-4/3

-2

7/3

1/3

-1/3

1/3

8/3

-4/3

Таблица 4 – Шаг 4 симплекс-метода

-1

-3/4

-1/4

-1/2

-1/4

-3/2

1/2

-1/2

-1

7/2

-3/2

3/2

-1

-3/2

-2

9/2 -

-3

-3/2

0 --6

-2/3-1-1

-5

-3/2

3/2

-7/2

7/2

1/2

-1/2

-2

Таблица 5 – Шаг 5 симплекс-метода

3/4

1/4

3/2

1/2

-7/2

7/2

3/2

-3/2

-1/4

-6

3/4

-1

-3

5/4

-2

7/4

-1/2

3/2

1-/3

- 1-1/4

7/4

-3/2

3/2

-7/2

-9/4

1/2

3/4

9/4

3/4

Таблица 6 – Шаг 6 симплекс-метода

4/3

1/3

-1/3

1/3

2/3

4/3

14/3

8/3

-1/3

4/3

5/3

-8/3

-18

7/3-

-7/3

-2/3

-1

-1/3-

2-4

7/3

58/3

-3

1/2

3/4

5/3

47/3

Таблица 7 – Шаг 7 симплекс-метода



3/4	-1/8	3/8	15/8	1/2	9/8
7/4	3/8	-1/8	3/8	1/2	5/8
-27/4	-7/8	-3/8	9/8	-3/2	7/8
29/4	9/8	5/8	33/8	5/2	47/8

Таблица 8 – Экономический смысл оптимальных решений ПЗЛП и ДЗЛП

Компоненты оптимального решения

П₁

П₂

П₃

П₄

П₅

Излишки ресурсов

ПЗЛП

Х1*

Х2*

Х3*

Х4*

Х5*

Х6*

Х7*

Х8*

9/8

5/8

7/8

ДЗЛП

5/2

33/8

29/4

9/8

5/8

У4*

У5*

У6*

У7*

У8*

У1*

У2*

У3*

Превышение затрат на производство единицы продкции в скрытых ценах ресурсов над ценой

Скрытые цены ресурсов

Компоненты оптимального решения

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

x₁^*, x₂^*, x₃^* , x₄^*,x₅^*-основные переменные - оптимальный план производства,

x₆^*, x₇^*- дополнительные переменные - изменение ресурсов,

y₁,y₂,y₃-основные переменные - скрытые цены.

y₄,y₅,y₆y₇,y₈-дополнительные переменны – избытки от производства (издержки, не вошедшие в план производства).

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

Подставим оптимальные значения переменных x^* и y_* в исходные системы ограничений неравенств ПЗЛП и ДЗЛП соответственно.

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

Изделия П1 и П2 вошли в оптимальный план, убытки от их производства равны 0.

От производства изделия П3 организация потерпит убыток 2,5 , от производства изделия П4 убыток составит 4,125, от производства изделия П5 организация потерпит убыток в размере 7,25. Эти изделия не вошли в оптимальный план производства.

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

Ресурсы Р₁ и Р₃ используются полностью. Избыток ресурса Р₂ равен 0,875.

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

Таблица 9 – Анализ изменения ресурса Р₁

			Комментарии
			Комментарии
-1/8	9/8-1/8	9/8-1/8	Выпуск продукции уменьшится на 1/8 x₁^*=1,25
3/8	5/8+3/8	5/8+3/8	Выпуск продукции увеличится на 3/8 x₂^*=1
-7/8	7/8-7/8	7/8-7/8	Избыток ресурса уменьшится на 7/8 x
9/8	47/8	47/8+9/8	Доход возрастет на 9/8 f₀(x*)=7

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

Таблица 10 – Анализ изменения ресурса Р₃

			Комментарии
			Комментарии
3/8	9/8+3/8	9/8+3/8	Выпуск продукции увеличился на 3/8
-1/8	5/8-1/8	5/8-1/8	Выпуск продукции уменьшился на 1/8
-3/8	7/8-3/8	7/8-3/8	Избыток ресурса уменьшится на 3/8
5/8	47/8	52/8	Доход возрастет на 5/8

6. Избыток ресурса Р₂ x₇*=7/8 определяется значением соответствующей дополнительной переменной. Фактическое использование равно:

5-0,875=4,125 единиц.

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