Вс, 23.07.2017, 07:40
Главная
Регистрация
Вход
აბაშის ხმა
Приветствую Вас Гость | RSS
Меню сайта
Категории раздела
Алгебра
Алгебра Дж. Буля
Алгоритмы
Анализ
Векторы
Вейвлеты
Геометрия
Графики
Дзета-функция Римана
Задача Лагранжа
Интегралы
Математика
Математическая интуиция
Математические игры
Методы Рунге Кутты
Нестандартный анализ
Теория Графов
Уравнения
Численные методы оптимизации
Геометрия в пространстве
Мини-чат
200
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » Математика » Численные методы оптимизации

Формирование М-задачи
Формирование М-задачи

Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.

Рассмотрим наряду с исходной задачей (2.1) - (2.3) в канонической форме следующую расширенную задачу (М-задачу):

                                                                (5.1)

                                                                         (5.2

                                                                             (5.3)

Здесь М>0 – достаточно большое число.

Начальный опорный план задачи (5.1) - (5.3) имеет вид



Переменные  называются искусственными переменными.

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

В соответствии с вышеизложенным имеем: требуется решить задачу (2.12), (2.13), записанную в канонической форме. Введем искусственную неотрицательную переменную х9 и рассмотрим расширенную М-задачу

   

                                  (5.4)

при условиях


                 (5.5)

, где .

где М – сколь угодно большая положительная величина.

Как и в L-задаче, добавление только одной искусственной переменной  (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7.

Категория: Численные методы оптимизации | Добавил: nukria (25.04.2012)
Просмотров: 83 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Вход на сайт
Поиск
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • | Copyright MyCorp © 2017 | |