Линейное программирование, симлекс-метод

ВВЕДЕНИЕ

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

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

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

количество продукции - расход сырья

количество продукции - качество продукции

Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.

При постановке задачи оптимизации необходимо:

1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

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

Правильная постановка задачи могла быть следующая:

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

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

4. Учет ограничений.

РАЗДЕЛ 1. ОБОСНОВАНИЕ И ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ

ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К СТАНДАРТНОЙ ФОРМЕ

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

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

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ? 0, j=1,…,n

и обращающих в максимум линейную функцию этих переменных:

E = C1X1 + C2X2 + … + CnXn max

При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:

Bj ? 0, j=1,…,n

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

- перейти от минимизации целевой функции к ее максимизации;

- изменить знаки правых частей ограничений;

- перейти от ограничений-неравенств к равенствам;

- избавиться от переменных, не имеющих ограничений на знак.

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

Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот - любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них. Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач.

Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности». Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

рационального использования сырья и материалов; задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

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

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ

Симплексный метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.

Пусть дана функция, для которой необходимо найти наибольшее или наименьшее значение, если значения всех неизвестных неотрицательные.

ѓ = C0 + C1x1 + C2x2 +...+ Cnxn

и система m линейных уравнений с n неизвестными. Это называется системой ограничений:

a11x1 + a12x2 +...+ a1nxn = b1

a21x1 + a12x2 +...+ a2nxn = b2

...

am1x1 +am2x12 +...+ amnxn = bm

Целевую функцию представим в виде:

ѓ - C1x1-C2x2 -...-Cnxn = C0

Составим симплекс-таблицу. В дальнейшем будем считать, что ранг матрицы системы ограничений равен r.В системе ограничений выбран базис (основные неизвестные)x1,x2,...xn и коэффициенты в правой части не отрицательны.

В этом случае система ограничений будет иметь вид:

x1 +...+ a1,r+1xr+1 +...+ a1nxn = b1

x2 + a2,r+1xr+1 +...+ a2nxn = b2

...

xr+ ar,r+1xr+1 +...+ arnxn = br

Тогда целевая функция имеет вид:

ѓ + Cr+1xr+1 + Cr+2xr+2 -...- Cnxn = C0

Нахождение оптимального плана симплексным методом включает следующие этапы:

1. Находят опорный план.

2. Составляют симплекс-таблицу. В общем виде:

Базисные неизвестные	Свободные члены	x1	x2	xr	xr+1	xj	xn
x1 x2 xi xr	b1 b2 bi br	1 0 0 0	0 1 0 0	0 0 0 1	a1,r+1 a2,r+1 ai,r+1 ar,r+1	a1j a2j aij arj	a1n a2n ain arn
ѓ	C0	0	0	0	Cr+2	Cj	Cn

3. В нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент Со). Если таких чисел нет, то данное базисное решение является оптимальным.

4. Пусть элемент Сj<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует.

5. Если положительный коэффициент в j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число aij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение bi/aij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.

6. В новой симплекс-таблице в столбце базисных неизвестных вместо xi пишется xj. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками.

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

АЛГОРИТМ СИПЛЕКС-МЕТОДА

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

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.Симплекс таблица

C	Б	H	C1	C2	…	Cm	Cm+1	…	Cm+k
			X1	X2	…	Xm	Xm+1	…	Xm+k
C1 C2 C3 : : Cm	X1 X2 X3 : : Xm	h1 h2 h3 : : Hm	1 0 0 : : 0	0 1 0 : : 0	: : : : : :	0 0 0 : : 0	q1,m+1 q2,m+1 q3,m+1 : : qm,m+1	: : : : : :	q1,m+k q2,m+k q3,m+k : : qm,m+k
		F0	F1	F2	…	Cm	Cm+1	…	Cm+k

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РАЗДЕЛ 2. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ СИМЛЕКС-МЕТОДА

ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ. ПОСТРОЕНИЕ АНАЛИТИЧЕСКОЙ МОДЕЛИ

В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 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

ПРИВЕДЕНИЕ ЗАДАЧИ К СТАНДАРТНОЙ ФОРМЕ. ОПРЕДЕЛЕНИЕ НАЧАЛЬНОГО ДОПУСТИМОГО РЕШЕНИЯ

Для приведения данной задачи к стандартной форме необходимо лишь перейти от ограничений - неравенств к равенствам. Для этого введем дополнительные балансовые неотрицательные переменные. Также для упрощения дальнейших вычислений разделим обе части ограничений на комплектацию деталей на 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.

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

ЭТАПЫ ДВУХЭТАПНОГО СИМПЛЕКС-МЕТОДА

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

Строим искусственную целевую функцию - сумму всех искусственных переменных:

W = X9 + X10 min

Так как целевая функция должна быть выражена только через небазисные переменные, то выражаем искусственные переменные X9 и X10 через небазисные переменные, а затем, упростив полученное выражение, переписываем искусственную целевую функцию:

X9 = - 2X1 + X2 - 6X4 + 3X5;

X10 = - 2X1 + 2X3 - 6X4 + 2X6.

W = - 4X1 + X2 + 2X3 - 12X4 + 3X5 + 2X6 min

Для приведения к стандартной форме направим искусственную целевую

функцию на максимум, для этого умножим обе ее части на -1:

-W = 4X1 - X2 - 2X3 + 12X4 - 3X5 - 2X6 max

Определяем начальное, недопустимое решение. Базис состоит из четырех переменных, из них две искусственные, остальные две - остаточные. Базисные переменные принимают значения, равные ограничениям задачи. Остальные переменные считаем равными нулю. В этом случае целевая функция Е принимает значение 0, искусственная целевая функция -W также принимает значение 0.

Составляем исходную симплекс-таблицу:

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

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	-1	-1	-2	-3	-3	-2	0	0	0	0	0
-W	-4	1	2	-12	3	2	0	0	0	0	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	0	0	0	1	1	1	0	1	0	0	8
X9	2	-1	0	6	-3	0	0	0	1	0	0
X10	2	0	-2	6	0	-2	0	0	0	1	0

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

Реализуем первый этап двухэтапного метода: с помощью процедур симплекс-метода выполняем максимизацию функции-W. При этом переменные, включаемые в базис, выбираются по W-строке (т.е. на каждом цикле в базис включается переменная, которой соответствует максимальный по модулю отрицательный элемент в W-строке; столбец, соответствующий этой переменной, становится ведущим). В нашем случае это столбец X4, т. к. коэффициент при этой переменной в W-строке равен -12. Ведущую строку определяем следующим образом: рассчитываем так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным коэффициентам ведущего столбца, соответствующим данным базисным переменным. Затем берем минимальное из этих отношений и по тому, какой строке оно соответствует, определяем ведущую строку. У нас есть три таких отношения: по переменной Х8 (8/1=8), Х9 (0/6=0) и Х10 (0/6=0). Получилось два минимальных значения, значит, возьмем любое из них, например по переменной Х9. После находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца (в нашем случае он равен 6). Затем определяем переменные, которые будем исключать из базиса и включать в него. Переменную, которой соответствует ведущий столбец, будем включать в базис вместо переменной, которой соответствует ведущая строка. Далее все преобразования выполняем по обычным формулам симплекс-метода или по "правилу прямоугольника". Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W-строку и столбец решений. Получаем новую симплекс-таблицу:

Таблица 3. Симплекс-таблица №2.

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	-1,5	-2	0	-4,5	-2	0	0	0,5	0	0
-W	0	-1	2	0	-3	2	0	0	2	0	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	-0,33	0,17	0	0	1,5	1	0	1	-0,17	0	8
X4	0,33	-0,17	0	1	-0,5	0	0	0	0,17	0	0
X10	0	1	-2	0	3	-2	0	0	-1	1	0

Мы получили новое решение (Х7,Х8,Х4,Х10)=(8,8,0,0). Это решение недопустимо, так как в базисе содержится искусственная переменная Х10. Выполим очередную итерацию. По строке -W для включения в базис выбираем переменную X5 (т.к. -3 - максимальное по модулю отрицательное число). Столбец X5 становится ведущим. По минимальному симплексному отношению ( 8/1,5=5,33; 0/3=0) для исключения из базиса выбираем переменную Х10. Ведущий элемент равен 3. После проведенных пересчетов получаем новую симплекс-таблицу:

