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

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

Представим расчет каждого элемента в виде таблицы:

 

B	x 1	x 2	x 3	x 4	x 5	x 6
70 : 22/3	0 : 22/3	1/3 : 22/3	22/3 : 22/3	1 : 22/3	0 : 22/3	-2/3 : 22/3
140-(70 • 41/3):22/3	0-(0 • 41/3):22/3	22/3-(1/3 • 41/3):22/3	41/3-(22/3 • 41/3):22/3	0-(1 • 41/3):22/3	1-(0 • 41/3):22/3	-1/3-(-2/3 • 41/3):22/3
40-(70 • 2/3):22/3	1-(0 • 2/3):22/3	11/3-(1/3 • 2/3):22/3	2/3-(22/3 • 2/3):22/3	0-(1 • 2/3):22/3	0-(0 • 2/3):22/3	1/3-(-2/3 • 2/3):22/3
3200-(70 • -62/3):22/3	0-(0 • -62/3):22/3	362/3-(1/3 • -62/3):22/3	-62/3-(22/3 • -62/3):22/3	0-(1 • -62/3):22/3	0-(0 • -62/3):22/3	262/3-(-2/3 • -62/3):22/3

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	261/4	0	1/8	1	3/8	0	-1/4
x5	261/4	0	21/8	0	-15/8	1	3/4
x1	221/2	1	11/4	0	-1/4	0	1/2
F(X2)	3375	0	371/2	0	21/2	0	25

 

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

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

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

 

Базис	B	x1	x2	x3	x4	x5	x6
x3	261/4	0	1/8	1	3/8	0	-1/4
x5	261/4	0	21/8	0	-15/8	1	3/4
x1	221/2	1	11/4	0	-1/4	0	1/2
F(X3)	3375	0	371/2	0	21/2	0	25

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

x3 = 261/4

x1 = 221/2

F(X)усл. = 60•261/4 + 80•221/2 = 3375

Конечная функция будет иметь вид:

 

Ответ: 19075

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ситуация №2

 

Построить математическую модель задачи. Составить задачу, двойственную к исходной.

 

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

 

Ресурсы	Объективно обусловленные оценки ресурсов	Затраты ресурсов на 1 изделие
		А	Б	В
Труд	40	6	4	2
Сырьё	20	2	1	3
Оборудование	20	3	1	2
Прибыль на 1 изделие		80	70	45

 

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

Определим максимальное значение целевой функции F(X) = 80x1 + 70x2 + 45x3 при следующих условиях-ограничений.

6x1 + 4x2 + 2x3≤40

2x1 + x2 + 3x3≤20

3x1 + x2 + 2x3≤20

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. 

6x1 + 4x2 + 2x3 + 1x4 + 0x5 + 0x6 = 40

2x1 + 1x2 + 3x3 + 0x4 + 1x5 + 0x6 = 20

3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 20

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A = | 6;4;2;1;0;0;2;1;3;0;1;0;3;1;2;0;0;1

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

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

Решим систему уравнений относительно базисных переменных:

x4, x5, x6,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,40,20,20)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x4	40	6	4	2	1	0	0
x5	20	2	1	3	0	1	0
x6	20	3	1	2	0	0	1
F(X0)	0	-80	-70	-45	0	0	0

 

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (40 : 6 , 20 : 2 , 20 : 3 ) = 62/3

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	40	6	4	2	1	0	0	62/3
x5	20	2	1	3	0	1	0	10
x6	20	3	1	2	0	0	1	62/3
F(X1)	0	-80	-70	-45	0	0	0	0

 

Поскольку в последнем столбце присутствует несколько минимальных элементов 62/3, то номер строки выбираем по правилу Креко.

Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=62/3, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.

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

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

Вместо переменной x6 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=6

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

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

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

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

 

B	x 1	x 2	x 3	x 4	x 5	x 6
40-(20 • 6):3	6-(3 • 6):3	4-(1 • 6):3	2-(2 • 6):3	1-(0 • 6):3	0-(0 • 6):3	0-(1 • 6):3
20-(20 • 2):3	2-(3 • 2):3	1-(1 • 2):3	3-(2 • 2):3	0-(0 • 2):3	1-(0 • 2):3	0-(1 • 2):3
20 : 3	3 : 3	1 : 3	2 : 3	0 : 3	0 : 3	1 : 3
0-(20 • -80):3	-80-(3 • -80):3	-70-(1 • -80):3	-45-(2 • -80):3	0-(0 • -80):3	0-(0 • -80):3	0-(1 • -80):3

 

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	0	0	2	-2	1	0	-2
x5	62/3	0	1/3	12/3	0	1	-2/3
x1	62/3	1	1/3	2/3	0	0	1/3
F(X1)	5331/3	0	-431/3	81/3	0	0	262/3