Воротницкий Ю.И. Исследование операций

Введение

0. Введение. Общие сведения. Объем курса – 34 часа лекции 24 часа лабораторные занятия 14 часов – КСР Лабораторные занятия и КСР проводятся в классе ПЭВМ и выполняются в среде пакета Mathematica Форма отчетности – экзамен (5 семестр) Преподавание обеспечивает кафедра кибернетики Лектор – Воротницкий Юрий Иосифович

0. Введение. Цели и задачи дисциплины. Ознакомить с фундаментальными основами дисциплины «Исследование операций», методами и конструктивными вычислительными алгоритмами решения задач поиска оптимальных решений. Определить множество задач в области информационно-коммуникационных технологий, решаемых методами дисциплины. Сформировать навыки формализации, разработки математических моделей и реализации вычислительных алгоритмов типовых задач исследования операций.

0. Введение. Литература. Основная 1. Таха Х. Введение в исследование операций.: Пер. с англ. – М.: Издательский дом «Вильямс», Давыдов Э.Г. Исследование операций. – М.: Высшая школа, Дегтярев Ю.И. Исследование операций. – М.: Высшая школа, Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. – М.: Мир, Дополнительная 1. Ахо А.В., Хопкрофт Дж.Э., Ульман Дж.Д. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», Поляк Б.Т. Введение в оптимизацию. – М.: Наука, Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, Химмельблау Д. Прикладное нелинейное программирование. – М.: Мир, 1975

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

0. Введение. 0.1 Основные понятия. Изменяемые переменные (переменные решения – decision variables) – переменные, оптимальные значения которых должны быть найдены в ходе решения математической модели задачи исследования операций: Целевая функция (objective function) – функция, вычисляющая количественное выражение критерия оптимальности: Эта функция достигает экстремума, когда ее аргументы принимают значения, описывающие оптимальное решение задачи в соответствии с заданным критерием. Эта функция зависит как от изменяемых переменных x 1,x 2,…,x n, так и от параметров задачи a 1,a 2,…,a l, которые принимают фиксированные значения, определяемые ее условием.

0. Введение Основные понятия. Ограничения (constraints) – неравенства или равенства, определяющие область допустимых значений (ОДЗ) изменяемых переменных, в которой осуществляется поиск решения (экстремума целевой функции).Часто выделяют два специфических типа ограничений: простые ограничения сверху (simple upper bound): неотрицательность переменных (nonnegativity restrictions):

0. Введение Основные понятия. Математическая модель (model) – результат формализации задачи исследования операций. Включает в себя множество изменяемых переменных, целевую функцию и ограничения, записанные в виде математических соотношений или заданные соответствующими вычислительными алгоритмами. Параметры модели (parameters) – множество параметров {a k, b j, c sj, u i }, входящих в структуру целевой функции и функций ограничений. Значения этих параметров определяются условием решаемой задачи и должны быть заданы при формировании математической модели.

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Предположим, что нам необходимо выбрать операторов мобильной связи и тарифные планы для организации персональной системы мобильной связи. Известны: среднемесячный объем разговоров с абонентами мобильных сетей Velcom, МТС, Belcel, республиканской телефонной сети, тарифные планы операторов, стоимость приемлемого мобильного телефона требуемый срок окупаемости его приобретения, максимальное количество телефонов, предельная сумма разовых вложений в приобретение телефонов.

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Варьируемые параметры и целевая функция Варьируемые параметры: массив бинарных переменных x i, i=1,...,n. x i ={1,0}. Количество элементов массива n равно количеству существующих тарифных планов у всех операторов. Значение 1 означает приобретение телефона и подключение к соответствующему тарифному плану соответствующего оператора. Функция, описывающая критерий оптимальности (целевая функция) – суммарные затраты в месяц здесь A i – затраты в месяц на подключение по i -му тарифному плану

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Структура месячных затрат (Velcom и МТС) Затраты в месяц по i -му тарифному плану для операторов Velcom и МТС определяются следующим образом: здесь T ij =v j t ij – стоимость j -го типа трафика объема vj, если он направлен на подключение по i -му тарифному плану (трафик направляется, если существует подключение по этому плану, т.е. x i =1, и тариф t ij по этому плану наименьший из тарифов существующих подключений); B i – ежемесячная абонентская плата по i -му плану; P i = S i /d – ежемесячные отчисления за стоимость телефона S i для i -го подключения из расчета окупаемости за d месяцев.

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Структура месячных затрат (Belcel) Затраты в месяц по i -му тарифному плану для оператора Belcel определяются следующим образом: здесь M i – ежемесячная оплата за разговоры определяется как T ij - стоимость j -го трафика, если он направлен на подключение по i - му тарифному плану; B i – ежемесячная предоплата по i -му плану; P i = S i /d – ежемесячные отчисления за стоимость телефона S i для i -го подключения из расчета окупаемости за d месяцев.

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Ограничения Ограничения в нашем случае принимают следующий вид: где X – максимально приемлемое число телефонов здесь c i – стоимость приемлемого телефона для i -го подключения, C – предельная сумма разовых вложений в стоимость телефонов.

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Математическая модель задачи Окончательно математическая модель задачи оптимального выбора операторов мобильной связи и тарифных планов выглядит следующим образом:

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Алгоритм и программная реализация Учитывая ограниченное число возможных вариантов оптимальное решение данной задачи может быть найдено путем полного перебора всех возможных вариантов Программная реализация метода была выполнена в среде пакета Microsoft Excel. Исходные данные заносятся в электронную таблицу, в ней же выполняется расчет целевой функции и функций, задающих ограничения. Перебор параметров выполняется с помощью небольшой программы, написанной на встроенном языке Microsoft Visual Basic. Ссылка на соответствующую книгу Excel размещена здесь.здесь

0. Введение Задача выбора операторов мобильной связи и тарифных планов. Некоторые замечания Как это обычно бывает, рассмотренная нами формулировка задачи предполагает наличие целого ряда упрощающих предположений. В частности, нами не учитывались: Качество связи Интервал тарификации Покрытие территории Беларуси Возможность роуминга и тарифы на него Функциональность и другие потребительские качества доступных телефонов Человеческий фактор И многое другое… Отметим, что варьируемые параметры в нашей задаче могли принимать только дискретные (бинарные) значения. Мы имели дело с задачей дискретной оптимизации.

0. Введение Многовариантность математических моделей. Задача нахождения коробки максимального объема заданной площади поверхности Рассмотрим почти «школьную» задачу построения оптимального решения: найти длину a, ширину b и высоту c прямоугольного параллелепипеда, имеющего наибольший объем V при заданной площади поверхности S. Математическая модель задачи: Варьируемые параметры – a, b, c. Необходимо найти максимум целевой функции F(a,b,c)=V(a,b,c)=abc max F(a,b,c); при ограничениях в виде равенства и неравенств: 2ab+2ac+2bc=S ; a > 0; b > 0; c > 0; Такую модель «школьными» методами решить невозможно (хотя интуитивно понятно, что решением будет куб). Оптимальное решение может быть найдено с помощью специальных методов нелинейного программирования, в частности реализованных в MS Excel (см. соответствующую книгу Excel)книгу

