Контрольная работа по "Методам оптимальных решений"

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	20	5	0	1	-1	0	1	4
x2	22/3	1/3	1	0	-1/3	0	1/3	8
x5	0	-2	0	0	1	1	-1	-
F(X2)	-102/3	-111/3	0	0	11/3	0	-11/3+M	0

 

4. Пересчет симплекс-таблицы.

Формируем следующую  часть симплексной таблицы.

Вместо переменной x₃ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₃ плана 1 на разрешающий элемент РЭ=5

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках  столбца x₁ плана 2 записываем нули.

Таким образом, в новом  плане 2 заполнены строка x₁ и столбец x₁.

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

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x1	4	1	0	1/5	-1/5	0	1/5
x2	11/3	0	1	-1/15	-4/15	0	4/15
x5	8	0	0	2/5	3/5	1	-3/5
F(X2)	342/3	0	0	24/15	-14/15	0	14/15+M

 

1. Проверка критерия  оптимальности.

Текущий опорный план неоптимален, так как в индексной  строке находятся отрицательные  коэффициенты.

2. Определение новой  базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₄, так как это наибольший коэффициент по модулю.

3. Определение новой свободной  переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i4

и из них выберем наименьшее:

min (- , - , 8 : ³/₅ ) = 13¹/₃

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент  равен (³/₅) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x1	4	1	0	1/5	-1/5	0	1/5	-
x2	11/3	0	1	-1/15	-4/15	0	4/15	-
x5	8	0	0	2/5	3/5	1	-3/5	131/3
F(X3)	342/3	0	0	24/15	-14/15	0	14/15+M	0

 

4. Пересчет симплекс-таблицы.

Формируем следующую  часть симплексной таблицы.

Вместо переменной x₅ в план 3 войдет переменная x₄.

Строка, соответствующая  переменной x₄ в плане 3, получена в результате деления всех элементов строки x₅ плана 2 на разрешающий элемент РЭ=³/₅

На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках  столбца x₄ плана 3 записываем нули.

Таким образом, в новом  плане 3 заполнены строка x₄ и столбец x₄.

Все остальные элементы нового плана 3, включая элементы индексной  строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x1	62/3	1	0	1/3	0	1/3	0
x2	48/9	0	1	1/9	0	4/9	0
x4	131/3	0	0	2/3	1	12/3	-1
F(X3)	471/9	0	0	28/9	0	15/9	M

 

1. Проверка критерия  оптимальности.

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

Окончательный вариант  симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x1	62/3	1	0	1/3	0	1/3	0
x2	48/9	0	1	1/9	0	4/9	0
x4	131/3	0	0	2/3	1	12/3	-1
F(X4)	471/9	0	0	28/9	0	15/9	M

 

Так как в оптимальном  решении отсутствуют искусственные  переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно  записать так:

x₁ = 6²/₃

x₂ = 4⁸/₉

F(X) = 10•6²/₃ -4•4⁸/₉ = 47¹/₉

Ответ: F(X) = 10•6²/₃ -4•4⁸/₉ = 47¹/₉, x₁ = 6²/₃, x₂ = 4⁸/₉.

Задача № 2.

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

 

продукция сырьё	I	II	III
1 2 3	5 1 4	2 6 5	3 8 10

 

Запасы сырья каждого  вида на планируемый период составляют 200, 320 и 400 единиц соответственно. План выпуска изделий каждого вида за этот период составляет 10, 20, 15 единиц. Сколько единиц изделий каждого вида необходимо выпускать для получения максимальной прибыли и выполнения плана, если прибыль, получаемая от реализации одного изделия каждого вида, составляет 6 у.е., 12 у.е. и 15 у.е.

Решение:

Математическая модель задачи:

Пусть х₁ – количество продукции первого вида

 х₂ – количество продукции второго вида

 х₃ – количество продукции третьего вида

Запас сырья трех типов определяется следующей системой неравенств, учитывающий  расход сырья на каждый вид продукции:

Необходимо максимизировать целевую  функцию:

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

Определим максимальное значение целевой  функции F(X) = 6x₁ + 12x₂ + 15x₃ при следующих условиях-ограничений.

5x₁ + 2x₂ + 3x₃≤200

x₁ + 6x₂ + 8x₃≤320

4x₁ + 5x₂ + 10x₃≤400

x₁≥10

x₂≥20

x₃≥15

Для построения первого опорного плана  систему неравенств приведем к системе  уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₄. В 2-м неравенстве смысла (≤) вводим базисную переменную x₅. В 3-м неравенстве смысла (≤) вводим базисную переменную x₆. В 4-м неравенстве смысла (≥) вводим базисную переменную x₇ со знаком минус. В 5-м неравенстве смысла (≥) вводим базисную переменную x₈ со знаком минус. В 6-м неравенстве смысла (≥) вводим базисную переменную x₉ со знаком минус.

5x₁ + 2x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 200

1x₁ + 6x₂ + 8x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 320

4x₁ + 5x₂ + 10x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ = 400

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆-1x₇ + 0x₈ + 0x₉ = 10

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 0x₉ = 20

0x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈-1x₉ = 15

Введем искусственные переменные x: в 4-м равенстве вводим переменную x₁₀; в 5-м равенстве вводим переменную x₁₁; в 6-м равенстве вводим переменную x₁₂;

5x₁ + 2x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ = 200

1x₁ + 6x₂ + 8x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ = 320

4x₁ + 5x₂ + 10x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ + 0x₁₂ = 400

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆-1x₇ + 0x₈ + 0x₉ + 1x₁₀ + 0x₁₁ + 0x₁₂ = 10

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 0x₉ + 0x₁₀ + 1x₁₁ + 0x₁₂ = 20

0x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈-1x₉ + 0x₁₀ + 0x₁₁ + 1x₁₂ = 15

Для постановки задачи на максимум целевую функцию запишем  так:

F(X) = 6x₁+12x₂+15x₃ - Mx₁₀ - Mx₁₁ - Mx₁₂ → max

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

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

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