|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Решение исходной задачиВесь процесс решения исходной задачи (2.15) – (2.16) приведен в таблице 4.1. Заполнение таблицы, отвечающей 0-й итерации, происходит на основе таблицы 2.1 (см. итерацию 1) следующим образом. Главная часть таблицы 0-й итерации исходной задачи (за исключением (m +1)-й строки) полностью повторяет главную часть таблицы заключительной итерации L -задачи без столбца Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным выше алгоритмом. Таблица 2.2 0 итерация
1 итерация
2 итерация
Решение ЗЛП (2.15) – (2.16) получено за две итерации. Оптимальным планом её является вектор Вернемся к исходной задаче (2.1) – (2.2) со старыми переменными
и
Принимая во внимание, что переменные
Формирование М -задачи Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М -задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача. Расширенная М-задача применительно к исходной задаче (2.5) – (2.7) записывается следующим образом:
Здесь Начальный опорный план задачи (2.24) – (2.26) может быть назначен непосредственно, так как в матрице условий этой задачи уже сформирована единичная подматрица, которая и составит его базис Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М -задаче, начальный опорный план которой может быть указан непосредственно. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план задачи (2.5) – (2.7), либо убедиться в её неразрешимости, если оказывается неразрешимой М -задача. В соответствии с вышеизложенным составим М - задачу применительно к нашей ЗЛП (2.15), (2.16), записанной в канонической форме. Для этого введём одну искусственную неотрицательную переменную
где М – сколь угодно большая положительная величина. Считается что она заведомо больше любого числа которыми будут заполняться симплекс-таблицы. Замечание: как и в L -задаче, добавление только одной искусственной переменной Решение М -задачи вторым алгоритмом симплекс-метода
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |