Решение исходной задачи симплексным методом
Лабораторная работа №1. Построение информационной модели Построить иерархическую информационную модель на примере своего генеалогического древа. Построение модели осуществить в следующих программах: 1. Word. 2. Power Paint 3. Visio.
Лабораторная работа №2. Решение задачи линейного программирования симплекс методом Задание: Построить математическую модель формирования производства. Определить максимальную прибыль и оптимальный план симплекс методом. Имеется производство по изготовлению двух видов продукции А и В при имеющемся объеме материалов трех сортов, из которых производится продукция. Исходные данные приведены в таблице. Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Пример выполнения: Предположим, что для производства двух видов продукции А и В можно использовать только материал трех сортов. При этом на изготовление единицы изделия вида А расходуется а1 кг материала первого сорта, а2 кг материала второго сорта и а3 кг материала третьего сорта. На изготовление единицы вида В расходуется b1 кг материала первого сорта, b2 кг материала второго сорта, b3 кг материала третьего сорта. На складе фабрики имеется всего материала первого сорта С1 кг, второго сорта – С2 кг, третьего – С3 кг. От реализации единицы продукции вида А фабрика имеет прибыль m тысяч рублей, а от реализации вида В прибыль составляет n тысяч рублей. Исходные данные представлены в таблице:
Составим математическую модель: Пусть x1 количество продукции вида А, x2 количество продукции вида В. Тогда количество материала первого сорта требуемого на изготовление продукции 1 будет 3x1 +2х2 .По условию данной задачи это число не должно превышать 32, следовательно получим первое ограничение 3x1 +2х2 ≤ 32 (1) 4x1 + 5х2 - количество материала второго сорта, требуемое на изготовление продукции 2, которое не должно превышать 48. исходя из этого, получим второе ограничение 4x1 + 5х2 ≤ 48 (2) Для изготовления продукции 3 необходимо количество материала третьего сорта x1 + 6х2, которое по условию данной задачи не должно превышать 40, таким образом получим третье ограничение x1 + 6х2 ≤ 40 (3) Поскольку х1 и х2 выражают количество выпускаемой продукции, то они не должны быть отрицательными (требования не отрицательности переменных), следовательно x1≥0, x2≥0. (4) Задача состоит в том, чтобы найти такие значения х1 и х2, при которых прибыль будет максимальной. Таким образом, 6х1 – прибыль, полученная от реализации продукции вида А, а 11х2 – прибыль, полученная от реализации продукции вида В. Следовательно, прибыль на единицу продукции, которая должна быть максимальной будет иметь следующий вид F= 6x1 + 11х2 (целевая функция задачи) Таким образом, математическая модель для данной задачи будет иметь следующий вид системы, состоящей из полученных ограничений: 3x1 +2х2 ≤ 32 (1) 4x1 + 5х2 ≤ 48 (2) x1 + 6х2 ≤ 40 (3) x1≥0, x2≥0. (4) F= 6x1 + 11х2 →max
Решение исходной задачи симплексным методом
Симплексный метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Полученная модель является задачей линейного программирования, функция F – целевая функция. Она является линейной функцией своих переменных (х1,х2), ограничения на эти переменные тоже являются переменными. Необходимо найти значения переменных х1 и х2 при которых данная функция F принимает максимальное значение, при соблюдении ограничений, накладываемых на эти переменные. Решение, удовлетворяющее системе ограничения и требования не отрицательности являются допустимыми, а решение удовлетворяющие одновременно и требованиям максимизации функции в целом является оптимальным. Приведем систему к каноническому виду. Для этого введем балансовые переменные- х3, х4, х5 и получим модель в следующем виде: 3x1 +2х2+х3 = 32 4x1 + 5х2 +х4= 48 x1 + 6х2 +х5= 40 хi≥0, i=1..5. F= 6x1 + 11х2 →max. Запишем данную задачу в исходную симплексную таблицу:
Первые три строки этой таблицы содержат в условной форме систему ограничений, а именно в столбце ai 0 - записываются свободные члены уравнений. В столбцах х1, х2, х3, х4, х5 – записываются коэффициенты при соответствующих переменных этой системы. Слева от столбца ai0 , в столбце (хi), записываются базисные переменные (которые ввели для баланса), содержащиеся в соответствующих уравнениях системы. Верхняя строка и крайний верхний столбец содержат коэффициенты при соответствующих переменных в целевой функции. Последняя строка называется оценочной, а элементы строки – оценками. Первый элемент а00 представляет собой значение целевой функции на начальном этапе. а00 = 0∙32+0∙48+0∙40=0 Остальные значения обозначаются а0k, получаются в результате скалярного умножения вектора столбца Сi на вектор столбец коэффициента при неизвестном xk c последующим вычитанием соответствующего элемента верхней строки, например: а01=(0∙3+0∙4+0∙1)-6 = -6 Для получения оптимального плана необходимо, чтобы все элементы оценочной строки симплексной таблицы были неотрицательными. Для этого: 1. выбираем в исходной таблице разрешающий столбец- p. Этот столбец соответствует наибольшей по абсолютной величине отрицательной оценке. В данной задаче это будет столбец х2 (т.к |-6| < |-11|). 2. выбираем в исходной таблице разрешающую строку – q., используя условие
На перекрестке разрешающей строки и разрешающего столбца, получим разрешающий элемент - аqp. В данной задаче разрешающим элементом будет являться 6.
3. В новой симплексной таблице элементы разрешающей строки пересчитываем по формуле: На месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы оценочной строки пересчитываем по формуле прямоугольников: Расчет по формуле прямоугольников представлен в таблице
В полученной таблице в оценочной строке имеется отрицательный элемент -
Следовательно, на пересечении разрешающего столбца и разрешающей строки найдем необходимый элемент:
Составляем новую таблицу - на месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы пересчитываем по формуле прямоугольников. Получим таблицу
Все элементы оценочной строки симплексной таблицы неотрицательны, следовательно исходный план является оптимальным. Оптимальное решение получаем в виде вектора xопт = (х1, х2, х3, х4, х5) Fmax = 92,63 Оптимальное решение к исходной задаче получается отбрасыванием из xопт компонент, связанными с балансовыми переменными х3, х4, х5, т.е xопт =( Fmax = Следовательно, фабрике необходимо выпускать
|
, т.е. 32/2=16, 48/5=9,6, 40/6=6,66(min)
. Столбец, содержащий этот элемент, будет являться разрешающим, поэтому для нахождения разрешающей строки выполним следующее решение:
= 
(min)
.
единицы продукции вида А и 
единицы продукции вида В, при этом максимальная прибыль составляет 92,63 тысячи рублей.
