Индивидуальное задание
СТАРООСКОЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ
(филиал) федерального государственного автономного образовательного учреждения
Высшего образования
«Национальный исследовательский технологический университет «МИСиС»
Кафедра АИСУ
Отчёт по лабораторной работе №7
По дисциплине: «Теория систем и системный анализ»
Выполнил: ст. гр. ЭТ-14-2Д
Рудаков Андрей Геннадиевич
Проверила ст. пр.:
Ковтун Нелли Игоревна
Старый Оскол
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
НА ОСНОВЕ МЕТОДОВ ИСКУССТВЕННОГО БАЗИСА
Цель работы
1. Рассмотреть назначение и принцип работы методов искусственного базиса.
2. Изучить двухэтапный метод.
3. Научиться проводить анализ оптимального решения на чувствительность.
Индивидуальное задание
Пусть К1 и К2 – количество проданных миксеров и чайников.
Тогда условия таковы:
К1*6 + К2*5 –> MIN
К1*4 + К2*2 >= 900
К1*2 + К2*1 >= 400
К1*1 + К2*1 >= 300
К1 и К2 – целые
К1*4 + К2*2 - К3 + К6 = 900
К1*2 + К2*1 - К4 + К7 = 400
К1*1 + К2*1 - К5 + К8 = 300
W = K6 + K7 + K8
E = К1*6 + К2*5
К6 = 900 - К1*4 - К2*2 + К3
К7 = 400 - К1*2 - К2*1 + К4
К8 = 300 - К1*1 - К2*1 + К5
W =1600 - К1*7 - К2*4 + К3+ К4 + К5 -> MIN
-W = - (1600 - К1*7 - К2*4 + К3+ К4 + К5) -> MAX
-E = - К1*6 - К2*5
Контрольные вопросы
1. Для решения каких задач линейного программирования предназначены методы искусственного базиса?
Методы искусственного базиса предназначены для решения задач линейного программирования, содержащих ограничения различных видов: «больше ли равно», «меньше или равно», «равно».
2. Расскажите принцип работы всех методов искусственного базиса.
Принцип работы всех методов искусственного базиса следующий. Во все ограничения, не содержащих базисных переменных, вводятся искусственные переменные (по одной в каждое ограничение), используемые для построения начального базиса. После этого выполняется поиск оптимального решения на основе обычных процедур симплекс-метода.
В окончательном (оптимальном) решении задачи все искусственные переменные должны быть равны нулю. Если в оптимальном решении какая-либо из искусственных переменных оказывается ненулевой, это означает, что задача не имеет допустимых решений. Причиной может быть ошибка в математической модели или противоречия в постановке задачи (например, количество изделий, которое требуется выпустить, не может быть выпущено из-за ограничений на ресурсы).
3. Какой физический смысл имеют искусственные переменные?
Искусственные переменные не имеют никакого физического смысла: их нельзя интерпретировать как количество изделий, запаса ресурсов и т.д. Они требуются только для построения начального базиса.
4. Перечислите основные этапы реализации двухэтапного метода
Основные этапы реализации двухэтапного метода (как и других методов искусственного базиса) следующие.
1) Строится искусственный базис. Находится начальное недопустимое решение. Выполняется переход от начального недопустимого решения к некоторому допустимому решению. Этот переход реализуется путем минимизации (сведения к нулю) искусственной целевой функции, представляющей собой сумму искусственных переменных.
2) Выполняется переход от начального допустимого решения к оптимальному решению.
5. На что должна быть направлена искусственная целевая функция и почему?
Эта целевая функция подлежит минимизации, т.к. для определения начального допустимого решения необходимо, чтобы все искусственные переменные приняли нулевые значения.
6. Назовите условие завершения поиска допустимого решения.
Искусственная целевая функция равна нулю, и все искусственные переменные исключены из базиса. Получено допустимое решение. Таким образом, первый этап двухэтапного метода завершен. Искусственная целевая функция и искусственные переменные исключаются из симплекс-таблицы.