Таблица 4. Симплекс-таблица №3

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	0	-5	0	0	-5	0	0	-1	1,5	0
-W	0	0	0	0	0	0	0	0	1	1	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	-0,33	-0,33	1	0	0	2	0	1	0,33	-0,5	8
X4	0,33	0	-0,33	1	0	-0.33	0	0	0	0,17	0
X5	0	0,33	-0,67	0	1	-0,67	0	0	-0,33	0,33	0

Итак, как видно из Таблицы 4, все искусственные переменные вышли из базиса, искусственная целевая функция обнулилась - значит, первый этап двухэтапного симплекс-метода закончен, найдено начальное допустимое решение: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), целевая функция Е=0. Теперь переходим к реализации второго этапа: вычеркиваем из таблицы строку искусственной целевой функции и столбцы искусственных переменных; над новой таблицей выполняем обычные процедуры симплекс-метода, а именно: ведущий столбец определяется также, как и для первого этапа двухэтапного симплекс-метода, единственное различие состоит в том, что максимальный по модулю отрицательный коэффициент находим по Е-строке целевой функции. Расчет ведем до тех пор, пока в Е-строке не останется отрицательных коэффициентов:

Таблица 5. Симплекс-таблица №4

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	0	0	-5	0	0	-5	0	0	0
X7	1	1	1	0	0	0	1	0	8
X8	-0,33	-0,33	1	0	0	2	0	1	8
X4	0,33	0	-0,33	1	0	-0,33	0	0	0
X5	0	0,33	-0,67	0	1	-0,67	0	0	0

Наше начальное допустимое решение не является оптимальным, так как в Е-строке содержатся отрицательные коэффициенты. Определим по Е-строке новую переменную для включения в базис. Это переменная X3, т.к. -5 - максимальное по модулю отрицательное число (коэффициент Е-строки при переменной X6 также равен -5, поэтому выбрали любую из этих переменных, например X3). Столбец X3 становится ведущим. По минимальному симплексному отношению ( 8/1=8; 8/1=8) для исключения из базиса выбираем переменную Х7 (симплексное отношение при переменной X8 также равно 8, поэтому выбрали любую из этих переменных). Ведущий элемент равен 1. После проведенных пересчетов получаем новую симплекс-таблицу:

Таблица 6. Симплекс-таблица №5

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	5	5	0	0	0	-5	5	0	40
X3	1	1	1	0	0	0	1	0	8
X8	-1,33	-1,33	0	0	0	2	-1	1	0
X4	0,67	0,33	0	1	0	-0,33	0,33	0	2,67
X5	0,67	1	0	0	1	-0,67	0,67	0	5,33

Итак, как видно из таблицы, некоторые из искомых переменных , а именно Х3, Х4 и Х5, начали расти, что привело и к росту значения целевой функции - из нулевого значения она приняла значение 40. Это можно объяснить тем, что из точки начального допустимого решения мы перешли к соседней угловой точке области допустимых решений, причем в этой соседней точке рост целевой функции максимален. Однако в Е-строке есть еще отрицательный коэффициент, поэтому продолжим расчеты.

Определим по Е-строке новую переменную для включения в базис. Это переменная X6, т.к. -5 - максимальное по модулю отрицательное число. Столбец X6 становится ведущим. По минимальному симплексному отношению ( 0/2=0) для исключения из базиса выбираем переменную Х8. Получаем новую симплекс-таблицу:

Таблица 7. Симплекс-таблица №6

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	1,67	1,67	0	0	0	0	2,5	2,5	40
X3	1	1	1	0	0	0	1	0	8
X6	-0,67	-0,67	0	0	0	1	-0,5	0,5	0
X4	0,44	0,11	0	1	0	0	0,17	0,17	2,67
X5	0,22	0,55	0	0	1	0	0,33	0,33	5,33

Так как все коэффициенты E-строки таблицы 7 положительные, то оптимальное решение найдено. Оптимальный план состоит в том, чтобы токарный станок работал над деталями типа 3 8 часов за смену, то есть всю рабочую смену, и не работал над деталями типа 1 и 2 вообще. Станок-автомат должен работать за смену 2,67 часа над деталями типа 1 и 5,33 часа над деталями типа 2 и не должен работать над деталями типа 3. При этом за смену будет выпускаться максимально возможное количество комплектов деталей, а именно 40 комплектов. Ни один из станков не будет простаивать.

3. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

