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

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

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

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

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

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

______________Н.В. Батин

“___”______________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. Учет ограничений.

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

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать