Реферат: Решение оптимизационной задачи линейного программирования

Белорусский государственныйуниверситет

информатики и радиоэлектроники

Факультетинформационных технологий и управления

Кафедраинформационных технологий автоматизированных систем

«К защите допускаю»

______________Н.В.Батин

“___”______________2001г.

КУРСОВАЯ РАБОТА

по дисциплине «Системный анализ иисследование операций»

на тему: «Решение оптимизационнойзадачи

линейного программирования»

Выполнил студент гр.920603 Журавкин А.В.

Руководитель работы БатинН.В.

Минск, 2001

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ…….………………………………………………………………...3

1. Постановказадачи оптимизации……………………………………….…8

2. Построениеаналитической модели…………………………………….…9

3. Обоснование и описание вычислительнойпроцедуры………………..11

3.1. Приведениезадачи линейного программирования к стандартной форме………………..………………………………………………….11

3.2. Основнаяидея симлекс-метода……………………………………..12

3.3. Двухэтапныйсимплекс-метод………………………………………12

4. Решение задачи оптимизации на основесимплекс-таблиц……………14

4.1. Приведениезадачи к стандартной форме………..………………..14

4.2. Определениеначального допустимого решения…………………14

4.3. Построениеискусственного базиса………...………………………15

4.4. Первыйэтап двухэтапного симплекс-метода…………………….16

4.5. Второйэтап двухэтапного метода………………………………….19

5. Анализ модели начувствительность……………………………………..22

5.1. Статусресурсов……….………………………………………………22

5.2. Ценностьресурсов……………………………………………………22

5.3. Анализ на чувствительность к изменениям правых частейограничений……………………………………………………….…..23

5.4. Анализ на чувствительность к изменениям коэффициентов целевойфункции……………………………………………...………25

6. Определение оптимальногоцелочисленного решения…………………26

6.1. Метод Гомори для частичноцелочисленных задач……..……….26

ЗАКЛЮЧЕНИЕ…………………………………………………………...……33

СПИСОК ИСПОЛЬЗОВАННОЙЛИТЕРАТУРЫ………………….……..34

УСЛОВНЫЕСОКРАЩЕНИЯ………………………….……………………35

ПРИЛОЖЕНИЕ…………………………………………………………….…..36

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи с нелинейной целевой функциейи линейными ограничениями называют задачами нелинейного программирования слинейными ограничениями. Оптимизационные задачи такого рода можноклассифицировать на основе структурных особенностей нелинейных целевых функций.Если целевая функция Е — квадратичная функция, то мы имеем дело с задачейквадратичного программирования; если Е – это отношение линейных функций, тосоответствующая задача носит название задачи дробно-линейного программирования,и т.д. Деление оптимизационных задач на эти классы представляет значительныйинтерес, поскольку специфические особенности тех или иных задач играют важнуюроль при разработке методов их решения.

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

1. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ

Вариант 80.

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

Станки

Детали

1.Токарный

5 5 10

2.Автомат

15 15 10

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

Составить программу работы станков, при которой втечение смены (8 часов) будет выпускаться максимальное количество комплектовдеталей.

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

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

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 ≥ .

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

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax

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

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

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

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

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

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ≥, j=1,…,n

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

E = C1X1 + C2X2 + … + CnXn Þmax

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

Bj ≥ 0, j=1,…,n

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

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

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

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

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

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

3.2.ОСНОВНАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА

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

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

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

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

1. Задача линейногопрограммирования сводится к стандартной форме.

2. Строится искусственныйбазис.

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

4. Реализуется первый этапдвухэтапного метода: с помощью обычных процедур симплекс-метода выполняетсяминимизация искусственной целевой функции. Если ее минимальное значение равно0, то соответствующее решение является допустимым решением исходной задачи.Очевидно, что при нулевом значении искусственной целевой функции всеискусственные переменные также нулевые (так как искусственная целевая функция — их сумма, и все они неотрицательны). Если минимальное значение искусственнойцелевой функции оказывается отличным от нуля, это означает, что задача не имеетдопустимых решений.

5. Реализуется второй этапдвухэтапного метода: найденное на шаге 4 допустимое решение используется вкачестве начального решения исходной задачи для поиска ее оптимального решения.