0. Введение Многовариантность математических моделей. Задача нахождения коробки требуемого объема заданной площади поверхности Модифицируем задачу: требуется найти длину a, ширину b и высоту c прямоугольного параллелепипеда, имеющего заданный объем V при заданной площади S. Математическая модель задачи: Варьируемые параметры – a, b, c. Необходимо найти минимум целевой функции min F(a,b,c) F(a,b,c)=(abc-V) 2 при ограничениях: 2ab+2ac+2bc=S a > 0; b > 0; c > 0; Эта модель оказывается «не по зубам» стандартным алгоритмам решения задач Excel.

0. Введение Многовариантность математических моделей. Задача нахождения коробки требуемого объема заданной площади поверхности Переформулируем математическую модель: Варьируемые параметры - a, b. Необходимо найти минимум целевой функции min F(a,b) F(a,b)=(abc-V) 2 где с=(S-2ab)/2(a+b) при ограничениях: a > 0; b > 0; a+b < S; Эта задача решается в Excel без малейших проблем, хотя, очевидно, что она имеет несколько решений и соответственно целевая функция имеет не один минимум.Excel Кстати, при решении ограничения можно не учитывать, так как априори очевидно, что минимум функции лежит внутри области допустимых значений переменных a и b.

0. Введение Последовательность решения задач исследования операций. П остановка задачи проектирования просветляющего оптического покрытия Характерный пример более сложной задачи – нахождение оптимальных параметров широкополосного просветляющего оптического покрытия T(n i,d i,N, λ,θ,α) λθαλθα R(n i,d i,N, λ,θ,α) n i,d i,n=Nn=1 i=1,2…m λ max λ min R θ 1, α 1 θ 2, α 2 θ 3, α 2 Требуется минимизировать энергетический коэффициент отражения от покрытия в диапазоне длин волн, углов падения и поляризации

0. Введение Последовательность решения задач исследования операций. Формализация задачи Пусть покрытие состоит из непоглощающих диэлектрических слоев, характеризуемых толщинами d i и показателями преломления n i. На плоскослоистое покрытие под углом θ падает плоская электромагнитная волна, длина волны λ, угол поляризации α. Известна рекурсивная формула для расчета энергетического коэффициента отражения R=R(n i,d i,N,λ,θ,α). Варьируемые параметры: n i,d i, i=1,2…m. Альтернативные решения отличаются значениями варьируемых парамметров. Необходимо минимизировать средний в заданном диапазоне длин волн λ min λ λ max, углов падения θ min θ θ max и углов поляризации α min α α max Суммарная тощина покрытия ограничена величиной D max Показатели преломления материалов слоев лежат в диапазоне, определяемом выбранными материалами для нанесения просветляющих слоев, диапазон толщин слоев ограничен технологическими возможностями.

0. Введение Последовательность решения задач исследования операций. Математическая модель

0. Введение Структурная и параметрическая оптимизация Процедура поиска оптимального решения может быть реализована двумя способами: В первом случае поиск оптимального решения достигается путем нахождения оптимальных значений (обычно – доставляющих минимум или максимум целевой функции) варьируемых параметров задачи. В этом случае говорят о параметрической оптимизации. Во втором случае для нахождения оптимального решения варьируют структуру оптимизируемого объекта. Такая оптимизация называется структурной. Обычно структурная оптимизация сочетается с оптимизацией параметрической.

0. Введение Методы исследования операций Все модели исследования операций можно разделить на группы по следующим основным признакам: Вид модели детерминированные вероятностные Тип варьируемых переменных: дискретные непрерывные Вид целевой функции и ограничений: линейные нелинейные Для их решения используются: Методы оптимизации Методы имитационного моделирования Эвристические подходы

0. Введение Методы исследования операций Наука и искусство Этапы реализации методов исследования операций: Формализация исходной проблемы Построение математической модели Поиск оптимального решения (решение модели) Проверка адекватности модели Реализация решения Из всех этапов только третий достаточно точно определен и прост в силу хорошо проработанной математической теории. Выполнение остальных этапов в значительной мере является искусством, а не наукой, и процедуры выполнения этих этапов не строго детерминированы. На всех этапах, предшествующих получению оптимального решения математической модели, успех зависит от опыта и творчества всей команды (специалистов-аналитиков и заказчиков задачи принятия решений), занимающейся решением задачи исследования операций

0. Введение Этапы реализации методов исследования операций Формализация исходной проблемы предполагает исследование предметной области, где возникла рассматриваемая проблема описание возможных альтернативных решений выбор варьируемых параметров определение критерия оптимальности и задание целевой функции построение системы ограничений Построение математической модели перевод формализованной задачи на язык математических соотношений попытка построить математическую модель как одну из стандартных математических моделей если модель очень сложная и не приводится к стандартному типу, ее следует упростить, либо применить эвристический подход, либо методы имитационного моделирования

0. Введение Этапы реализации методов исследования операций Поиск оптимального решения (решение модели) Применение известных методов оптимизации, методов имитационного моделирования или эвристических подходов Исследование чувствительности оптимального решения к отклонению варьируемых параметров Проверка адекватности модели Оценка полученного решения: имеет ли оно смысл и приемлемо ли интуитивно Сравнение полученного решения с известными ранее моделями или поведением реальной системы Реализация решения Перевод результатов решения модели в рекомендации, комплекты технической документации или другие документы, понятные для лиц принимающих решение – заказчиков решения исходной проблемы

1.Линейное программирование

1. Линейное программирование 1.1. Постановка задачи Линейное программирование (ЛП) – это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. Модель линейного программирования, как и любая задача исследования операций включает три основных элемента: Переменные, которые следует определить, Целевая функция, подлежащая минимизации (или максимизации) Ограничения, которым должны удовлетворять переменные Линейное программирование оперирует с линейными моделями, то есть целевая функция и функции левой части ограничений должны быть линейными:

1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг Телекоммуникационная компания Spam Networks оказывает два основных вида услуг: подключение пользователей по коммутируемым каналам по безлимитному плану в Internet и хостинг веб-сайтов. Для организации доступа в Internet компания покупает асимметричный трафик: исходящий у оператора Fool Communications по цене 6 долларов за 1 Кбит/с, пропускная способность выделенной линии – до 2 Мбит/с входящий трафик через собственную приемную спутниковую тарелку по цене 0,8 доллара за 1 Кбит/с, максимальный объем – 2 Мбит/с Для предоставления услуги хостинга одного сайта необходимо зарезервировать 2 Кбит/с на передачу и 1 Кбит/с на прием. Месячный доход от услуги составляет 8 долларов. Для предоставления услуги доступа в Internet необходимо зарезервировать 4 Кбит/с на прием и 1 Кбит/с на передачу. Месячный доход от услуги составляет 6 долларов.

1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг Кроме того, количество портов на сервере удаленного доступа ограничено 32 портами, что не позволяет оказывать услуги доступа в Internet более чем 480 клиентам. Spam Networks Fool Communications Пользователи Internet Хостинг веб-сайтов Коммутируемые линии Internet Выделенная линия