СТАТУС РЕСУРСОВ

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

По статусу ресурсы делятся на дефицитные и недефицитные. Если некоторый ресурс при реализации оптимального плана расходуется полностью, он называется дефицитным, если не полностью - недефицитным.

Статус ресурсов определяется по значениям остаточных переменных Х7 и Х8, введенных в исходную систему ограничений для приведения ее к стандартной форме. Эти переменные означают остатки ресурсов при реализации оптимального плана. Ни одна из остаточных переменных не входит в оптимальное решение, т.е. их значения равны нулю. Это означает, что токарный станок и станок-автомат использовались все выделенное для их работы время, т.е. запасы времени работы станков являются дефицитными ресурсами. Увеличение запасов дефицитных ресурсов позволяет увеличить значение целевой функции, а снижение этих запасов приводит к уменьшению целевой функции.

Ценность ресурса - это величина увеличения значения целевой функции при увеличении запасов данного ресурса на единицу (или соответственно величина уменьшения целевой функции при снижении запаса ресурса). Другое название этой величины - теневая (скрытая) цена. В симплекс-таблице, соответствующей оптимальному решению, теневые цены содержатся в E-строке и представляют собой коэффициенты при остаточных переменных, соответствующим остаткам ресурсов. Таким образом, ценность времени работы токарного станка и станка-автомата соответственно равна по 2,5 комплекта деталей. Другими словами, если запас времени работы токарного станка увеличить (уменьшить) на 1 час, то количество производимых комплектов деталей увеличится (уменьшится) на 2,5 единицы, и, аналогично, если увеличить (уменьшить) время работы станка-автомата станка на 1 час, то количество комплектов увеличится (уменьшится) на 2,5 комплекта.

АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ ПРАВЫХ ЧАСТЕЙ ОГРАНИЧЕНИЙ

Для анализа решения на чувствительность к изменению запасов времени работы станков (без изменения других исходных данных задачи) используются коэффициенты из столбцов остаточных переменных Х7 и Х8 (соответственно для токарного станка и станка-автомата) в последней симплекс-таблице. Например, если запас времени работы токарного станка изменился на d часов и стал равен 8+d часов, то новое оптимальное решение находится по следующим формулам:

Х3 = 8 + 1*d

X6 = 0 - 0,5*d

X4 = 2,67 + 0,17*d

X5 = 5,33 + 0,33*d

E = 40 + 2,5*d

При составлении этих формул использовали коэффициенты из столбца остаточной переменной Х7 в последней симплекс-таблице. По содержательному смыслу эти формулы означают изменение времени работы токарного станка или станка-автомата над каждой из деталей в сутки при изменении запаса дефицитного ресурса. Формула E = 40 + 2,5*d означает изменение количества производимых комплектов деталей в сутки. Например, если время работы токарного станка станет не 8, а 6 часов в сутки, т.е. уменьшится на 2 часа (d=-2), то базисные переменные, а также целевая функция примут следующие значения:

Х3 = 6; Х6 = 1; Х4 = 2,33; Х5 = 4,67; Е = 35.

Все остальные переменные равны нулю (они не являются базисными).

Как видно, из-за уменьшения запаса времени работы токарного станка уменьшилось время работы этого станка над деталями типа 3, но вместе с тем увеличилось время работы станка-автомата над этими же деталями. Так как станок-автомат стал работать за смену 1 час над деталями третьего типа, то он уменьшил свое время работы над деталями типа 1 и 2 (ранее он отдавал все свое время на обработку только этих деталей). И, очевидно, что если время работы токарного станка уменьшилось, то уменьшится и количество комплектов деталей, производимых в сутки.

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

Изменение запасов ресурсов (т.е. правых частей ограничений) может привести к недопустимости оптимального базиса, найденного для исходной задачи. Так как на все переменные, используемые в задаче, накладывается требование неотрицательности, допустимый диапазон изменения запаса ресурса (т. е. диапазон допустимых значений d) находят из системы неравенств. Таким образом, допустимый диапазон изменения запаса времени работы токарного станка, при котором состав переменных в базисе оптимального решения не изменяется, находится из условия:

Х3 = 8 + 1*d > 0

Х6 = 0 - 0,5*d > 0

Х4 = 2,67 + 0,17*d > 0