4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕСИМПЛЕКС-ТАБЛИЦ

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

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

X1 + X2 + X3 + X7 = 8;

X4 + X5 + X6 + X8 = 8;

2X1 – X2 + 6X4 – 3X5 = ;

2X1 – 2X3 + 6X4 – 2X6 =;

X1, X2, X3, X4, X5, X6, X7, X8 ≥ .

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax

где Х7, Х8 – остаточные переменные.

Итак, нашу исходную задачу мы привели кстандартной форме основной задачи линейного программирования.

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

Для задачи, представленной встандартной форме, количество переменных обычно больше, чем количествоограничений. Поэтому для нахождения начального решения задачи требуется выразитьm переменных (т.е. количество переменных, равное количеству уравнений) черезостальные n-m переменных, принять эти n-m переменных равными нулю и, такимобразом, найти значения m переменных (в заданной задачеm=4 и n=8). Переменные, значения которых принимаются равными нулю,называются небазисными, а остальные m переменных — базисными. Значения базисныхпеременных неотрицательны (некоторые из них могут оказаться равными нулю).Количество базисных переменных всегда равно количеству ограничений. Найденноетаким образом решение называется начальным допустимым базисным решением. Оносоответствует всем ограничениям.

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

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

4.3. ПОСТРОЕНИЕ ИСКУССТВЕННОГО БАЗИСА

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

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

2X1 – X2 + 6X4 – 3X5 + Х9 = ;

2X1 – 2X3 + 6X4 – 2X6 + Х10 =.

где Х9 и Х10 –искусственные переменные, не имеющие никакого физического смысла, причем Х9, Х10 ≥0.

Послепостроения искусственного базиса, придав нулевые значения всем переменным,кроме базисных, получим начальный базис: Х7, Х8, Х9, Х10.Всего в базисе имеется четыре переменные и их значения равны правым частямограничений, т.е.:

Х7 = 8;

Х8 = 8;

Х9 = ;

Х10 = .

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

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

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

1. Строимискусственную целевую функцию – сумму всех искусственных

переменных:

W = X9 + X10 Þmin

2. Так как целевая функция должна быть выражена только через небазисные

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

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

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

W = — 4X1 + X2 + 2X3 – 12X4 + 3X5 + 2X6 Þmin

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

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

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

4. Определяемначальное, недопустимое решение. Базис состоит из четырех

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

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

БП

X10

БР

-1 -1 -2 -3 -3 -2

-W

-4 1 2 -12 3 2

1 1 1 1 8

2 -1

-3 1

X10

2 -2 6 -2 1

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

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

6. Реализуем первый этап двухэтапного метода: с помощью процедур симплекс-

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

БП

X10

БР

-1,5 -2 -4,5 -2 0,5

-W

-1 2 -3 2 2

1 1 1 1 8

-0,33 0,17 1,5 1 1 -0,17 8

0,33 -0,17 1 -0,5 0,17

X10

1 -2

-2 -1 1

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

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

БП

X10

БР

-5 -5 -1 1,5

-W

1 1

1 1 1 1 8

-0,33 -0,33 1 2 1 0,33 -0,5 8

0,33 -0,33 1 -0.33 0,17

0,33 -0,67 1 -0,67 -0,33 0,33

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

4.5.ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА

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

БП

БР

-5 -5

1 1

1 8

-0,33 -0,33 1 2 1 8

0,33 -0,33 1 -0,33

0,33 -0,67 1 -0,67

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

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

БП

БР

5 5 -5 5 40

1 1 1 1 8

-1,33 -1,33

-1 1

0,67 0,33 1 -0,33 0,33 2,67

0,67 1 1 -0,67 0,67 5,33

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

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

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

БП

БР

1,67 1,67 2,5 2,5 40

1 1 1 1 8

-0,67 -0,67 1 -0,5 0,5

0,44 0,11 1 0,17 0,17 2,67

0,22 0,55 1 0,33 0,33 5,33

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

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

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

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

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

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

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

5.2. ЦЕННОСТЬ РЕСУРСОВ

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

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

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

