Студопедия

Главная страница Случайная страница

Разделы сайта

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






    • Определение 4.1. Задача, состоящая в определении максимального значения функции


    Стр 1 из 3Следующая ⇒




    Теоретическая часть

    Метод искусственного базиса

    Для задачи, записанной в форме основной задачи линейного программирования, можно непосредственно указать ее опорный план, если среди векторов Pj, компонентами которых являются коэффициенты при неизвестных в системе уравнений данной задачи, име­ется mединичных (m – число неравенств ограничений, m ≥ 3).

    Однако для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов Рj- не всегда есть mединичных. Рассмотрим такую задачу:

    Пусть требуется вычислить максимум функции

    F = С1Х1 + С2Х2 +...+ СnХn (11.1)

    при условиях

    (11.2)

    .........

    x j ≥ 0 (), (11.3)

     

    где , m < n и среди векторов

     

    Р1 = Р2 = … Рn нет m единичных.

    Определение 4.1. Задача, состоящая в определении максимального значения функции

    F = С1Х1 + С2Х2 +...+ СnХn –MXn+1 - …- MXn+m (11.4)

     

    при условиях

    (11.5)

    ...........

     

    x j ≥ 0 (), (11.6)

     

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

    Расширенная задача имеет опорный план

    Х=(0; 0;...; 0; b1; b 2;...; b m), который

    n нулей

    определяется системой единичных векторов Рn+1, Рn+2, ...., Рn+m, образующих базис m-го векторного пространства, который назы­вается искусственным. Сами векторы, так же как и переменные xn+i (i= 1, m), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть получено симплексным методом.

    Теорема 11.1. Если в оптимальном плане X*=(х1*; х2*;...; xn*; x*n+1;...; x*n+m) расширенной задачи (11.4) — (11.6)значения искусственных переменных х*n+i = 0 (i= ), то X*=(х1*; х2*;...; xn*) является оптимальным планом исходной задачи (11.1) — (11.3).

    Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
    Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
    Что умеет делать SeoHammer
    — Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
    — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
    — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
    — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
    SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.
    Зарегистрироваться и Начать продвижение

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

    При опорном плане Х=(0; 0;...; 0; b1; b2;...; bm), расширенной задачи значение линейной формы определяется по формуле

    (11.7)

    а значения равны - . (11.8)

    Таким образом, Fo и разности z j — Cj состоят из двух независимых частей, одна из кото­рых зависит от М, а другая — нет.

    После вычисления F0 и их значения, а также исходные данные расширенной задачи заносят в таблицу, которая содер­жит на одну строку больше, чем обычная симплексная табли­ца. При этом в (m + 2)-ю строку помещают коэффициенты при М, а в (m+1)-ю—слагаемые, не содержащие М.

    При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m + 2)-й строки.

    Искусствен­ный вектор, исключенный из базиса в результате некоторой итерации, в дальнейшем не имеет смысла вводить ни в один из последующих базисов и, следовательно, преобразование столб­цов этого вектора излишне.

    Необходимо иметь ввиду, что возможны случаи, когда в результате некоторой итерации ни один из искусственных век­торов из базиса не будет исключен.

    Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

    Итерационный процесс по (m + 2)-й строке ведут до тех пор, пока:

    1) либо все искусственные векторы не будут исключены из базиса;

    2) либо не все искусственные векторы исключены, но (m + 2)-я строка не содержит больше отрицательных элементов в столб­цах векторов P1, P2,.... Рn+m;

    В первом случае базис отвечает некоторому опорному пла­ну исходной задачи и определение ее (исходной задачи) оптимального плана про­должают по (m+1)-й строке.

    Во втором случае, если элемент, стоящий в (m+2)-й строке столбца вектора Ро отрицателен, исходная задача не имеет решения; если же он равен нулю, то полученный опорный план исходной задачи является вырожденным и базис содержит по крайней мере один из векторов искусственного базиса.

    Если исходная задача содержит несколько единичных векто­ров, то их следует включить в искусственный базис.

    Следовательно, процесс решения исходной задачи (11.1) — (11.3) методом искусственного базиса включает следующие ос­новные этапы:

    1) составляют расширенную задачу (11.4) — (11.6);

    Сервис онлайн-записи на собственном Telegram-боте
    Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
    — Разгрузит мастера, специалиста или компанию;
    — Позволит гибко управлять расписанием и загрузкой;
    — Разошлет оповещения о новых услугах или акциях;
    — Позволит принять оплату на карту/кошелек/счет;
    — Позволит записываться на групповые и персональные посещения;
    — Поможет получить от клиента отзывы о визите к вам;
    — Включает в себя сервис чаевых.

    Для новых пользователей первый месяц бесплатно.
    Зарегистрироваться в сервисе

    2) вычисляют опорный план расширенной задачи;

    3) с помощью обычных вычислений симплекс-метода исклю­чают искусственные векторы из базиса. В результате либо получают опорный план расширенной задачи, либо уста­навливают ее неразрешимость;

    4) используя полученный опорный план расширенной задачи, либо получают симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

    Практическое применение метода искусственного базиса. Решение задачи ручным способом.

    Вычислить минимум функции F = - 2х1+3х2 - 6х3 - х4 (11.9)

    при условиях

    ,

    , (11.10)

    ,

    x1, x2, x3, x4 ≥ 0. (11.11)

    Обратите внимание – в системе ограничений имеются как неравенства обоих типов, так и равенства.

    Решение.

    Запишем данную задачу в форме основной задачи: вычислить максимум функции F = 2х1-3х2+6х3+х4 → max (11.12)

     

    при условиях

    (11.13)

    x1, x2, x3, x4, х5, х6 ≥ 0.

    Обратите внимание, что мы ввели дополнительные (это пока не искусственные) переменные во второе и третье неравенства со знаками, соответствующими виду неравенства (превратили неравенства в равенства)

    Запишем векторы из коэффициентов при неизвестных:

     

    Р1 = ; Р2 = ; Р3 = ; Р4 = ; Р5 = ; Р6 = . (11.14)

     

    Среди векторов P1, Р2, Р3, Р4, Р5 и Р6только два единичных (Р4 и Р5)-, (вектор, в котором элемент равен (-1) за единичный не принимается).

    В левую часть третьего уравнения системы ограничений (там, где нет единичного вектора) задачи добавим дополнительную неотрицательную переменную х7) с тем же знаком, что и свободный член), и рассмотрим расширенную задачу, состоящую в максимизации функции

    F = 2х1-3х2+6х3+х4 –Mx7 → max (11.15)

    при условиях

    ,

    , (11.16)

    ,

    x1, x2, x3, x4, х5, х6, х7 ≥ 0.

    Выберем в качестве основных переменных – переменные х4, х5, х7

    Выразим основные переменные через неосновные:

    ,

    , (11.1)

    .

    Приравняем нулю все неосновные переменные х1 = 0, х2 = 0, х3 = 0, х6 = 0.

    Тогда расширенная задача имеет опорный план X0Р=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P4, P5, P7.

    Заполняем строки 1-3 первой симплекс -таблицы расширенной задачи (таблица 11.1).

    В верхней подстроке записываем значения коэффициентов при целевой функции расширенной задачи (11.15): (2, (-3), 6, 1, 0, 0, (-М)).

    Заполняем столбец базиса Р4, Р5, Р7.

    Заполняем столбец Сб: коэффициенты при основных переменных в целевой функции расширенной задачи: х4 = 1, х5 = 0, х7 = -М.

    Заполняем столбец Р0 (вектор столбец свободных членов расширенной задачи: 24, 22, 10 - для базисных векторов).

    Заполняем столбцы векторов Р1 – Р7.

     

    Таблица 11.1 – Первая симплекс таблица расширенной задачи

    i Базис сб P0   -3         -M
    P1 P2 P3 P4 P5 P6 P7
      P4         -2        
      P5                  
      P7 -M     -1       -1  
                -8        
          -10 -1   -2        

    Рассчитываем значения элементов строк 4 и 5.

    F0 = = 1*24 + 0 * 22 - 10 M (в строку 4 записываем значение без М, в строку 5 – значение при М);

    элемент а41 = = 1*2+ 0*1 – 2 = 0;

    элемент а51 =1*(- М) = - 1;

    элемент а42 = 1*1+ 0*2 –(-3) =4;

    элемент а52 = -1*(- М) = 1;

    элемент а43 = 1*(-2) + 0*4 –6 = -8;

    элемент а53 = 2*(- М) = -2;

    элемент а46 = 1* 0 + 0*0 –0 = 0;

    элемент а56 = (-1)(- М) =1.

    В результате анализа 4 –й и 5-й строк таблицы 11.1 можно сделать следующий вывод. В 5-й строке в столбцах векторов Рj (j= 1, 7) имеет­ся два отрицательных числа (-1 и -2). Наличие этих чисел показывает, что данный опорный план расширенной задачи не является оптимальным.

     

    Переходим к получению нового опорного пла­на расширенной задачи. В базис вводим вектор Р3 (в котором максимальное по абсолютной величине отрицательное число).

    Для опре­деления вектора, исключаемого из базиса, реализуем правило q = min(22/4; 10/2) = 10/2 (отношение 24/(-2) не берется, т.к. отрицательные элементы в столбце не используются). Следовательно, вектор Р7 исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последую­щих базисов, поэтому в дальнейших таблицах столбец данного вектора исключен (таблицы 11.2 и 11.3).

    Составляем таблицу II итерации (таблица 11.2). Она содержит только четыре строки, так как искусственный вектор (вектор Р7, а он единственный) из базиса исключен.

    Разрешающая строка – строка 3 (вектора Р7), разрешающий столбец – столбец вектора Р3, разрешающий элемент – а33 = 2.

    Заполняем столбец вектора нового базиса – Р4, Р5, Р3.

    Заполняем столбец Сб (коэффициенты при управляемых переменных, т.е. переменных в целевой функции) – Р4 = 1; Р5 = 0; Р3 = 6.

    Заполняем элементы разрешающей строки. Для этого соответствующие элементы строки три таблицы 11.1 делим на значение разрешающего элемента (а33 = 2).

    Рассчитываем оставшиеся элементы столбца Р0 :

    b10Н = b10C - а13С * b30Н = 24 – (-2) * 5 = 34;

    b20Н = b20C - а23С * b30Н = 22 – 4 * 5 = 2;

    Рассчитываем значение целевой функции на данном шаге F1

    F1 = |Cб| x |P0| (скалярное произведение вектора Сб на вектор Р0)

    F1 = 1 * 34 + 0 * 2 + 6 * 5 = 64.

    Рассчитываем значения оставшихся элементов столбца Р1 :

    a11H = a11C - a13C * a31H = 2 - (-2) * ½ = 3;

    a21H = a21C - a23C * a32H = 1 - 4 * ½ = -1;

    Рассчитываем значения оставшихся элементов столбца Р2 :

    a12H = a12C - a23C * a32H = 1 - (-2) * (-1/2) = 0;

    a22H = a22C - a23C * a32H = 2 - 4 * (- ½) = 4;

    Рассчитываем значения оставшихся элементов столбца Р6 :

    a16H = a16C - a13C * a36H = 0 -(-2) * (-1/2) = -1;

    a26H = a26C - a23C * a36H = 0 - 4 * (- ½) = 2;

    Рассчитываем значения элементов 4-й строки Р6 :

    ∆ 1 = |Cб| x |P1| - c1 = 1 * 3 + 0 *(-1) + 6 * ½ - 2 = 4;

    ∆ 2 = |Cб| x |P2| - c2 = 1 * 0 + 0 * 4 + 6 * (-½) – (-3) = 0;

    ∆ 3 = |Cб| x |P3| - c3 = 1 * 0 + 0 * 0 + 6 * 1 – 6 = 0;

    ∆ 4= |Cб| x |P4| - c4 = 1 * 1 + 0 * 0 + 6 * 0 – 1 = 0;

    ∆ 5= |Cб| x |P5| - c5 = 1 * 0 + 0 * 1 + 6 * 0 – 0 = 0;

    ∆ 6= |Cб| x |P6| - c6 = 1 * (-1) + 0 * 2 + 6 *(-1/2) – 0 = -4;

     

    Таблица 11.2- Вторая симплекс – таблица задачи 11.1

    i Базис сб P0 F1   -3        
    P1 P2 P3 P4 P5 P6
      P4               -1
      P5     -1          
      P3     1/2 -1/2       -1/2
                      -4

     

    Из анализа таблицы 2 следует, что для исходной задачи опорным является план Х= (0; 0; 5; 34; 2). Проверим его на оптималь­ность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора Р6имеется отрицательное число (-4). Сле­довательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора P6. Из базиса исключается вектор Р5 (в векторе Р6 единственное положительное число а26 = 2). Составляем таблицу III ите­рации.

     

    Таблица 11.3 - Вторая симплекс – таблица задачи 11.1

    i Базис сб F2 P0 F1   -3        
    P1 P2 P3 P4 P5 P6
      P4     5/2       1/2  
      P6     -1/2       1/2  
      P3   11/2 1/4 1/2     1/4  
                       

     

    В 4-й строке таблицы 3 нет отрицательных значений ∆ j. Это означает, что полученный опорный план исходной за­дачи Х*=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы Fmax=68.

    Отметим, что решение данной задачи можно проводить, используя только одну объединенную таблицу вида 11.4.

     

    Таблица 11. 4 – Объединенная таблица решения задачи 11.1

    i Базис сб P0   -3         -M
    P1 P2 P3 P4 P5 P6 P7
      P4         -2        
      P5                  
      P7 -M     -1       -1  
                -8        
          -10 -10   -2        
                         
      P4               -1  
      P5     -1            
      P3     1/2 -1/2       -1/2  
                      -4  
                         
      P4     5/2       1/2    
      P6     -1/2       1/2    
      P3   11/2 1/4 1/2     1/4    
                         

     


    123Следующая ⇒




    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.