Х5 = 5,33 + 0,33*d > 0

Решив данную систему неравенств, получим, что -8 < d < 0. Таким образом, базис оптимального решения будет состоять из переменных (Х3,Х6,Х4,Х5), если запас времени работы токарного станка будет находиться в диапазоне от 0 до 8 часов. Выход значения d за границы этого диапазона приведет к недопустимости найденного нами оптимального решения, так как минимум одна из базисных переменных окажется отрицательной, и для того, чтобы найти оптимальное решение, нам придется решать задачу заново.

Аналогично выполняется анализ на чувствительность к изменению запаса времени работы станка-автомата.

ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ

Данная задача по своему содержанию является частично целочисленной. Переменные X1, X2, X3, X4, X5, X6, обозначающие время работы определенного станка над деталями определенного типа, должны принимать целые значения. В то же время, переменные Х7, Х8, обозначающие время простоя соответственно токарного станка и станка-автомата, могут принимать дробные значения. Для поиска оптимального целочисленного решения воспользуемся методом Гомори для частично целочисленных задач.

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

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

L1*W1 + L2*W2 + … +Ln*Wn ? {Bi} , где

Aij, если Aij?0 и Wj может быть дробной, (1)

({Bi}*Aij)/({Bi}-1), если Aij<0 и Wj может быть дробной, (2)

Lj = {Aij}, если {Aij}{Bi} и Wi должна быть целой, (3)

{Bi}*(1-{Aij})/(1-{Bi}), если {Aij}>{Bi} и Wi должна быть целой, (4)

j=1,…,n

где Wn - небазисная переменная;

Bi - базисная переменная, имеющая максимальную дробную часть ( дробная часть числа - это разность между этим числом и максимальным целым числом, не превосходящим его);

Aij - коэффициент, стоящий на пересечении строки i-ой базисной переменной и столбца j-ой небазисной переменной;

Далее полученное ограничение приводится к стандартному виду:

-L1*W1 - L2*W2 - … -Ln*Wn + Sr = -{Bi}

где r - номер итерации алгоритма.

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

В нашем случае переменная, имеющая максимальную дробную часть - это

Х4 ({2,67}=0,67)

она должна быть целой, переменные Х7 и Х8 могут быть дробными, переменные Х1 и Х2 должны быть целыми, поэтому, согласно выше приведенной формуле, составим новое дополнительное ограничение. Так как все коэффициенты на пересечениях базисной переменной Х4 и небазисных переменных

Х1 , Х2 , Х7 , Х8 ? 0 (0,44?0, 0,11?0, 0,17?0)

то коэффициенты при переменных Х1 и Х2 рассчитали по формуле (3):

L1={0,44}=0,44, L2={0,11}=0,11,

а коэффициенты при переменных Х7 и Х8 рассчитали по формуле (1):

L3=0,17, L4=0,17. {В4}={Х4} = {2,67} = 0,67

Ограничение будет иметь вид:

0,44Х1 + 0,11Х2 + 0,17Х7 + 0,17Х8 ? 0,67

Можно убедиться, что это ограничение сделало наше оптимальное решение недопустимым (если подставить Х1=0, Х2=0, Х7=0, Х8=0, - значения переменных, полученных в оптимальном нецелочисленном решении, то получим 0?0,67 - неверно).

Приведя ограничение к стандартному виду, имеем:

-0,44Х1 - 0,11Х2 - 0,17Х7 - 0,17Х8 + Х9 = -0,67

Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменной Х9:

Таблица 8. Симплекс-таблица №7

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	БР
E	1,67	1,67	0	0	0	0	2,5	2,5	0	40
X3	1	1	1	0	0	0	1	0	0	8
X6	-0,67	-0,67	0	0	0	1	-0,5	0,5	0	0
X4	0,44	0,11	0	1	0	0	0,17	0,17	0	2,67
Х5	0,22	0,55	0	0	1	0	0,33	0,33	0	5,33
X9	-0,44	-0,11	0	0	0	0	-0,17	-0,17	1	-0,67

Как видно, полученная симплекс-таблица содержит недопустимое решение (переменная Х9 имеет отрицательное значение). Произведем дальнейший пересчет таблицы, причем ведущую строку определяем максимальным по модулю отрицательным элементом столбца решений, а ведущий столбец - минимальным по модулю отношением элемента Е-строки к отрицательным элементам ведущей строки. Пересчет симплекс-таблицы осуществляется на основе стандартных процедур симплекс-метода.

