![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Двойственный симплекс-метод
Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов Рj составленных из коэффициентов при неизвестных в системе уравнений, имеется т единичных. Вместе с тем двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы P1, Р2,..., Рт, т. е. рассмотрим задачу, состоящую в определении максимального значения функции F= с1х1 + с2х2 +…+ спхп (1) при условиях x1P1+ x2P2+…+ xmPm+ xm+1Pm+1+…+ x1P1=P0 , (2) xj≥ 0 (j=1, n), (3)
где Р1 = и Рm среди чисел bi, (i=1, m) имеются отрицательные. В данном случае Х=(b1; b2;...; bт; 0;...; 0) есть решение системы линейных уравнений (1). Однако это решение не является планом задачи, так как среди его компонент имеются отрицательные числа. Поскольку ректоры Р1, Р2,..., Рт — единичные, каждый из векторов Pj (j=1, n) можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов Pj по векторам P1, Р2,..., Рт служат числа хij=aij (i=1, m; j=1, n). Таким образом, можно m ∆ j =zj-cj=∑ ciaij-сj (j=1, n). i=1 Решение Х=(b1; b2;...; bт; 0;...; 0) системы линейных уравнений (1), определяемое базисом Р1, Р2,..., Рт, называется п севд опланом задачи (1) — (3), если ∆ j≥ 0 для любого j (j=1, n). Теорема 1. Если в псевдоплане Х=(b1; b2;...; bт; 0;...; 0), определяемом базисом Р1, Р2,..., Рт, есть хотя бы_одно отрицательное число bi< 0 такое, что все aij ≥ 0 (j=1, n), то задача (1) — (3) вообще не имеет планов. Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок. — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта. — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы). — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание. SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Теорема 2. Если в псевдоплане Х=(b1; b2;...; bт; 0;...; 0), определяемом базисом Р1, Р2,..., Рт имеются отрицательные числа bi< 0 такие, что для любого из них существуют числа aij < 0, то можно перейти к новому псевдоплану, при котором значение целевой функции задачи (1) — (3) не уменьшится. Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.
Таким образом, отыскание решения задачи (1) — (3) двойственным симплекс-методом включает следующие этапы: 1. Находят псевдоплан задачи. 2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану. 3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Ро и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+l)-й строки к соответствующим отрицательным элементам разрешающей строки. 4. Находят новый псевдоплан и повторяют все действия, начиная с этапа 2.
Таблица 2
Контрольные вопросы
|