1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг: формализация исходной проблемы Множество возможных альтернатив – различное число сопровождаемых веб-сайтов и количество подключаемых пользователей Internet Варьируемые параметры – число сопровождаемых сайтов x 1 и число пользователей Internet x 2. Хотя параметры являются целочисленными, эту задачу можно попытаться решить в вещественных числах и затем округлить решение до ближайших целых. Цель – получение максимального дохода: F(x 1, x 2 )=8x 1 +6x 2 Ограничения: общий объем входящего трафика меньше или равен предельно возможному, общий объем исходящего трафика меньше или равен пропускной способности канала, число подключаемых пользователей меньше или равно емкости портов х – средний коэффициент использования. Число сопровождаемых сайтов и число пользователей неотрицательны.

1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг: математическая модель max F(x 1, x 2 ); F(x 1, x 2 ) = 8x 1 +6x 2 ; x 1 +4 x ; 2x 1 + x ; x 2 480; x 1 0; x 2 0. Данная модель – классическая модель линейного программирования. Замечание: хотя мы и назвали задачу: «оптимизация структуры услуг…», это – типичная задача параметрической оптимизации. Рассмотрим графическое решение этой модели (модель решается в электронной таблице Excel: см. соответствующую книгу).книгу

1. Линейное программирование Графическое решение задачи ЛП Оптимизация структуры телекоммуникационных услуг: решение Месячный доход от хостинга $8 Месячный доход от подключения $6

1. Линейное программирование. 1.3.Графическое исследование чувствительности решения Оптимизация структуры телекоммуникационных услуг: изменение коэффициентов целевой функции Месячный доход от хостинга $8 Месячный доход от подключения снижаем до $3,9

1. Линейное программирование. 1.3.Графическое исследование чувствительности решения Оптимизация структуры телекоммуникационных услуг: изменение коэффициентов целевой функции Месячный доход от хостинга снизился до $1,3 Месячный доход от подключения $6

1. Линейное программирование. 1.3.Графическое исследование чувствительности решения Оптимизация структуры телекоммуникационных услуг: изменение ограничений (исходные ограничения) Доступный объем входящего трафика – 2048 Кбит/с Доступный объем исходящего трафика – 2048 Кбит/с

1. Линейное программирование. 1.3.Графическое исследование чувствительности решения Оптимизация структуры телекоммуникационных услуг: изменение ограничений (сокращение трафика) Доступный объем входящего трафика – 2048 Кбит/с Доступный объем исходящего трафика сократился до 728 Кбит/с

1. Линейное программирование. 1.3.Графическое исследование чувствительности решения Оптимизация структуры телекоммуникационных услуг: изменение ограничений (увеличение доступного трафика) Доступный объем входящего трафика – 2048 Кбит/с Доступный объем исходящего трафика увеличился до 4096 Кбит/с

1. Линейное программирование. 1.3.Графическое исследование чувствительности решения Оптимизация структуры телекоммуникационных услуг: изменение ограничений. Стоимость ресурса

1. Линейное программирование. 1.4.Принципы построения аналитических методов решения задачи ЛП Оптимизация структуры телекоммуникационных услуг: Анализ результатов поиска решения Интуитивно очевидно, что оптимальное решение может находиться только в угловых точках пространства допустимых решений. На этом основан симплексный алгоритм решения задач линейного программирования. При анализе чувствительности наблюдаются качественные изменения при переходе с одной ветви решения на другую. Необходимо особенно тщательно анализировать чувствительность, если решение находится в окрестности таких точек Графическое решение возможно только в простейших случаях – при числе варьируемых параметров не более 2 и небольшом числе ограничений. В общем случае необходимо построение эффективного вычислительного алгоритма для решения задачи линейного программирования.

1. Линейное программирование. 1.4.Принципы построения аналитических методов решения задачи ЛП Методика поиска оптимального решения Оптимальное решение задачи ЛП всегда ассоциируется с угловой точкой пространства решений (крайней точкой множества). Для построения симплекс-метода необходимо вначале выполнить алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу ЛП к стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных. Стандартная форма позволяет алгебраически получить базисные решения, (используя систему уравнений, порожденную ограничениями). Эти базисные решения полностью определяют все крайние точки пространства решений. Симплекс-метод позволяет найти оптимальное решение среди всех базисных.

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП шаг 1 Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью. Неравенства любого типа (со знаками или ) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных – остаточных или избыточных. остаточные переменные y k обычно интерпретируются как количество неиспользованных ресурсов, а избыточные переменные z l – как превышение левой части неравенства над заданным минимально допустимым значением. Правую часть равенства всегда можно сделать неотрицательной путем умножения равенства на -1. Кстати, неравенство вида также преобразуется в неравенство вида (и наоборот) посредством умножения обоих частей неравенства на -1.

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП шаг 2 Все варьируемые переменные должны быть неотрицательными. Преобразование неположительных переменных в неотрицательные: Назовем переменную свободной, если она может принимать как положительные, так и отрицательные значения. Преобразование свободных переменных в неотрицательные можно выполнить следующим образом: причем одну из двух переменных x i - или x i + можно полагать равной нулю. Например, если x=3, то ее можно представить в виде x i + =3, x i - =0. Если x=-5, то x i + =0, x i - =-5. Такие преобразования должны быть выполнены во всех неравенствах и целевой функции После решения задачи с переменными x i - и x i + значения исходных переменных восстанавливаются с помощью обратной подстановки.

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП шаг 3 Целевую функцию следует минимизировать или максимизировать Задача эквивалентна задаче и наоборот

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП Математическая модель в стандартной форме max F(x 1, x 2 ); F(x 1, x 2 ) = 8x 1 +6x 2 ; x 1 +4 x ; 2x 1 + x ; x 2 480; x 1 0; x 2 0. max F(x 1, x 2 ); F(x 1, x 2 ) = 8x 1 + 6x 2 ; x 1 +4 x 2 + y 1 = 2048; 2x 1 + x 2 + y 2 = 2048; x 2 + y 3 = 480; x 1 0; x 2 0; y 1 0; y 2 0; y 3 0;

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП Математическая модель в стандартной форме (после переобозначения переменных)