Х3 = 8 + 1*d

X6 = – 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,5*d > 0

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

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

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

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

5.4. АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ КИЗМЕНЕНИЯМ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ

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

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

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

6.1. МЕТОД ГОМОРИ ДЛЯ ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ

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

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

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:

БП

БР

1,67 1,67 2,5 2,5 40

1 1 1 1 8

-0,67 -0,67 1 -0,5 0,5

0,44 0,11 1 0,17 0,17 2,67

Х5

0,22 0,55 1 0,33 0,33 5,33

-0,44

-0,11 -0,17 -0,17 1 -0,67

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

Как видно, полученная симплекс-таблица содержитнедопустимое решение (переменная Х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. Получим новую симплекс-таблицу:

БП

БР

1,25 1,875 1,875 3,75 37,5

0,75 1 0,625 -0,375 2,25 6,5

-0,5 1 -0,25 0,75 -1,5 1

1 1 2

Х5

0,5 1 0,25 0,25 0,5 5

1 0,25 0,375 0,375 -2,25 1,5

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

Все значения базисных переменных сталинеотрицательными, это означает остановку вычислительного процесса на даннойитерации и анализ полученных результатов. Как видно из таблицы, в базис вошлановая переменная Х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

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

БП

X10

БР

1,25 1,875 1,875 3,75 37,5

Х3

0,75 1 0,625 -0,375 2,25 6,5

-0,5 1 -0,25 0,75 -1,5 1

1 1 2

1 0,5 1 0,2 0,25 0,5 5

Х1

1 0,25 0,375 0,375 -2,25 1,5

X10

-0,25 -0,375 -0,375

-2,25

1 -0,5

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

Переменная, исключаемая из базиса – это X10, т.к. ее значение –0,5 — это максимальный по модулюотрицательный элемент столбца решений. В базис включаем переменную X9, т.к. |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5,1,67 – минимальное по модулю отношение элемента Е-строки котрицательным элементам ведущей строки. Ведущий элемент равен –2,25.Получим новую симплекс-таблицу:

БП

X10

БР

0,83 1,25 1,25 1,67 36,67

Х3

0,5 1 0,25 -0,75 1 6

-0,33 1 1 -0,67 1,33

0,111 1 -0,17 -0,17 0,44 1,78

0,444 1 0,17 0,17 0,22 4,89

Х1

1 0,5 0,75 0,75 -1 2

0,11 0,17 0,17 1 -0,44 0,22

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

Решение все еще не целочисленное, поэтому переходимк следующей итерации. Переменная, имеющая максимальную дробнуючасть – это Х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

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

БП

X10

Х11

БР

0,83 1,25 1,25 1,67 36,67

Х3

0,5 1 0,25 -0,75 1 6

-0,3 1 1 -0,67 1,33

0,11 1 -0,17 -0,17 0,44 1,78

0,44 1 0,17 0,17 0,22 4,89

Х1

1 0,5 0,75 0,75 -1 2

Х9

0,11 0,17 0,17 1 -0,44 2

X11

-0,44

-0,17 -0,17 -0,22 1 -0,89

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

Переменная, исключаемая из базиса – это 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.После пересчетов получим получим новую симплекс-таблицу:

БП

X10

Х11

БР

0,938 0,94 1,25 1,89 35

Х3

1 0,063 -0,938 0,75 1,125 5

1 0,125 1,125 -0,5 -0,75 2

1 -0,125 -0,125 0,5 -0,25 2

1 1 4

Х1

1 0,563 0,563 -1,25 1,125 1

Х9

0,125 0,125 1 -0,5 0,25

1 0,375 0,375 0,5 -2,25 2

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

Столбец решений не содержит отрицательныхэлементов, все переменные 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.

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

СПИСОК ИСПОЛЬЗОВАННОЙЛИТЕРАТУРЫ

1. Смородинский С.С., Батин Н.В. Методы иалгоритмы для решения оптимизационных задач линейного программирования. Ч.1. –Мн.: БГУИР, 1995.

2. Смородинский С.С., БатинН.В. Методы и алгоритмы для решения оптимизационных задач линейногопрограммирования. Ч.2. – Мн.: БГУИР, 1996.

3. Смородинский С.С.,Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей. — Мн.:БГУИР, 1997.

4. ДегтяревЮ.И. Исследование операций. - М.: Высшая школа, 1986.

УСЛОВНЫЕ СОКРАЩЕНИЯ

БР – базисное решение

БП – базисная переменная

Условие задачи. Приложение.

+-----------------------------------------------------------------------+

¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦Вид огр.¦Значение¦

+--------+--------+--------+--------+--------+--------+--------+--------¦

¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ E ¦ ¦

+--------+--------+--------+--------+--------+--------+--------+--------¦

¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ == ¦ 0.00¦

¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ == ¦ 0.00¦

¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ <= ¦ 8.00¦

¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ <= ¦ 8.00¦

+-----------------------------------------------------------------------+

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ 1¦ E ¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ ¦ -W ¦ -4.00¦ 1.00¦ 2.00¦ -12.00¦ 3.00¦ 2.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ ¦ X9 ¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦

¦ ¦ X10¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦

¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 8.00¦

+----------------------------------------------------------------------------------------------------------+

Ведущий элемент находится в 4 столбце и 1 строке.

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 2¦ E ¦ 0.00¦ -1.50¦ -2.00¦ 0.00¦ -4.50¦ -2.00¦ 0.00¦ 0.00¦ 0.50¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ -W ¦ 0.00¦ -1.00¦ 2.00¦ 0.00¦ -3.00¦ 2.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

¦ ¦ X4 ¦ 0.33¦ -0.17¦ 0.00¦ 1.00¦ -0.50¦ 0.00¦ 0.00¦ 0.00¦ 0.17¦ 0.00¦ 0.00¦

¦ ¦ X10¦ 0.00¦ 1.00¦ -2.00¦ 0.00¦ 3.00¦ -2.00¦ 0.00¦ 0.00¦ -1.00¦ 1.00¦ 0.00¦

¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ -0.33¦ 0.17¦ 0.00¦ 0.00¦ 1.50¦ 1.00¦ 0.00¦ 1.00¦ -0.17¦ 0.00¦ 8.00¦

+----------------------------------------------------------------------------------------------------------+

Ведущий элемент находится в 5 столбце и 2 строке.

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 3¦ E ¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -1.00¦ 1.50¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

¦ ¦ -W ¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

¦ ¦ X4 ¦ 0.33¦ 0.00¦ -0.33¦ 1.00¦ 0.00¦ -0.33¦ 0.00¦ 0.00¦ 0.00¦ 0.17¦ 0.00¦

¦ ¦ X5 ¦ 0.00¦ 0.33¦ -0.67¦ 0.00¦ 1.00¦ -0.67¦ 0.00¦ 0.00¦ -0.33¦ 0.33¦ 0.00¦

¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ -0.33¦ -0.33¦ 1.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 1.00¦ 0.33¦ -0.50¦ 8.00¦

+----------------------------------------------------------------------------------------------------------+

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ 3¦ E ¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ X4 ¦ 0.33¦ 0.00¦ -0.33¦ 1.00¦ 0.00¦ -0.33¦ 0.00¦ 0.00¦ 0.00¦

¦ ¦ X5 ¦ 0.00¦ 0.33¦ -0.67¦ 0.00¦ 1.00¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦

¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ -0.33¦ -0.33¦ 1.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 1.00¦ 8.00¦

+----------------------------------------------------------------------------------------+

Ведущий элемент находится в 3 столбце и 3 строке.

Вывод промежуточных результатовоптимизации.

+----------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ 4¦ E ¦ 5.00¦ 5.00¦ 0.00¦ 0.00¦ 0.00¦ -5.00¦ 5.00¦ 0.00¦ 40.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ ¦ X4 ¦ 0.67¦ 0.33¦ 0.00¦ 1.00¦ 0.00¦ -0.33¦ 0.33¦ 0.00¦ 2.67¦

¦ ¦ X5 ¦ 0.67¦ 1.00¦ 0.00¦ 0.00¦ 1.00¦ -0.67¦ 0.67¦ 0.00¦ 5.33¦

¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ -1.33¦ -1.33¦ 0.00¦ 0.00¦ 0.00¦ 2.00¦ -1.00¦ 1.00¦ 0.00¦

+----------------------------------------------------------------------------------------+

Ведущий элемент находится в 6 столбце и 4 строке.

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ 5¦ E ¦ 1.67¦ 1.67¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 2.50¦ 2.50¦ 40.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ ¦ X4 ¦ 0.44¦ 0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.17¦ 0.17¦ 2.67¦

¦ ¦ X5 ¦ 0.22¦ 0.56¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.33¦ 0.33¦ 5.33¦

¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 8.00¦

¦ ¦ X6 ¦ -0.67¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ -0.50¦ 0.50¦ 0.00¦

+----------------------------------------------------------------------------------------+

Результаты оптимизации.

Базис Значение

X4 2.67

X5 5.33

X3 8.00

X6 0.00

Максимум функции равен 40.00

Вывод промежуточныхрезультатов оптимизации.

+-------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ 1¦ E ¦ 1.67¦ 1.67¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 2.50¦ 2.50¦ 0.00¦ 40.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ X4 ¦ 0.44¦ 0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.17¦ 0.17¦ 0.00¦ 2.67¦

¦ ¦ X5 ¦ 0.22¦ 0.56¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.33¦ 0.33¦ 0.00¦ 5.33¦

¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 8.00¦

¦ ¦ X6 ¦ -0.67¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ -0.50¦ 0.50¦ 0.00¦ 0.00¦

¦ ¦ X9 ¦ -0.44¦ -0.11¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ 1.00¦ -0.67¦

+-------------------------------------------------------------------------------------------------+

Ведущий элемент находится в 1 столбце и 5 строке.

Вывод промежуточныхрезультатов оптимизации.

+-------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 2¦ E ¦ -0.00¦ 1.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.88¦ 1.88¦ 3.75¦ 37.50¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ ¦ X4 ¦ -0.00¦ -0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.00¦ -0.00¦ 1.00¦ 2.00¦

¦ ¦ X5 ¦ -0.00¦ 0.50¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.25¦ 0.25¦ 0.50¦ 5.00¦

¦ ¦ X3 ¦ -0.00¦ 0.75¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.62¦ -0.38¦ 2.25¦ 6.50¦

¦ ¦ X6 ¦ -0.00¦ -0.50¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.25¦ 0.75¦ -1.50¦ 1.00¦

¦ ¦ X1 ¦ 1.00¦ 0.25¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦ 0.38¦ -2.25¦ 1.50¦

+-------------------------------------------------------------------------------------------------+

Результаты оптимизации.

Базис Значение

X4 2.00

X5 5.00

X3 6.50

X6 1.00

X1 1.50

Максимум функции равен 37.50

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 2¦ E ¦ -0.00¦ 1.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.88¦ 1.88¦ 3.75¦ 0.00¦ 37.50¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ X4 ¦ -0.00¦ -0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.00¦ -0.00¦ 1.00¦ 0.00¦ 2.00¦

¦ ¦ X5 ¦ -0.00¦ 0.50¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.25¦ 0.25¦ 0.50¦ 0.00¦ 5.00¦

¦ ¦ X3 ¦ -0.00¦ 0.75¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.62¦ -0.38¦ 2.25¦ 0.00¦ 6.50¦

¦ ¦ X6 ¦ -0.00¦ -0.50¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.25¦ 0.75¦ -1.50¦ 0.00¦ 1.00¦

¦ ¦ X1 ¦ 1.00¦ 0.25¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦ 0.38¦ -2.25¦ 0.00¦ 1.50¦

¦ ¦ X10¦ 0.00¦ -0.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.38¦ -0.38¦ -2.25¦ 1.00¦ -0.50¦

+----------------------------------------------------------------------------------------------------------+

Ведущий элемент находится в 9 столбце и 6 строке.

Вывод промежуточныхрезультатов оптимизации.

+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 3¦ E ¦ -0.00¦ 0.83¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.25¦ 1.25¦ -0.00¦ 1.67¦ 36.67¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ X4 ¦ -0.00¦ -0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ -0.00¦ 0.44¦ 1.78¦

¦ ¦ X5 ¦ -0.00¦ 0.44¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.17¦ 0.17¦ -0.00¦ 0.22¦ 4.89¦

¦ ¦ X3 ¦ -0.00¦ 0.50¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.25¦ -0.75¦ -0.00¦ 1.00¦ 6.00¦

¦ ¦ X6 ¦ -0.00¦ -0.33¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦ 1.00¦ -0.00¦ -0.67¦ 1.33¦

¦ ¦ X1 ¦ 1.00¦ 0.50¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.75¦ 0.75¦ -0.00¦ -1.00¦ 2.00¦

¦ ¦ X9 ¦ -0.00¦ 0.11¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.17¦ 0.17¦ 1.00¦ -0.44¦ 0.22¦

+----------------------------------------------------------------------------------------------------------+

Результаты оптимизации.

Базис Значение

X4 1.78

X5 4.89

X3 6.00

X6 1.33

X1 2.00

X9 0.22

Максимум функции равен 36.67

Вывод промежуточныхрезультатов оптимизации.

+-------------------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦ X11 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 3¦ E ¦ -0.00¦ 0.83¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.25¦ 1.25¦ -0.00¦ 1.67¦ 0.00¦ 36.67¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ X4 ¦ -0.00¦ -0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ -0.00¦ 0.44¦ 0.00¦ 1.78¦

¦ ¦ X5 ¦ -0.00¦ 0.44¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.17¦ 0.17¦ -0.00¦ 0.22¦ 0.00¦ 4.89¦

¦ ¦ X3 ¦ -0.00¦ 0.50¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.25¦ -0.75¦ -0.00¦ 1.00¦ 0.00¦ 6.00¦

¦ ¦ X6 ¦ -0.00¦ -0.33¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦ 1.00¦ -0.00¦ -0.67¦ 0.00¦ 1.33¦

¦ ¦ X1 ¦ 1.00¦ 0.50¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.75¦ 0.75¦ -0.00¦ -1.00¦ 0.00¦ 2.00¦

¦ ¦ X9 ¦ -0.00¦ 0.11¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.17¦ 0.17¦ 1.00¦ -0.44¦ 0.00¦ 0.22¦

¦ ¦ X11¦ 0.00¦ -0.44¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ 0.00¦ -0.22¦ 1.00¦ -0.89¦

+-------------------------------------------------------------------------------------------------------------------+

Ведущий элемент находится в 2 столбце и 7 строке.

Вывод промежуточныхрезультатов оптимизации.

+-------------------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦ X11 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 4¦ E ¦ -0.00¦ -0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.94¦ 0.94¦ -0.00¦ 1.25¦ 1.88¦ 35.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

¦ ¦ X4 ¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦ -0.00¦ -0.12¦ -0.12¦ -0.00¦ 0.50¦ -0.25¦ 2.00¦

¦ ¦ X5 ¦ -0.00¦ -0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ 4.00¦

¦ ¦ X3 ¦ -0.00¦ -0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.06¦ -0.94¦ -0.00¦ 0.75¦ 1.13¦ 5.00¦

¦ ¦ X6 ¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ 0.12¦ 1.12¦ -0.00¦ -0.50¦ -0.75¦ 2.00¦

¦ ¦ X1 ¦ 1.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.56¦ 0.56¦ -0.00¦ -1.25¦ 1.12¦ 1.00¦

¦ ¦ X9 ¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.12¦ 0.12¦ 1.00¦ -0.50¦ 0.25¦ 0.00¦

¦ ¦ X2 ¦ -0.00¦ 1.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦ 0.38¦ -0.00¦ 0.50¦ -2.25¦ 2.00¦

+-------------------------------------------------------------------------------------------------------------------+

Результаты оптимизации.

Базис Значение

X4 2.00

X5 4.00

X3 5.00

X6 2.00

X1 1.00

X9 0.00

X2 2.00

Максимум функции равен 35.00

еще рефераты

Еще работы по математике

Реферат по математике

Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка

31 Августа 2013

Реферат по математике

Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

31 Августа 2013

Реферат по математике

Решение уравнений в целых числах

31 Августа 2013

Реферат по математике

Ряды Фурье и их приложения

20 Июня 2015