Симплекс-метод, его сущность

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

     1.3 Алгоритм симплекс-метода. 

      Пусть система приведена к каноническому виду. 

     X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

     X2+q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

     X3+q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

     ………………………………………………………

     Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm 

     В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.

     Fmin= C1X1+ C2X2+ C3X3+....+ CnXn 

     Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица1).

     Таблица 1.Симплекс таблица 

 

     Первый столбец - коэффициенты в целевой функции при базисных переменных.

     Второй столбец - базисные переменные.

     Третий столбец - свободные члены (hi00).

     Самая верхняя строка - коэффициенты при целевой функции.

     Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.

     Основное поле симплекс метода - система коэффициентов из уравнения.

     Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».

     Индексная строка позволяет нам судить об оптимальности плана:

     При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.

     При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

     Переход ко второй итерации:

     Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

     Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

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

     На пересечении строки и столбца находится разрешающий элемент.

     На этом этапе осуществляется к переходу к последующим итерациям.

     Переход к итерациям:

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

     Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.

     Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.

     Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.

     Остальные элементы переносятся по формуле:

     

     1.4 Решение задачи оптимизации. Построение аналитической модели. 

     В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часовая производительность станков по каждой из деталей приведена в таблице:

     Таблица 1. Часовая производительность станков

 

     Составить программу работы станков, при которой в течение смены (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) , не хватает еще двух базисных переменных. Их можно создать с помощью специального способа, который называется построением искусственного базиса.

     Методы искусственного базиса предназначены для построения начального базиса (т.е. для получения начального решения) в случаях, когда его построение непосредственно на основе стандартной формы невозможно. При использовании искусственного базиса начальное решение оказывается недопустимым; от него по определенным алгоритмам выполняется переход к начальному допустимому решению.