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

Решение исходной задачи

Читайте также:
  1. I Психологические принципы, задачи и функции социальной работы
  2. I. 1.1. Пример разработки модели задачи технического контроля
  3. I. 1.2. Общая постановка задачи линейного программирования
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  6. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  7. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  8. I. Решение логических задач средствами алгебры логики
  9. I. Ситуационные задачи и тестовые задания.
  10. I. Цель и задачи дисциплины
  11. I.5.3. Подготовка данных для задачи линейного программирования
  12. I.5.4. Решение задачи линейного программирования

Весь процесс решения исходной задачи (2.15) – (2.16) приведен в таблице 4.1.

Заполнение таблицы, отвечающей 0-й итерации, происходит на основе таблицы 2.1 (см. итерацию 1) следующим образом. Главная часть таблицы 0-й итерации исходной задачи (за исключением (m +1)-й строки) полностью повторяет главную часть таблицы заключительной итерации L -задачи без столбца . Также без изменений остается столбец Р базисных векторов. Строка коэффициентов линейной формы исходной задачи и столбец коэффициентов при базисных переменных заполняются исходя из (2.15). С учетом новых элементов столбца пересчитываются значение линейной формы и оценки .

Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным выше алгоритмом.

Таблица 2.2

0 итерация

                   
    44 1/3 1/15 3 2/15 -2/5         2/15
                     
    79 1/3 -1 11/15 6 8/15 -1 3/5         8/15
    1 2/3 11/15 7/15 3/5         -1/30 2 7/9
m+1 - -   5 1/5 -2 3/5 -27 1/5         -1 3/5 -

1 итерация

    45 4/9 5/9 3 4/9   2/3       1/9  
                       
    83 7/9 2/9 7 7/9   2 2/3       4/9 188 1/2
    2 7/9 1 2/9 7/9   1 2/3       -1/18
m+1 - - 155 5/9 38 4/9 18 5/9   45 1/3       -3 1/9 -

2 итерация

    24 1/2 1/2 1 1/2         -1/4    
    29 1/2 -1/2 -17 1/2   -6     -2 1/4    
    188 1/2 1/2 17 1/2         2 1/4    
    13 1/4 1 1/4 1 3/4         1/8    
m+1 - -                   -

 

Решение ЗЛП (2.15) – (2.16) получено за две итерации. Оптимальным планом её является вектор и .

Вернемся к исходной задаче (2.1) – (2.2) со старыми переменными . Из (2.7) и (2.11) получим

(2.22)

и

. (2.23)

Принимая во внимание, что переменные могут принимать только натуральные значения, можем сказать, что при заданных затратах ресурсов на изготовление единицы товара, известных запасах ресурсов и прибыли на единицу товара предприятию необходимо выпускать следующий ассортимент товаров: 2 изделия №1, 3 изделия №2, 15 изделий №3, 1 изделие №4. Максимальная прибыль при этом составит 1023 у.е.

 

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

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

Расширенная М-задача применительно к исходной задаче (2.5) – (2.7) записывается следующим образом:

; (2.24)
; (2.25)
. (2.26)

Здесь - достаточно большое число.

Начальный опорный план задачи (2.24) – (2.26) может быть назначен непосредственно, так как в матрице условий этой задачи уже сформирована единичная подматрица, которая и составит его базис . Поэтому вектор с компонентами , и будет являться начальным опорным планом задачи (2.24) – (2.26).Переменные называются искусственными переменными.

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

В соответствии с вышеизложенным составим М - задачу применительно к нашей ЗЛП (2.15), (2.16), записанной в канонической форме. Для этого введём одну искусственную неотрицательную переменную и запишем М -задачу в виде:

(2.27)
(2.28)

где М – сколь угодно большая положительная величина. Считается что она заведомо больше любого числа которыми будут заполняться симплекс-таблицы.

Замечание: как и в L -задаче, добавление только одной искусственной переменной (вместо четырёх) обусловлено тем, что исходная задача уже содержит три единичных вектора условий .

Решение М -задачи вторым алгоритмом симплекс-метода

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)