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

Вариант 3

Ситуация №1

 

Построить математическую модель задачи оптимизации производства.

Фабрика выпускает 3 вида тканей, причём суточное плановое задание составляет не менее 90м тканей 1-го вида, 70м- 2, 60м- 3. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья и 790 единиц электроэнергии, расход которых на 1м представлен в таблице. Цена за 1м равна 80 у.е.- 1 вид, 70-2й, 60-3й. Определить сколько метров ткани каждого вида следует выпускать, чтобы общая стоимость выпускаемой продукции была максимальной.

 

Ресурсы	1	2	3
Оборудование	2	3	4
Сырьё	1	4	5
Электроэнергия	3	4	2

 

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

 

 

Учитывая минимальный объём производства преобразуем условие задачи.

 

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

 

Далее решим задачу симплекс методом.

 

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

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

2x1 + 3x2 + 4x3≤150

x1 + 4x2 + 5x3≤180

3x1 + 4x2 + 2x3≤120

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

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

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

1x1 + 4x2 + 5x3 + 0x4 + 1x5 + 0x6 = 180

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

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

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

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

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

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

x4, x5, x6,

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

X1 = (0,0,0,150,180,120)

 

 

 

 

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

 

Базис	B	x1	x2	x3	x4	x5	x6
x4	150	2	3	4	1	0	0
x5	180	1	4	5	0	1	0
x6	120	3	4	2	0	0	1
F(X0)	0	-80	-70	-60	0	0	0

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

Итерация №0.

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

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

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

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

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

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

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

min (150 : 2 , 180 : 1 , 120 : 3 ) = 40

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	150	2	3	4	1	0	0	75
x5	180	1	4	5	0	1	0	180
x6	120	3	4	2	0	0	1	40
F(X1)	0	-80	-70	-60	0	0	0	0

 

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

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

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

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6
150-(120 • 2):3	2-(3 • 2):3	3-(4 • 2):3	4-(2 • 2):3	1-(0 • 2):3	0-(0 • 2):3	0-(1 • 2):3
180-(120 • 1):3	1-(3 • 1):3	4-(4 • 1):3	5-(2 • 1):3	0-(0 • 1):3	1-(0 • 1):3	0-(1 • 1):3
120 : 3	3 : 3	4 : 3	2 : 3	0 : 3	0 : 3	1 : 3
0-(120 • -80):3	-80-(3 • -80):3	-70-(4 • -80):3	-60-(2 • -80):3	0-(0 • -80):3	0-(0 • -80):3	0-(1 • -80):3

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	70	0	1/3	22/3	1	0	-2/3
x5	140	0	22/3	41/3	0	1	-1/3
x1	40	1	11/3	2/3	0	0	1/3
F(X1)	3200	0	362/3	-62/3	0	0	262/3

 

Итерация №1.

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

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

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

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

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

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

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

min (70 : 22/3 , 140 : 41/3 , 40 : 2/3 ) = 261/4

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	70	0	1/3	22/3	1	0	-2/3	261/4
x5	140	0	22/3	41/3	0	1	-1/3	324/13
x1	40	1	11/3	2/3	0	0	1/3	60
F(X2)	3200	0	362/3	-62/3	0	0	262/3	0

 

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

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

Вместо переменной x4 в план 2 войдет переменная x3.

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

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

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

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