1. Линейное программирование. 1.6.Понятие базисного решения задачи ЛП Допустимые базисные решения Задача ЛП в стандартной форме содержит m линейных равенств с n неизвестными переменными (m

1. Линейное программирование. 1.6.Понятие базисного решения задачи ЛП Свободные переменные и базисные решения Свободные переменные мы определили как переменные, которые могут принимать любые действительные значения (положительные, нулевые и отрицательные). В стандартной форме записи задачи ЛП свободная переменная x i должна быть представлена как разность двух неотрицательных переменных: Из определения базисного решения очевидно, что невозможна ситуация, когда x i + и x i - являются одновременно базисными переменными, что вытекает из их зависимости. Это означает, что в любом базисном решении по крайней мере одна из переменных x i + и x i - должна быть небазисной, то есть нулевой. Ранее было показано, что при этом переменная x i может принимать любое действительное значение (если x=3, то ее можно представить в виде x i + =3, x i - =0; если x=-5, то x i + =0, x i - =-5 ).

1. Линейное программирование Основы симплекс-метода Идея алгоритма Можно доказать, что решение задачи ЛП может достигаться только в одной из угловых точек ОДЗ варьируемых параметров (в крайней точке пространства решений). Можно доказать, что базисные решения полностью определяют все крайние точки пространства решений. Тогда решение может быть найдено путем перебора всех допустимых базисных решений, что неэффективно. Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. Алгоритм начинается с некоторого допустимого базисного решения и затем пытается найти другое базисное решение, улучшающее значение целевой функции. Для этого необходимо: ввести в число базисных переменную, которая ранее была небазисной (это возможно, если ее возрастание ведет к увеличению целевой функции); одну из текущих базисных переменных сделать нулевой (небазисной): это необходимо, чтобы получить систему m уравнений с m неизвестными.

1. Линейное программирование Основы симплекс-метода Оптимизация структуры телекоммуникационных услуг. Математическая модель. Вспомним математическую формулировку задачи x 1 – число сопровождаемых сайтов, x 2 – число подключаемых пользователей к Internet, x 3 – неиспользуемая пропускная способность спутникового канала, x 4 – неиспользуемая пропускная способность исходящего канала, x 4 – неиспользуемая емкость портов

1. Линейное программирование Основы симплекс-метода Оптимизация структуры телекоммуникационных услуг. Система уравнений Перепишем уравнения в виде: x 1 – число сопровождаемых сайтов, x 2 – число подключаемых пользователей к Internet, x 3 – неиспользуемая пропускная способность спутникового канала, x 4 – неиспользуемая пропускная способность исходящего канала, x 4 – неиспользуемая емкость портов

1. Линейное программирование Основы симплекс-метода Исходная таблица Задачу ЛП в стандартной форме можно представить в виде таблицы: Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Ре- ше- ние F x3x x4x x5x5 480 Решение: x 1 =0; x 2 =0; x 3 =2048; x 4 =2048; x 5 =480.

1. Линейное программирование Основы симплекс-метода Начальное допустимое базисное решение на графике Месячный доход от хостинга $8 Месячный доход от подключения $6

1. Линейное программирование Основы симплекс-метода Определение вводимой в базис переменной Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Ре- ше- ние F x3x x4x x5x5 480 Вводим в базис переменную, отрицательный коэффициент при которой в F-строке таблицы (положительный коэффициент в целевой функции) наибольший по абсолютной величине. Это - x 1.

Месячный доход от подключения $6 1. Линейное программирование Основы симплекс-метода Графическое нахождение наибольшего значения, которое может принять вводимая переменная. Месячный доход от хостинга $8 Месячный доход от подключения $6 X 1 =1024

1. Линейное программирование Основы симплекс-метода Алгебраическое нахождение наибольшего значения, которое может принять вводимая переменная. Симплекс-метод должен определять новую точку алгебраически. Эта точка – точка пересечения прямых, соответствующих ограничениям, с координатной осью, соответствующей вводимой переменной (в данном случае – с осью 0x 1. Алгебраически эта точка – отношение правой части равенства (столбца «Решение») к коэффициенту при вводимой переменной (x 1 ). Разумеется, нас интересуют только неотрицательные отношения. Чтобы точка лежала внутри ОДЗ надо из всех положительных выбрать наименьшее значение x1x1 БазисРешениеОтношение (точка пересечения) 1x3x /1=2048 2x4x /2=1024 (минимум) 0x5x /0= (не подходит)

Месячный доход от подключения $6 1. Линейное программирование Основы симплекс-метода Алгебраическое нахождение наибольшего значения, которое может принять вводимая переменная: графическая иллюстрация. Месячный доход от хостинга $8 Месячный доход от подключения $6 X 1 =1024X 1 =2048 Значение целевой функции возрастет до 8192

1. Линейное программирование Основы симплекс-метода Выбор исключаемой из базиса переменной Исключается та переменная, которой в найденной нами точке в таблице соответствовало наименьшее неотрицательное отношение. В рассматриваемом случае это – переменная x 4 (отношение равно 1024). Критерий исключения таков, потому что именно в этом случае в новом базисном решении переменная x 1 автоматически получит наилучшее из возможных значение Вычисление нового базисного решения основано на методе исключения переменных (метод Гаусса-Жордана)

1. Линейное программирование Основы симплекс-метода Определение ведущего столбца, ведущей строки и ведущего элемента Ведущий столбец – столбец, соответствующий вводимой в базис переменной. Ведущая строка – строка, соответствующая исключаемой переменной. Ведущий элемент – элемент, находящийся на пересечении ведущего столбца и ведущей строки. Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Ре- ше- ние F x3x x4x x5x5 480

1. Линейное программирование Основы симплекс-метода Вычисление нового базисного решения: шаг 1. Вычисление элементов новой ведущей строки Новая ведущая строка = Текущая ведущая строка / ведущий элемент Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Ре- ше- ние F x3x /2=021/2=½0/2=01/2=½0/2=0x4x4 2048/2 = x5x5 480

1. Линейное программирование Основы симплекс-метода Вычисление нового базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка) Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Ре- ше- ние F x3x ½0½0x1x x5x5 480

1. Линейное программирование Основы симплекс-метода Вычисление нового базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка) Нулевая строка: коэффициент в ведущем столбце = -8. Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние 01- (-80) = (-81) = (-8½) =-2 0- (-80) =0 0- (-8½) =4 0- (-80) =0 F 0- (-81024) = x3x ½0½0x1x x5x5 480

1. Линейное программирование Основы симплекс-метода Вычисление нового базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка) Первая строка: коэффициент в ведущем столбце = 1. Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние F (10) =0 1- (11) =0 4- (1½ ) =3½ 1- (10) =1 0- (1 ½) = -½ 0- (10) =0 x3x (11024) = ½0½0x1x x5x5 480

1. Линейное программирование Основы симплекс-метода Вычисление нового базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка) Третья строка: коэффициент в ведущем столбце = 0. Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние F ½1-½0x3x ½0½0x1x1 30- (00) =0 0- (01) =0 1- (0 ½) =1 0- (00) =0 0- (0 ½ ) =0 1- (00) =1 x5x (01024) =480

1. Линейное программирование Основы симплекс-метода Вычисление нового базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка) Третья строка: коэффициент в ведущем столбце = 0. Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние F ½1-½0x3x ½0½0x1x x5x5 480 Решение: x 1 =1024; x 2 =0; x 3 =1024; x 4 =0; x 5 =480.

Месячный доход от подключения $6 1. Линейное программирование Основы симплекс-метода Новое базисное решение на графике. Месячный доход от хостинга $8 Месячный доход от подключения $6 X 1 =1024

