Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Определение расширенной задачи

Метод искусственного базиса (М-метод) дает возможность решать задачи без предварительного нахождения опорного решения.

Пусть требуется найти

(4)

Рассмотрим М-задачу, соответствующую исходной задаче. Для этого в каждое уравнение исходной задачи в канонической форме в левую часть добавляем искусственную переменную с коэффициентом «1». Эти же искусственные переменные добавляем в целевую функцию исходной задачи с коэффициентами «-М», если исходная задача на максимум.

Определение Задача, состоящая в определении

где М – некоторое достаточно большое положительное число, конкретное значение которого не задается, называется расширенной задачей по отношению к задаче (4).

Расширенная задача имеет опорный план Х= , который называется искусственным.

Переменные называются искусственными. Так как расширенная задача имеет опорный план, то ее решение можно найти симплексным методом.

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