Итак, переменная, исключаемая из базиса - это X9, т.к. ее значение -0,67 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X1, т.к.

|1,67/(-0,44)|=3,8, |1,67/(-0,11)|=15,2, |2,5/(-0,17)|=14,7, 3,8

- минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен -0,44. Получим новую симплекс-таблицу:

Таблица 9. Симплекс-таблица №8.

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	БР
E	0	1,25	0	0	0	0	1,875	1,875	3,75	37,5
X3	0	0,75	1	0	0	0	0,625	-0,375	2,25	6,5
X6	0	-0,5	0	0	0	1	-0,25	0,75	-1,5	1
X4	0	0	0	1	0	0	0	0	1	2
Х5	0	0,5	0	0	1	0	0,25	0,25	0,5	5
X1	1	0,25	0	0	0	0	0,375	0,375	-2,25	1,5

Все значения базисных переменных стали неотрицательными, это означает остановку вычислительного процесса на данной итерации и анализ полученных результатов. Как видно из таблицы, в базис вошла новая переменная Х1, переменные Х3, Х4 и Х5 уменьшили свое значение, а переменная Х6 увеличилась. Значение целевой функции уменьшилось и стало равно 37,5 , что объясняется тем, что оптимальное нецелочисленное решение было отсечено нашим дополнительным ограничением, и для поиска оптимального целочисленного решения мы ушли вглубь области допустимых решений, где значение целевой функции меньше оптимального. Наше решение все еще нецелочисленное, поэтому составим новое ограничение.

Переменная, имеющая максимальную дробную часть - это

Х3 ({6,5}=0,5)

(Х1 имеет такую же дробную часть, поэтому выбрали любую из них, например, Х3), она должна быть целой, переменные Х7 , Х8 и Х9 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х3 и небазисных переменных

Х2 , Х7 , Х9 ? 0 (0,75?0, 0,625?0, 2,25?0),

то коэффициент при переменной Х2 рассчитаем по формуле (3):

L1={0,75}=0,75,

коэффициенты при переменных Х7 и Х9 рассчитаем по формуле (1): L3=0,625, L4=2,25. Так как коэффициент на пересечении базисной переменной Х3 и небазисной переменной Х8<0, то коэффициент при переменной Х8 рассчитаем по формуле (2):

L2=({6,5}*(-0,375))/({6,5}-1)=0,375.

{В3}={Х3} = {6,5} = 0,5.

Ограничение будет иметь вид:

0,25Х2 + 0,625Х7 + 0,375Х8 + 2,25Х9 ? 0,5

Или, после приведения к стандартному виду, получим:

-0,25Х2 - 0,625Х7 - 0,375Х8 - 2,25Х9 + Х10 = -0,5

Добавим это ограничение к нашей предыдущей симплекс-таблице:

Таблица 10. Симплекс-таблица №9

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	1,25	0	0	0	0	1,875	1,875	3,75	0	37,5
Х3	0	0,75	1	0	0	0	0,625	-0,375	2,25	0	6,5
X6	0	-0,5	0	0	0	1	-0,25	0,75	-1,5	0	1
X4	0	0	0	1	0	0	0	0	1	0	2
X5	1	0,5	0	0	1	0	0,2	0,25	0,5	0	5
Х1	1	0,25	0	0	0	0	0,375	0,375	-2,25	0	1,5
X10	0	-0,25	0	0	0	0	-0,375	-0,375	-2,25	1	-0,5

Переменная, исключаемая из базиса - это X10, т.к. ее значение -0,5 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X9, т.к.

|3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5, 1,67

- минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен -2,25. Получим новую симплекс-таблицу:

Таблица 11. Симплекс-таблица №10

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	0,83	0	0	0	0	1,25	1,25	0	1,67	36,67
Х3	0	0,5	1	0	0	0	0,25	-0,75	0	1	6
X6	0	-0,33	0	0	0	1	0	1	0	-0,67	1,33
X4	0	0,111	0	1	0	0	-0,17	-0,17	0	0,44	1,78
X5	0	0,444	0	0	1	0	0,17	0,17	0	0,22	4,89
Х1	1	0,5	0	0	0	0	0,75	0,75	0	-1	2
X9	0	0,11	0	0	0	0	0,17	0,17	1	-0,44	0,22