1. Линейное программирование Основы симплекс-метода Определение вводимой в базис переменной Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние F ½1-½0x3x ½0½0x1x x5x5 480 Вводим в базис переменную, отрицательный коэффициент при которой в F-строке таблицы (положительный коэффициент в целевой функции) наибольший по абсолютной величине. Это - x 2.

1. Линейное программирование Основы симплекс-метода Определение исключаемой переменной Находим отношение правой части равенства (столбца «Решение») к коэффициенту при вводимой переменной (x 2 ). Рассматриваются только неотрицательные отношения. Чтобы точка лежала внутри ОДЗ надо из всех положительных выбрать наименьшее значение x2x2 БазисРешениеОтношение (точка пересечения) 3½x3x /3½ =293 (минимум) ½x1x /½ = x5x /1=480

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние F /3½ =0 3½1/3½ =2/7 -½/ 3 ½ =-1/7 0/3½ =0 x3x3 1024/3½ = ½0½0x1x x5x Линейное программирование Основы симплекс-метода Вычисление следующего базисного решения: шаг 1. Вычисление элементов новой ведущей строки Новая ведущая строка = Текущая ведущая строка / ведущий элемент

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние F /7-1/70x2x ½0½0x1x x5x Линейное программирование Основы симплекс-метода Вычисление следующего базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние 01004/73 5/7 0F /7-1/70x2x /74/70x1x /71/71x5x Линейное программирование Основы симплекс-метода Вычисление следующего базисного решения: шаг 2. Вычисление элементов остальных строк Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка) Результат: Решение: x 1 =878; x 2 =293; x 3 =0; x 4 =0; x 5 =187.

Месячный доход от подключения $6 1. Линейное программирование Основы симплекс-метода Графическая иллюстрация полученного решения. Месячный доход от хостинга $8 Месячный доход от подключения $6

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние 01004/73 5/7 0F /7-1/70x2x /74/70x1x /71/71x5x Линейное программирование Анализ решения, полученного симплекс-методом Оптимальность решения Так как отрицательных коэффициентов в F – строке больше нет, полученное решение является оптимальным Оптимальное число поддерживаемых сайтов x 1 =878 Оптимальное число пользователей Internet x 2 =293 Решение: x 1 =878; x 2 =293; x 3 =0; x 4 =0; x 5 =187.

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние 01004/73 5/7 0F /7-1/70x2x /74/70x1x /71/71x5x Линейное программирование Анализ решения, полученного симплекс-методом Дефицитные ресурсы Неиспользованный входящий трафик x 3 =0 Неиспользованный входящий трафик x 4 =0 Эти ресурсы являются дефицитными, и увеличение объема разрешенного входящего и исходящего трафика приведет к улучшению решения (получению дополнительного дохода) Решение: x 1 =878; x 2 =293; x 3 =0; x 4 =0; x 5 =187.

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 x5x5 Ба- зис Реше- ние 01004/73 5/7 0F /7-1/70x2x /74/70x1x /71/71x5x Линейное программирование Анализ решения, полученного симплекс-методом Недефицитные ресурсы Неиспользованная емкость портов сервера удаленного доступа (возможное число дополнительных подключений) x 5 =187 Этот ресурс не является дефицитными, и увеличение числа портов при данных объемах входящего и исходящего трафика не приведет к улучшению решения (получению дополнительного дохода) Решение: x 1 =878; x 2 =293; x 3 =0; x 4 =0; x 5 =187.

1. Линейное программирование Алгоритм симплекс-метода Базовый алгоритм 1. Найти начальное допустимое базисное решение (полный алгоритм будет рассмотрен позднее) 2. На основе условия оптимальности определить вводимую переменную 3. Если вводимых переменных нет – закончить вычисления. 4. На основе условия допустимости выбрать исключаемую переменную 5. Методом Гаусса-Жордана вычислить новое базисное решение 6. Перейти к шагу 2 7. Вывести текущее базисное решение, являющееся оптимальным.

1. Линейное программирование Алгоритм симплекс-метода Правила выбора вводимых и исключаемых переменных Условие оптимальности. Вводимой переменной в задаче максимизации (минимизации) целевой функции является небазисная переменная, имеющая наибольший по модулю отрицательный (положительный) коэффициент в F-строке. Если в F-строке есть несколько таких коэффициентов, выбор вводимой переменной осуществляется произвольно. Оптимальное решение достигнуто, если в F-строке при небазисных коэффициентах все переменные являются неотрицательными (неположительными). Условие допустимости. В качестве исключаемой выбирается базисная переменная, для которой отношение правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если базисных переменных с таким свойством несколько, то выбор исключаемой переменной осуществляется произвольно.

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде В глобальной компьютерной сети сформирована распределенная вычислительная среда, состоящая из N высокопроизводительных рабочих станций, объединенных в M групп (кластеров). Данные для обработки однородны и трудоемкость расчетов зависит только от их объема. Данные независимы и их отдельные массивы могут обрабатываться совершенно независимо. Известно время обработки 1 Мб данных на каждой рабочей станции q i. Необходимо найти оптимальное распределение заданного объема данных для обработки на станциях. Так как рабочие станции должны использоваться и для решения других – локальных – задач необходимо минимизировать общее время загрузки всех рабочих станций. Желательно, чтобы результаты обработки от разных кластеров поступали одновременно. Кроме того, владельцами кластеров могут ограничиваться как объемы информации, обрабатываемой их кластерами, так и объемы, обрабатываемые отдельными рабочими станциями.

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде кластер 1 … кластер 2 … кластер M … … i=1,2…m 1 i=m 1 +1, m 1 +2…m 2 i=m M-1 +1, m M-1 +2…N Центр анализа данных x1x1 q2q2 q1q1 q m1 qiqi qNqN xNxN x2x2 xixi q i – время обработки 1 Мб данных i-й станцией х i – объем данных, передаваемый на i-ю станцию

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде. Формализация исходной проблемы Множество возможных альтернатив – определяется объемом данных х i, направляемых для обработки на i -ю станцию. Варьируемые параметры – вектор значений объема данных, направляемого для обработки на каждую станцию. Фиксированные независимые параметры – времена обработки q i 1 Мб данных i -й станцией, предельно допустимые объемы информации, которые могут быть обработаны i -й станцией P i, i=1,2…N и j -м кластером R j, j=1,2…M ; объем данных, подлежащий обработке X. Цель – минимизация суммарного времени загрузки всех станций Ограничения: суммарный объем обрабатываемых данных равен X, объем данных, обрабатываемый каждой i -й станцией больше или равен 0, но меньше или равен P i, объем данных, обрабатываемый каждым j -м кластером меньше или равен R j ; времена обработки данных кластерами равны.

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде. Математическая модель.

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде. Конкретная задача. Количество вычислительных кластеров M=3 Количество рабочих станций N=10 В первом кластере имеется 4 станции, во втором – 2, в третьем – 4. Времена обработки 1Мб данных станциями: i q i,сек Объем данных для обработки каждой станцией ограничен: i P i, Мб700 Объем данных для обработки каждым кластером ограничен : j123 P i, Мб Общий объем данных для обработки X=1000 Мб. Времена обработки данных кластерами должны совпадать

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде. Математическая модель конкретной задачи.

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде. Приведение модели к стандартной форме. Для приведения этой задачи к стандартной форме необходимо в ограничения вида с неотрицательной правой частью ввести дополнительные (остаточные) переменные:

