Симплекс-метод, его сущность (стр. 2 из 5)
Второй столбец - базисные переменные.
Третий столбец - свободные члены (hi00).
Самая верхняя строка - коэффициенты при целевой функции.
Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».
Индексная строка позволяет нам судить об оптимальности плана:
При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.
Переход ко второй итерации:
Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.
Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.
Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца.
На пересечении строки и столбца находится разрешающий элемент.
На этом этапе осуществляется к переходу к последующим итерациям.
Переход к итерациям:
Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
Остальные элементы переносятся по формуле:
1.4 Решение задачи оптимизации. Построение аналитической модели.
В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часовая производительность станков по каждой из деталей приведена в таблице:
Таблица 1. Часовая производительность станков
| Станки | Детали | ||
| 1 | 2 | 3 | |
| 1.Токарный | 5 | 5 | 10 |
| 2. Автомат | 15 | 15 | 10 |
Составить программу работы станков, при которой в течение смены (8 часов) будет выпускаться максимальное количество комплектов деталей.
Составим аналитическую модель задачи. Для этого сначала введем переменные, которые требуется определить:
X1 – время, которое работал токарный станок над деталями типа 1 в течение рабочей смены;
X2 – время, которое работал токарный станок над деталями типа 2 в течение рабочей смены;
X3 – время, которое работал токарный станок над деталями типа 3 в течение рабочей смены;
X4 – время, которое работал станок-автомат над деталями типа 1 в течение рабочей смены;
X5 – время, которое работал станок-автомат над деталями типа 2 в течение рабочей смены;
X6 – время, которое работал станок-автомат над деталями типа 3 в течение рабочей смены.
Система ограничений состоит из двух групп. Первая группа устанавливает, что каждый из станков может работать не более 8 часов в смену.
Ограничение времени работы токарного станка:
X1 + X2 + X3 £ 8;
Ограничение времени работы станка-автомата:
X4 + X5 + X6 £ 8.
Вторая группа ограничений направлена на выполнение требования о комплектации деталей: на каждую деталь 1 должно приходиться по 2 детали 2 и 3. Но перед тем, как вводить это ограничение, определим, сколько деталей каждого типа у нас будет производиться за смену:
5X1 + 15X4 - будет произведено за смену деталей типа 1;
5X2 + 15X5 - будет произведено за смену деталей типа 2;
10X3 + 10X6 - будет произведено за смену деталей типа 3.
Теперь введем сами ограничения:
2(5X1 + 15X4) = 5X2 + 15X5;
2(5X1 + 15X4) = 10X3 + 10X6.
Очевидно, что все переменные в задаче неотрицательные (объем продукции не может быть отрицательным):
X1 , X2 , X3 , X4 , X5 , X6 ≥ 0.
Целевая функция в нашей задаче должна выражать количество комплектов деталей, выпускаемых за смену, поэтому сложим все выпускаемые детали и поделим на 5 (в комплект, как уже упоминалось, входят 1 деталь типа 1 и по 2 детали типа 2 и 3):
E= (5X1 + 15X4 + 5X2 + 15X5 + 10X3 + 10X6)/5 Þ max
или, если упростить это выражение, то получим:
E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax
Целевую функцию надо максимизировать.
Таким образом, формальная постановка задачи оптимизации имеет следующий вид:
X1 + X2 + X3 £ 8;
X4 + X5 + X6 £ 8;
2(5X1 + 15X4) = 5X2 + 15X5;
2(5X1 + 15X4) = 10X1 + 10X6;
X1 , X2 , X3 , X4 , X5 , X6 ≥ 0.
E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax
1.5 Приведение задачи к стандартной форме. Определение начального допустимого решения.
Для приведения данной задачи к стандартной форме необходимо лишь перейти от ограничений – неравенств к равенствам. Для этого введем дополнительные балансовые неотрицательные переменные. Также для упрощения дальнейших вычислений разделим обе части ограничений на комплектацию деталей на 5:
X1 + X2 + X3 + X7 = 8;
X4 + X5 + X6 + X8 = 8;
2X1 – X2 + 6X4 – 3X5 = 0;
2X1 – 2X3 + 6X4 – 2X6 =0;
X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8 ≥ 0.
E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax
где Х7 , Х8 – остаточные переменные.
Итак, нашу исходную задачу мы привели к стандартной форме основной задачи линейного программирования.
Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Поэтому для нахождения начального решения задачи требуется выразить m переменных (т.е. количество переменных, равное количеству уравнений) через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных (в заданной задаче m=4 и n=8). Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны (некоторые из них могут оказаться равными нулю). Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением. Оно соответствует всем ограничениям.
Начальное решение проще всего найти в случае, когда в каждом ограничении есть переменная, которая входит в него с коэффициентом 1 и при этом отсутствует в других ограничениях. Такие переменные принимаются в качестве базисных (они образуют начальный базис задачи). Остальные (небазисные) переменные принимаются равными нулю. Таким образом, базисные переменные принимают значения, равные правым частям ограничений.
Итак, для нахождения начального допустимого решения необходимо, чтобы в каждое из уравнений входила переменная с коэффициентом 1 и не входила в другие уравнения (базисная переменная). В нашем случае мы имеем только 2 базисные переменные (X7 и X8) , не хватает еще двух базисных переменных. Их можно создать с помощью специального способа, который называется построением искусственного базиса.
Методы искусственного базиса предназначены для построения начального базиса (т.е. для получения начального решения) в случаях, когда его построение непосредственно на основе стандартной формы невозможно. При использовании искусственного базиса начальное решение оказывается недопустимым; от него по определенным алгоритмам выполняется переход к начальному допустимому решению.
Для того, чтобы построить искусственный базис, необходимо в каждое уравнение стандартной формы, не содержащее базисных переменных (т.е. полученное из ограничения-равенства или "не меньше"), добавить по одной искусственной переменной. В нашем случае это:
2X1 – X2 + 6X4 – 3X5 + Х9 = 0;
2X1 – 2X3 + 6X4 – 2X6 + Х10 =0.
где Х9 и Х10 – искусственные переменные, не имеющие никакого физического смысла, причем Х9, Х10 ≥0.
После построения искусственного базиса, придав нулевые значения всем переменным, кроме базисных, получим начальный базис: Х7, Х8, Х9, Х10 . Всего в базисе имеется четыре переменные и их значения равны правым частям ограничений, т.е.:
Х7 = 8; Х8 = 8; Х9 = 0; Х10 = 0.
Теперь необходимо решить эту задачу, т.е. найти оптимальное допустимое решение. Для этого воспользуемся двухэтапным симплекс-методом.
Глава 2. Двухэтапный метод.
2.1 Искусственное начальное решение.
В простом симплексе при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа «<=» (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа «>=» ?
Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод и двухэтапный метод.
Для объяснения двухэтапного метода объясним сначала концепцию М-метода.
Пусть задача ЛП записана в стандартной форме. Для любого равенства I, в котором не содержится дополнительная остаточная переменная, введём искусственную переменную Ri, которая далее войдёт в начальное базисное решение. Но поскольку эта переменная искусственна (другими словами, не имеет никакого «физического смысла» в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.