Решение все еще не целочисленное, поэтому переходим к следующей итерации. Переменная, имеющая максимальную дробную часть - это Х5 ({4,89}=0,89), она должна быть целой, переменные Х7 , Х8 и Х10 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х5 и небазисных переменных

Х2, X7, X8, Х10?0 (0,44?0, 0,17?0, 0,22?0),

то коэффициент при переменной Х2 рассчитаем по формуле (3):

L1={0,44}=0,44,

коэффициенты при переменных Х7, Х9 и Х10 рассчитаем по формуле (1):

L2=0,17, L3=0,17, L4=0,22. {В5}={Х5} = {4,89} = 0,89.

Ограничение будет иметь вид:

0,44Х2 + 0,17Х7 + 0,17Х8 + 0,22Х10 ? 0,89

Или, после приведения к стандартному виду, получим:

-0,44Х2 - 0,17Х7 - 0,17Х8 - 0,22Х10 + Х11 = -0,89

Добавим это ограничение к нашей предыдущей симплекс-таблице:

Таблица 12. Симплекс-таблица №11

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Х11	БР
E	0	0,83	0	0	0	0	1,25	1,25	0	1,67	0	36,67
Х3	0	0,5	1	0	0	0	0,25	-0,75	0	1	0	6
X6	0	-0,3	0	0	0	1	0	1	0	-0,67	0	1,33
X4	0	0,11	0	1	0	0	-0,17	-0,17	0	0,44	0	1,78
X5	0	0,44	0	0	1	0	0,17	0,17	0	0,22	0	4,89
Х1	1	0,5	0	0	0	0	0,75	0,75	0	-1	0	2
Х9	0	0,11	0	0	0	0	0,17	0,17	1	-0,44	0	2
X11	0	-0,44	0	0	0	0	-0,17	-0,17	0	-0,22	1	-0,89

Переменная, исключаемая из базиса - это X11, т.к. ее значение -0,89 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную

X2, т.к. |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4, |1,67/(-0,22)|=7,6, 1,9

- минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен -0,44. После пересчетов получим получим новую симплекс-таблицу:

Таблица 13. Симплекс-таблица №12

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Х11	БР
E	0	0	0	0	0	0	0,938	0,94	0	1,25	1,89	35
Х3	0	0	1	0	0	0	0,063	-0,938	0	0,75	1,125	5
X6	0	0	0	0	0	1	0,125	1,125	0	-0,5	-0,75	2
X4	0	0	0	1	0	0	-0,125	-0,125	0	0,5	-0,25	2
X5	0	0	0	0	1	0	0	0	0	0	1	4
Х1	1	0	0	0	0	0	0,563	0,563	0	-1,25	1,125	1
Х9	0	0	0	0	0	0	0,125	0,125	1	-0,5	0,25	0
X2	0	1	0	0	0	0	0,375	0,375	0	0,5	-2,25	2

Столбец решений не содержит отрицательных элементов, все переменные X1, X2, X3 , X4 , X5 , X6 приняли целочисленные значения, значит, оптимальное целочисленное решение найдено, оно равно:

(X1,X2,X3,X4,X5,X6)=(1,2,5,2,4,2),

целевая функция при этом принимает максимальное значение: Е=35.

ЗАКЛЮЧЕНИЕ

Симлекс-метод - это характерный пример итерационных вычислений. используемых при решении большинства оптимизационных задач.

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

После проведенных вычислений, решив задачу оптимизации, мы получили следующие результаты: оптимальный план работы станков состоит в том, чтобы токарный станок работал 1 час над деталями типа 1, 2 часа над деталями типа 2 и 5 часов над деталями типа 3 за смену; станок-автомат должен работать 2 часа над деталями типа 1 , 4 часа над деталями типа 2 и 2 часа над деталями типа 3 за смену. При этом количество комплектов деталей, выпускаемых цехом, будет максимально и равно 35.

В результате проведенного анализа на чувствительность к изменению запаса времени работы токарного станка получили, что если запас времени работы этого станка будет находиться в пределах от 0 до 8 часов, то базис оптимального решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5).