1. Линейное программирование Искусственное начальное решение Размещение данных для обработки в распределенной вычислительной среде. Искусственное начальное базисное решение Переменных теперь 23, остаточных переменных – 13. Однако, на эти 13 остаточных переменных приходятся 16 уравнений, задающих ограничения. Действительно, если в формулировке задачи присутствуют ограничения вида равенств или неравенства вида, число уравнений оказывается больше остаточных переменных. В этом случае невозможно сформировать начальное допустимое базисное решение из остаточных переменных. В этом случае обычно применяют один из методов, основанных на использовании искусственных переменных Разработано два метода нахождения начального решения, которые используют искусственные переменные: М-метод (метод больших штрафов) двухэтапный метод

1. Линейное программирование М-метод нахождения искусственного начального решения. Запишем задачу ЛП в стандартной форме. Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем искусственную переменную r i, которая далее войдет в начальное базисное решение. Так как эта переменная искусственная, необходимо, чтобы она обратилась в ноль на следующих итерациях. Для этого в выражение целевой функции вводят штраф: к ней добавляют выражение +Mr i в случе минимизации целевой функции или –Mr i в случае максимизации.

1. Линейное программирование М-метод нахождения искусственного начального решения. Пример использования М-метода: исходная задача и стандартная форма (из кн. Х.Таха) min F(x 1, x 2 ); F(x 1, x 2 ) = 4x 1 +x 2 ; 3x 1 + x 2 = 3; 4x 1 + 3x 2 6; x 1 +2x 2 4; x 1 0; x 2 0. min F(x 1, x 2 ); F(x 1, x 2 ) = 4x 1 +x 2 ; 3x 1 + x 2 = 3; 4x 1 + 3x 2 – x 3 = 6; x 1 +2x 2 +x 4 =4; x 1 0; x 2 0; x 3 0; x 4 0;

1. Линейное программирование М-метод нахождения искусственного начального решения. Пример использования М-метода: введение искусственных переменных min F(x 1, x 2 ); F(x 1, x 2 ) = 4x 1 +x 2 ; 3x 1 + x 2 = 3; 4x 1 + 3x 2 – x 3 = 6; x 1 +2x 2 +x 4 =4; x 1 0; x 2 0; x 3 0; x 4 0; min F(x 1,x 2,r 1,r 2 ); F(x 1, x 2 ) = 4x 1 +x 2 +Mr 1 +Mr 2 ; 3x 1 + x 2 +r 1 = 3; 4x 1 + 3x 2 – x 3 +r 2 = 6; x 1 +2x 2 +x 4 =4; x 1 0; x 2 0; r 1 0; x 3 0; x 4 0; r 2 0;

1. Линейное программирование М-метод нахождения искусственного начального решения. Пример использования М-метода: симплекс-таблица В модифицированной задаче переменные x 4, r 1 и r 2 можно использовать в качестве начального допустимого базисного решения Номер урав- нения Fx1x1 x2x2 x3x3 r1r1 r2r2 x4x4 Ба- зис Ре- ше- ние M 0F r1r r2r x4x4 4 Решение: x 1 =0; x 2 =0; x 3 =0; r 1 =3; r 2 =6; x 4 =4. Однако, F-строка нуждается в согласовании: при полученных значениях переменных F=3M+6M=9M, а не 0. Это получилось потому, в этой с троке коэффициенты при r 1 и r 2 не равны 0.

1. Линейное программирование М-метод нахождения искусственного начального решения. Пример использования М-метода: измененная симплекс-таблица Умножим элементы строк r 1 и r 2 на M и сложим эти строки с нулевой F – строкой. Номер урав- нения Fx1x1 x2x2 x3x3 r1r1 r2r2 x4x4 Ба- зис Ре- ше- ние М-1+4М-М000F9M9M r1r r2r x4x4 4 Теперь значение F при значениях x 1 =0; x 2 =0; x 3 =0; r 1 =3; r 2 =6; x 4 =4 равно, как и следует 9М. Эта таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости.

1. Линейное программирование М-метод нахождения искусственного начального решения. Пример использования М-метода: решение Самостоятельно проделайте процедуру решения представленной задачи с использованием симплекс- таблицы. Убедитесь, что на первом шаге: в базис вводится переменная x 1 (из условия оптимальности: функция минимизируется и вводится переменная с наибольшим положительным коэффициентом в F-строке); из базиса исключается переменная r 1 (условие допустимости: отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально). На втором шаге вводимая и исключаемая переменные x 2 и r 2 соответственно. Окончательно получим оптимальное решение x 1 =2/5; x 2 =9/5; x 3 =1; F=17/5.

1. Линейное программирование М-метод нахождения искусственного начального решения. Некоторые замечания Использование штрафа M может не привести к исключению искусственных переменных после выполнения последней симплекс-итерации. Если исходная задача ЛП не имеет допустимого решения (например, система ограничений несовместна), то в конечной итерации хотя бы одна искусственная переменная будет иметь положительное значение. Величина M при реализации алгоритма на ЭВМ должна быть конечной и в то же время достаточно большой. Она должна быть настолько большой, чтобы успешно выполнять роль штрафа, но не слишком большой, чтобы не уменьшить точность вычислений, в которых участвуют как большие, так и малые числа. Правильный выбор значения M зависит от условия задачи. Опасность значительных ошибое округления при неправильном выборе М не позволяет применять М-метод в коммерческих программах, реализующих симплекс-метод. Вместо него на практике используется двухэтапный метод.

