Математическое моделирование производства
Построение математической модели задачи оптимизации производства. Уменьшение ресурсов на обязательный объём, который необходимо произвести. Решение прямой задачи линейного программирования симплексным методом с использованием симплексной таблицы.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 09.06.2015 |
| Размер файла | 1,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Ситуация 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) этой системы уравнений имеет вид:
Базисные переменные -- это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: 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 |
Переходим к основному алгоритму симплекс-метода.
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. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
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.
Все остальные элементы нового плана 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) этой системы уравнений имеет вид:
Базисные переменные -- это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: 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 |
Переходим к основному алгоритму симплекс-метода.
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 |
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (0 : 2, 62/3 : 1/3, 62/3 : 1/3) = 0
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
x4 |
0 |
0 |
2 |
-2 |
1 |
0 |
-2 |
0 |
|
|
x5 |
62/3 |
0 |
1/3 |
12/3 |
0 |
1 |
-2/3 |
20 |
|
|
x1 |
62/3 |
1 |
1/3 |
2/3 |
0 |
0 |
1/3 |
20 |
|
|
F(X2) |
5331/3 |
0 |
-431/3 |
81/3 |
0 |
0 |
262/3 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=2.
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
Расчет каждого элемента
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
|
0 : 2 |
0 : 2 |
2 : 2 |
-2 : 2 |
1 : 2 |
0 : 2 |
-2 : 2 |
|
|
62/3-(0 * 1/3):2 |
0-(0 * 1/3):2 |
1/3-(2 * 1/3):2 |
12/3-(-2 * 1/3):2 |
0-(1 * 1/3):2 |
1-(0 * 1/3):2 |
-2/3-(-2 * 1/3):2 |
|
|
62/3-(0 * 1/3):2 |
1-(0 * 1/3):2 |
1/3-(2 * 1/3):2 |
2/3-(-2 * 1/3):2 |
0-(1 * 1/3):2 |
0-(0 * 1/3):2 |
1/3-(-2 * 1/3):2 |
|
|
5331/3-(0 * -431/3):2 |
0-(0 * -431/3):2 |
-431/3-(2 * -431/3):2 |
81/3-(-2 * -431/3):2 |
0-(1 * -431/3):2 |
0-(0 * -431/3):2 |
262/3-(-2 * -431/3):2 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x2 |
0 |
0 |
1 |
-1 |
1/2 |
0 |
-1 |
|
|
x5 |
62/3 |
0 |
0 |
2 |
-1/6 |
1 |
-1/3 |
|
|
x1 |
62/3 |
1 |
0 |
1 |
-1/6 |
0 |
2/3 |
|
|
F(X2) |
5331/3 |
0 |
0 |
-35 |
212/3 |
0 |
-162/3 |
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (-, 62/3 : 2, 62/3 : 1) = 31/3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
x2 |
0 |
0 |
1 |
-1 |
1/2 |
0 |
-1 |
- |
|
|
x5 |
62/3 |
0 |
0 |
2 |
-1/6 |
1 |
-1/3 |
31/3 |
|
|
x1 |
62/3 |
1 |
0 |
1 |
-1/6 |
0 |
2/3 |
62/3 |
|
|
F(X3) |
5331/3 |
0 |
0 |
-35 |
212/3 |
0 |
-162/3 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 3 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 3, получена в результате деления всех элементов строки x5 плана 2 на разрешающий элемент РЭ=2.
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x3 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
Расчет каждого элемента
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
|
0-(62/3 * -1):2 |
0-(0 * -1):2 |
1-(0 * -1):2 |
-1-(2 * -1):2 |
1/2-(-1/6 * -1):2 |
0-(1 * -1):2 |
-1-(-1/3 * -1):2 |
|
|
62/3 : 2 |
0 : 2 |
0 : 2 |
2 : 2 |
-1/6 : 2 |
1 : 2 |
-1/3 : 2 |
|
|
62/3-(62/3 * 1):2 |
1-(0 * 1):2 |
0-(0 * 1):2 |
1-(2 * 1):2 |
-1/6-(-1/6 * 1):2 |
0-(1 * 1):2 |
2/3-(-1/3 * 1):2 |
|
|
5331/3-(62/3 * -35):2 |
0-(0 * -35):2 |
0-(0 * -35):2 |
-35-(2 * -35):2 |
212/3-(-1/6 * -35):2 |
0-(1 * -35):2 |
-162/3-(-1/3 * -35):2 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x2 |
31/3 |
0 |
1 |
0 |
5/12 |
1/2 |
-11/6 |
|
|
x3 |
31/3 |
0 |
0 |
1 |
-1/12 |
1/2 |
-1/6 |
|
|
x1 |
31/3 |
1 |
0 |
0 |
-1/12 |
-1/2 |
5/6 |
|
|
F(X3) |
650 |
0 |
0 |
0 |
183/4 |
171/2 |
-221/2 |
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai6 и из них выберем наименьшее: min (-, -, 31/3 : 5/6) = 4
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (5/6) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
x2 |
31/3 |
0 |
1 |
0 |
5/12 |
1/2 |
-11/6 |
- |
|
|
x3 |
31/3 |
0 |
0 |
1 |
-1/12 |
1/2 |
-1/6 |
- |
|
|
x1 |
31/3 |
1 |
0 |
0 |
-1/12 |
-1/2 |
5/6 |
4 |
|
|
F(X4) |
650 |
0 |
0 |
0 |
183/4 |
171/2 |
-221/2 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x1 в план 4 войдет переменная x6.
Строка, соответствующая переменной x6 в плане 4, получена в результате деления всех элементов строки x1 плана 3 на разрешающий элемент РЭ=5/6.
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x6 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x6 и столбец x6.
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
Расчет каждого элемента
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
|
31/3-(31/3 * -11/6):5/6 |
0-(1 * -11/6):5/6 |
1-(0 * -11/6):5/6 |
0-(0 * -11/6):5/6 |
5/12-(-1/12 * -11/6):5/6 |
1/2-(-1/2 * -11/6):5/6 |
-11/6-(5/6 * -11/6):5/6 |
|
|
31/3-(31/3 * -1/6):5/6 |
0-(1 * -1/6):5/6 |
0-(0 * -1/6):5/6 |
1-(0 * -1/6):5/6 |
-1/12-(-1/12 * -1/6):5/6 |
1/2-(-1/2 * -1/6):5/6 |
-1/6-(5/6 * -1/6):5/6 |
|
|
31/3 : 5/6 |
1 : 5/6 |
0 : 5/6 |
0 : 5/6 |
-1/12 : 5/6 |
-1/2 : 5/6 |
5/6 : 5/6 |
|
|
650-(31/3 * -221/2):5/6 |
0-(1 * -221/2):5/6 |
0-(0 * -221/2):5/6 |
0-(0 * -221/2):5/6 |
183/4-(-1/12 * -221/2):5/6 |
171/2-(-1/2 * -221/2):5/6 |
-221/2-(5/6 * -221/2):5/6 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x2 |
8 |
12/5 |
1 |
0 |
3/10 |
-1/5 |
0 |
|
|
x3 |
4 |
1/5 |
0 |
1 |
-1/10 |
2/5 |
0 |
|
|
x6 |
4 |
11/5 |
0 |
0 |
-1/10 |
-3/5 |
1 |
|
|
F(X4) |
740 |
27 |
0 |
0 |
161/2 |
4 |
0 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x2 |
8 |
12/5 |
1 |
0 |
3/10 |
-1/5 |
0 |
|
|
x3 |
4 |
1/5 |
0 |
1 |
-1/10 |
2/5 |
0 |
|
|
x6 |
4 |
11/5 |
0 |
0 |
-1/10 |
-3/5 |
1 |
|
|
F(X5) |
740 |
27 |
0 |
0 |
161/2 |
4 |
0 |
Оптимальный план можно записать так:
x2 = 8
x3 = 4
F(X) = 70*8 + 45*4 = 740
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 4.
Значение 27> 0 в столбце x1 означает, что использование x1 - не выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 0 в столбце x3 означает, что использование x3 - выгодно.
Значение 161/2 в столбце x4 означает, что теневая цена (двойственная оценка) равна 161/2.
Значение 4 в столбце x5 означает, что теневая цена (двойственная оценка) равна 4.
Составим двойственную задачу к прямой задаче.
6y1 + 2y2 + 3y3?80
4y1 + y2 + y3?70
2y1 + 3y2 + 2y3?45
40y1 + 20y2 + 20y3 > min
y1 ? 0
y2 ? 0
y3 ? 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 161/2
y2 = 4
y3 = 0
Z(Y) = 40*161/2+20*4+20*0 = 740
Ситуация 3
Решить транспортную задачу с использованием вычислительных средств Excel.
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-й центр распределения Сij приведена в таблице, где под строкой понимается пункт производства, а под столбцом - пункт распределения. Кроме того, в этой таблице в i-й строке указан объем производства в i- м пункте производства, а в j-м столбце указан спрос в j-м центре распределения. Необходимо составить план перевозок по доставке требуемой продукции в пункты распределения, минимизирующий суммарные транспортные расходы.
|
1 |
2 |
3 |
4 |
Потребность |
||
|
A |
6 |
3 |
4 |
5 |
20 |
|
|
B |
5 |
2 |
3 |
3 |
70 |
|
|
C |
3 |
4 |
2 |
4 |
50 |
|
|
D |
5 |
6 |
2 |
7 |
30 |
|
|
Объём производства |
15 |
30 |
80 |
20 |
Первоначально перенесём исходные данные в excel. Добавив дополнительный центр распределения, так как задача несбалансированная, объём производства неравен распределению. Фиктивный центр под номером 5.
Далее введём вспомогательную таблицу и пропишем формулы.
Так же введём целевую функцию = СУММ(D22:H25)
И решим задачу через поиск решения, введя все необходимые ограничения
Окончательное решение примет вид.
Ответ: минимальные расходы составляют 340 у.е.
Ситуация 4
Решить задачу о назначениях преподавателей на проведение занятий в соответствии с заданной таблицей.
|
Преподаватели |
Стоимость выполнения |
||||
|
Виды занятий |
|||||
|
1 |
2 |
3 |
4 |
||
|
1 |
860 |
620 |
200 |
500 |
|
|
2 |
510 |
230 |
910 |
860 |
|
|
3 |
300 |
800 |
120 |
900 |
|
|
4 |
100 |
410 |
210 |
330 |
|
|
5 |
300 |
720 |
990 |
500 |
Требуется так распределить преподавателей по занятиям, чтобы минимизировать суммарные расходы на оплату за выполнение работ. Заметим, что данная модель не сбалансирована, поскольку преподавателей больше, чем видов занятий. Следовательно, необходимо ввести фиктивный вид занятий.
Внесём исходные данные в EXCEL и решим задачу через поиск решение.
Первоначально заполним таблицу и введём фиктивный вид занятий. Затем составим вспомогательную таблицу и введём целевую функцию.
ЦФ=СУММПРОИЗВ(B5:F9;B15:F19)
Также введём дополнительные ограничения, которые необходимы для того, чтобы 1 преподаватель вёл только один вид занятий.
$G$15:$G$19=$H$15:$H$19
$B$20:$F$20=$B$21:$F$21
Так же введём еще одно дополнительное условие, которое необходимо для того, что поиск решений ввёлся только по значениям 1 или 0, так как в задаче поставлено условие, что преподаватель либо ведёт занятие, либо нет.
$B$15:$F$19= бинарное
Таким образом, исходя из полученного решения:
1 преподаватель ведёт 4 занятие
2 преподаватель ведёт 2 занятие
3 преподаватель ведёт 3 занятие
4 преподаватель ведёт 1 занятие
5 преподаватель ведёт фиктивное занятие
И минимальные расходы составят 950 у.е.
Ответ: 950 у.е.
Размещено на Allbest.ru
Подобные документы
Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Пример решения задачи симплексным методом, приведение ее к каноническому виду. Составление экономико-математической модели задачи. Расчеты оптимального объёма производства предприятия при достижении максимальной прибыли. Построение симплексной таблицы.
практическая работа [58,0 K], добавлен 08.01.2011Построение одноиндексной математической модели задачи линейного программирования, ее решение графическим методом. Разработка путей оптимизации сетевой модели по критерию "минимум исполнителей". Решение задачи управления запасами на производстве.
контрольная работа [80,8 K], добавлен 13.12.2010Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Построение модели планирования производства. Использование инструментального средства "Поиск решения" для решения задачи линейного программирования. Решение оптимальной задачи, с использованием методов математического анализа и возможностей MathCad.
лабораторная работа [517,1 K], добавлен 05.02.2014Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа [613,3 K], добавлен 18.02.2014Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.
презентация [1,1 M], добавлен 02.12.2014Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
задача [579,8 K], добавлен 11.07.2010Решение графическим методом задачи линейного программирования с двумя неизвестными. Решение транспортной задачи методом северо-западного угла и методом минимальной стоимости. Системы массового обслуживания. Стохастическая модель управления запасами.
контрольная работа [458,1 K], добавлен 16.03.2012