1. Линейное программирование Двухэтапный метод. Базовый алгоритм Найти допустимое базисное решение Записать задачу ЛП в стандартной форме. Добавить в ограничения необходимые искусственные переменные (как в М-методе). Решить задачу ЛП минимизации суммы искусственных переменных при имеющихся ограничениях. Если минимальное значение новой целевой функции больше 0, то завершить вычисления, так как исходная задача не имеет допустимого решения, Иначе использовать оптимальное решение, полученное на первом этапе, как начальное допустимое базисное решение исходной задачи. Решить модифицированную с учетом полученного базисного решения исходную задачу ЛП

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода. min F(x 1, x 2 ); F(x 1, x 2 ) = 4x 1 +x 2 ; 3x 1 + x 2 = 3; 4x 1 + 3x 2 – x 3 = 6; x 1 +2x 2 +x 4 =4; x 1 0; x 2 0; x 3 0; x 4 0; min U(r 1,r 2 ); U(r 1, r 2 ) = r 1 +r 2 ; 3x 1 + x 2 +r 1 = 3; 4x 1 + 3x 2 – x 3 +r 2 = 6; x 1 +2x 2 +x 4 =4; x 1 0; x 2 0; r 1 0; x 3 0; x 4 0; r 2 0;

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: симплекс-таблица В модифицированной задаче переменные x 4, r 1 и r 2 можно использовать в качестве начального допустимого базисного решения Номер урав- нения Ux1x1 x2x2 x3x3 r1r1 r2r2 x4x4 Ба- зис Ре- ше- ние U r1r r2r x4x4 4 Решение: x 1 =0; x 2 =0; x 3 =0; r 1 =3; r 2 =6; x 4 =4. Однако, U-строка нуждается в согласовании: при полученных значениях переменных U=3+6=9, а не 0. Это получилось потому, в этой строке коэффициенты при r 1 и r 2 не равны 0.

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: измененная симплекс- таблица Умножим элементы строк r 1 и r 2 на M и сложим эти строки с нулевой U – строкой. Номер урав- нения Ux1x1 x2x2 x3x3 r1r1 r2r2 x4x4 Ба- зис Ре- ше- ние U r1r r2r x4x4 4 Теперь значение F при значениях x 1 =0; x 2 =0; x 3 =0; r 1 =3; r 2 =6; x 4 =4 равно, как и следует 9М. Эта таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости.

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: оптимальное решение 1-го этапа Оптимальное решение выглядит следующим образом (проверьте): Номер урав- нения Ux1x1 x2x2 x3x3 r1r1 r2r2 x4x4 Ба- зис Ре- ше- ние U /53/5-1/50x1x1 3/ /5-4/53/50x2x2 6/ x4x4 1 Искусственные переменные исключены из базиса и их столбцы можно удалить из симплекс-таблицы.

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: измененная исходная задача Номер урав- нения Ux1x1 x2x2 x3x3 r1r1 r2r2 x4x4 Ба- зис Ре- ше- ние U /53/5-1/50x1x1 3/ /5-4/53/50x2x2 6/ x4x4 1 min F(x 1,x 2 ); F(x 1, x 2 ) = 4x 1 +x 2 ; x 1 + 1/5 x 3 = 3/5; x 1 0; x 2 0; x 2 – 3/5x 3 = 6/5; x 3 0; x 4 0; x 3 +x 4 =1;

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: симплекс-таблица измененной задачи Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 Ба- зис Ре- ше- ние F /50x1x1 3/ /50x2x2 6/ x4x4 1 Поскольку базисные переменные имеют ненулевые коэффициенты в F-строке, эту строку следует преобразовать Для этого вторую строку умножим на 4 и сложим с нулевой, а вторую – на 1 и также сложим с нулевой

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: начальная таблица второго этапа Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 Ба- зис Ре- ше- ние 01001/50F18/ /50x1x1 3/ /50x2x2 6/ x4x4 1 Так как решается задача минимизации, из условия оптимальности в базис вводим переменную x 3. Коэффициент при этой переменной в строке положительный и наибольший, следовательно – в целевой функции отрицателен. Из условия допустимости исключаем базисную переменную, для которой отношение правой части к положительному коэффициенту ведущего столбца минимально. Это – x 4.

1. Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: расчет нового базисного решения Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 Ба- зис Ре- ше- ние 01001/50F18/ /50x1x1 3/ /50x2x2 6/ x4x4 1 Новая ведущая строка = текущая строка / ведущий элемент. Для остальных строк: новая строка = текущая строка – ее коэффициент в ведущем столбце х новая ведущая строка

Номер урав- нения Fx1x1 x2x2 x3x3 x4x4 Ба- зис Ре- ше- ние /5F17/ /5x1x1 2/ /5x2x2 9/ x3x Линейное программирование Двухэтапный метод. Пример использования двухэтапного метода: оптимальное решение Данное решение является оптимальным, так как в нулевой строке нет переменной с положительным коэффициентом.

1. Линейное программирование Двухэтапный метод. Замечания по применению Удаление искусственных переменных в конце первого этапа имеет смысл только, если они являются небазисными. Возможна ситуация, когда в конце первого этапа они имеют нулевые значения, но остаются в базисе. В этом случае необходимо так изменить вычисления на втором этапе, чтобы эти искусственные переменные ни в одной итерации симплекс-метода не приняли положительные значения.

1. Линейное программирование Особые случаи применения симплекс-метода Вырожденность Альтернативные оптимальные решения Неограниченные решения Отсутствие допустимых решений

1. Линейное программирование Особые случаи применения симплекс-метода Вырожденность В ходе выполнения симплекс-метода проверка условия допустимости может привести к неоднозначному выбору исключаемой переменной В этом случае на следующей итерации одна или более базисных переменных примут нулевое значение и решение будет вырожденным Вырожденность означает, что в исходной задаче присутствует по крайней мере одно избыточное ограничение Пример: max F(x 1,x 2 )=3x 1 +9x 2 ; x 1 +4x 2 8; x 1 +2x 2 4 x 1, x 2 0

1. Линейное программирование Особые случаи применения симплекс-метода Вырожденность Оптимальное вырожденное решение x 1 +2x 2 4; F=3x 1 +9x 2 x2x2 x1x1 x 1 +4x 2 8; (избыточное)

1. Линейное программирование Особые случаи применения симплекс-метода Вырожденность Возможные последствия вырожденности: Зацикливание симплекс-метода (некоторая последовательность будет повторяться, не изменяя значения целевой функции и не приводя к завершению вычислительного процесса) В двух последовательных итерациях состав базисных и небазисных переменных может быть различен, но значения всех переменных и целевой функции не меняются. Тем не менее, останавливать вычисления нельзя (решение может быть временно вырожденным).

1. Линейное программирование Особые случаи применения симплекс-метода Альтернативные оптимальные решения Альтернативные оптимальные решения возникают, когда целевая функция принимает одно и то же оптимальное значение на некотором множестве точек границы области допустимых значений. Это бывает, когда прямая (в общем случае – гиперплоскость), представляющая целевую функцию параллельна прямой (гиперплоскости), соответствующей связывающему неравенству. Связывающее неравенство в точке оптимума выполняется как точное равенство. Симплекс-метод может найти угловые точки, затем можно найти остальные. Пример: max F(x 1,x 2 )=2x 1 +4x 2 ; x 1 +2x 2 5; x 1 +x 2 4 x 1, x 2 0

1. Линейное программирование Особые случаи применения симплекс-метода Альтернативные оптимальные решения x 1 +2x 2 5; F=2x 1 +4x 2 x2x2 x1x1 x 1 +x 2 4;

1. Линейное программирование Особые случаи применения симплекс-метода Неограниченные решения Если в процессе поиска решения значения переменных могут неограниченно возрастать без нарушения ограничений, то пространство допустимых решений не ограничено по крайней мере по одному направлению. В результате этого целевая функция может неограниченно возрастать (убывать в задачах минимизации). Неограниченность решения означает, что модель задачи разработана некорректно. Пример: max F(x 1,x 2 )=2x 1 +x 2 ; x 1 – x 2 4; 2x 1 6 x 1, x 2 0

1. Линейное программирование Особые случаи применения симплекс-метода Неограниченные решения 2x 1 6; F=2x 1 +x 2 x2x2 x1x1 x 1 -x 2 4;

1. Линейное программирование Особые случаи применения симплекс-метода Неограниченные решения Правило выявления неограниченности решения: Если на какой-либо симплекс-итерации коэффициенты в ограничениях для какой-нибудь небазисной переменной будут неположительными, значит пространство решений не ограничено в направлении возрастания этой переменной. Если, кроме того, коэффициент этой переменной в F-строке отрицателен (задача максимизации) или положителен (в задаче минимизации), целевая функция не ограничена.

1. Линейное программирование Особые случаи применения симплекс-метода Отсутствие допустимых решений Если ограничения задачи ЛП несовместны, то задача не имеет допустимых решений. Если все ограничения имеют вид неравенств типа с неотрицательными правыми частями, то дополнительные переменные всегда могут составить допустимое решение. Для других типов ограничений используются искусственные переменные и если пространство допустимых решений является пустым, то в решении будет присутствовать хотя бы одна положительная искусственная перемменная. Отсутствие допустимых решений свидетельствует о некорректной формулировке задачи. Пример: max F(x 1,x 2 )=3x 1 +2x 2 ; 2x 1 + x 2 2; 3x 1 + 4x 2 12; x 1, x 2 0

1. Линейное программирование Особые случаи применения симплекс-метода Отсутствие допустимых решений 2x 1 +x 2 2; F=3x 1 +2x 2 x2x2 x1x1 3x 1 +4x 2 12;

1. Линейное программирование Матричное представление стандартной задачи ЛП В матричной форме стандартную задачу ЛП можно представить следующим образом: max F =Cх или min F =Cх при ограничениях вида (A,I)х=b, x0, где: I – единичная матрица размера m x m, х=(x 1,x 2,…,x n ) T, C=(c 1,c 2,…c n )

1. Линейное программирование Матричное представление стандартной задачи ЛП пример max F=2x 1 +3x 2 x 1 +x 2 5, x 1 +2x 2 = 7, 5x 1 -x 2 9, x 1,x 2 0. Эта задача имеет n=6 переменных и m=3 ограничений x 3 и x 6 – дополнительные, x 4 и x 5 – искусственные переменные

1. Линейное программирование Матричное представление стандартной задачи ЛП Базисные решения Для системы из m уравнений (A,I)х=b с n неизвестными (m

1. Линейное программирование Матричное представление симплекс-таблиц Мы утверждаем, что конечное оптимальное решение задачи ЛП достигается в крайних точках пространства решений. Все крайние точки можно определить алгебраически как базисные решения системы линейных уравнений (A,I)х=b, х 0. Алгоритм симплекс-метода предполагает последовательный переход от одной крайней точки к другой (от одного допустимого базисного решения к другому), когда значение целевой функции не ухудшается, и так до тех пор, пока не будет достигнуто оптимальное решение (во всех соседних крайних точках значение целевой функции будет хуже, чем в достигнутой). Для представления симплекс-таблицы в матричной форме в стандартной задаче ЛП: max F =Cх при ограничениях (A,I)х=b, x 0, разобьем вектор x на два вектора х I и x II,таких, что вектор x II соответствует начальному базису B, то есть является начальным допустимым базисным решением; вектор C также разделим на два вектора CI и CII в соответствии с векторами х I и x II.

1. Линейное программирование Матричное представление симплекс-таблиц Тогда стандартную задачу ЛП можно записать в следующем виде: Для любой симплексной итерации будем обозначать через x B текущий базисный вектор переменных, а через C B – вектор коэффициентов целевой функции, соответствующий этому базису. Так как все небазисные переменные равны 0, стандартная задача ЛП сводится к задаче с целевой функцией F =C B x B и ограничениями Bx B = b. Текущее решение удовлетворяет уравнению:

1. Линейное программирование Матричное представление симплекс-таблиц Преобразованную симплекс-таблицу получаем, домножив обе части на B -1 : Номер уравнения FxIxI x II Базис Решение 01C B B -1 A-C I C B B -1 -C II FC B B -1 b 1…m0B -1 AB -1 xBxB B -1 b

1. Линейное программирование Матричное представление симплекс-таблиц Представленная симплекс-таблица является основой всех вычислительных алгоритмов линейного программирования. В симплекс-методе решение переходит от одного базиса B к следующему B след путем замены в B базисного вектора (исключаемого) на небазисный (вводимый). Условие оптимальности. Вводимой переменной в задаче максимизации (минимизации) целевой функции является небазисная переменная, имеющая наибольший по модулю отрицательный (положительный) коэффициент в F-строке. Этот коэффициент равен C B B -1 P j - c j, где P j – j-й столбец матрицы (A,I), c j – j-й элемент вектора С. Условие допустимости. В качестве исключаемой выбирается базисная переменная, для которой отношение правой части ограничения к положительному коэффициенту ведущего k-го столбца минимально (здесь x k -вводимая в базис переменная, P k -вводимый вектор, определяемые из условия оптимальности):

1. Линейное программирование Модифицированный симплекс-метод В модифицированном симплекс-методе вместо процедуры преобразования строк с помощью метода Гаусса-Жордана используется обратная матрица B -1. В симплекс-методе последовательные базисы B и B след различаются только одним вектор-столбцом, что позволяет использовать мультипликативное представление обратной матрицы: Матрицу E можно определить как m-мерную единичную матрицу, у которой r-й столбец заменен следующим столбцом: Здесь P j и P r – вводимый в базис и исключаемый столбец соответственно. Доказательство можно найти в книге Х.А.Таха

1. Линейное программирование Модифицированный симплекс-метод Рассмотрим пример решения задачи ЛП (Х.А.Таха): максимизировать F=x 1 +4x 2 +7x 3 +5x 4 при ограничениях: 2x 1 +x 2 +2x 3 +4x 4 =10, 3x 1 -x 2 -2x 3 +6x 4 =5 x 1,x 2,x 3,x 4 0 Пусть B=(P 1,P 2 ) является допустимым базисом. Покажем, что решение B не является оптимальным. Найдем вводимый в базис и исключаемый из него векторы и B след

1. Линейное программирование Модифицированный симплекс-метод B=(P 1,P 2 ), то есть x B =( x 1,x 2 ) T и C B =(1,4)

1. Линейное программирование Модифицированный симплекс-метод Так как целевая функция максимизируется, наличие отрицательного коэффициента при 4-й переменной говорит о том, что решение неоптимально. Значение целевой функции можно улучшить, если ввести в базис переменную x 4. Вычислим коэффициенты при небазисных переменных x 3 и x 4 в F -строке:

1. Линейное программирование Модифицированный симплекс-метод Найдем исключаемую переменную. Для нахождения выражения вычисляем вектор B -1 P 4 имеет один строго положительный элемент = 2, исключается переменная x 1 и значение вводимой переменной будет равно:

1. Линейное программирование Модифицированный симплекс-метод Итак, в базисе B вектор P 1 будет заменен на P 2, что приводит к новому базису Новое значение целевой функции F = старое значение (19) – коэффициент при вводимой переменной x 4 в F-строке (- 3) х значение вводимой переменной (3/2) = 23,5

-

2.Сетевые модели