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

Содержание

Слайд 2

Введение

Введение

Слайд 3

0. Введение. Общие сведения.

Объем курса – 34 часа лекции 24 часа лабораторные занятия 14

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

Слайд 4

0. Введение. Цели и задачи дисциплины.

Ознакомить с фундаментальными основами дисциплины «Исследование операций»,

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

Слайд 5

0. Введение. Литература.

Основная
Таха Х. Введение в исследование операций.: Пер. с англ. –

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

Слайд 6

0. Введение. 0.1. Предмет дисциплины.

Исследование операций – дисциплина, изучающая методы построения последовательности действий

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

Слайд 7

0. Введение. 0.1 Основные понятия.

Изменяемые переменные (переменные решения – decision variables) – переменные,

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

Слайд 8

0. Введение. 0.1. Основные понятия.

Ограничения (constraints) – неравенства или равенства, определяющие область допустимых

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

Слайд 9

0. Введение. 0.1. Основные понятия.

Математическая модель (model) – результат формализации задачи исследования операций.

0. Введение. 0.1. Основные понятия. Математическая модель (model) – результат формализации задачи
Включает в себя множество изменяемых переменных, целевую функцию и ограничения, записанные в виде математических соотношений или заданные соответствующими вычислительными алгоритмами.
Параметры модели (parameters) – множество параметров {ak, bj, csj, ui}, входящих в структуру целевой функции и функций ограничений. Значения этих параметров определяются условием решаемой задачи и должны быть заданы при формировании математической модели.

Слайд 10

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов.

Предположим, что

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

Слайд 11

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Варьируемые

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Варьируемые
параметры и целевая функция

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

Слайд 12

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Структура

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Структура
месячных затрат (Velcom и МТС)

Затраты в месяц по i-му тарифному плану для операторов Velcom и МТС определяются следующим образом: здесь Tij =vjtij– стоимость j-го типа трафика объема vj, если он направлен на подключение по i-му тарифному плану (трафик направляется, если существует подключение по этому плану, т.е. xi=1, и тариф tij по этому плану наименьший из тарифов существующих подключений);
Bi – ежемесячная абонентская плата по i-му плану;
Pi = Si/d – ежемесячные отчисления за стоимость телефона Si для i-го подключения из расчета окупаемости за d месяцев.

Слайд 13

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Структура

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Структура
месячных затрат (Belcel)

Затраты в месяц по i-му тарифному плану для оператора Belcel определяются следующим образом: здесь Mi – ежемесячная оплата за разговоры определяется как
Tij - стоимость j-го трафика, если он направлен на подключение по i-му тарифному плану;
Bi – ежемесячная предоплата по i-му плану;
Pi = Si/d – ежемесячные отчисления за стоимость телефона Si для i-го подключения из расчета окупаемости за d месяцев.

Слайд 14

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

Ограничения

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

Слайд 15

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

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

Слайд 16

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Алгоритм

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

Слайд 17

0. Введение. 0.2. Задача выбора операторов мобильной связи и тарифных планов. Некоторые

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

Слайд 18

0. Введение. 0.3. Многовариантность математических моделей. Задача нахождения коробки максимального объема заданной

0. Введение. 0.3. Многовариантность математических моделей. Задача нахождения коробки максимального объема заданной
площади поверхности

Рассмотрим почти «школьную» задачу построения оптимального решения: найти длину 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)

Слайд 19

0. Введение. 0.3. Многовариантность математических моделей. Задача нахождения коробки требуемого объема заданной

0. Введение. 0.3. Многовариантность математических моделей. Задача нахождения коробки требуемого объема заданной
площади поверхности
Модифицируем задачу: требуется найти длину 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.

Слайд 20

0. Введение. 0.3. Многовариантность математических моделей. Задача нахождения коробки требуемого объема заданной

0. Введение. 0.3. Многовариантность математических моделей. Задача нахождения коробки требуемого объема заданной
площади поверхности
Переформулируем математическую модель:
Варьируемые параметры - 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 без малейших проблем, хотя, очевидно, что она имеет несколько решений и соответственно целевая функция имеет не один минимум.
Кстати, при решении ограничения можно не учитывать, так как априори очевидно, что минимум функции лежит внутри области допустимых значений переменных a и b.

Слайд 21

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

0. Введение. 0.4. Последовательность решения задач исследования операций. Постановка задачи проектирования просветляющего
покрытия
Характерный пример более сложной задачи – нахождение оптимальных параметров широкополосного просветляющего оптического покрытия

λmax

λmin

R

θ1, α1

θ2, α2

θ3, α2
Требуется минимизировать энергетический коэффициент отражения от покрытия в диапазоне длин волн, углов падения и поляризации

Слайд 22

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

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

Слайд 23

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

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

Слайд 24

0. Введение. 0.5. Структурная и параметрическая оптимизация

Процедура поиска оптимального решения может быть

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

Слайд 25

0. Введение. 0.6. Методы исследования операций

Все модели исследования операций можно разделить

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

Слайд 26

0. Введение. 0.6. Методы исследования операций Наука и искусство

Этапы реализации методов исследования операций:
Формализация

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

Слайд 27

0. Введение. 0.7. Этапы реализации методов исследования операций

Формализация исходной проблемы
предполагает исследование

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

Слайд 28

0. Введение. 0.7. Этапы реализации методов исследования операций

Поиск оптимального решения (решение

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

Слайд 29

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

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

Слайд 30

1. Линейное программирование 1.1. Постановка задачи

Линейное программирование (ЛП) – это метод математического моделирования,

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

Слайд 31

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

Телекоммуникационная

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

Слайд 32

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

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

Кроме того, количество портов на сервере удаленного доступа ограничено 32 портами, что не позволяет оказывать услуги доступа в Internet более чем 480 клиентам.

Spam Networks

Fool Communications

Пользователи Internet

Хостинг веб-сайтов

Коммутируемые
линии

Internet

Выделенная линия

Слайд 33

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

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

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

Слайд 34

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

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

max F(x1, x2);
F(x1, x2) = 8x1+6x2;
x1+4 x2 ≤ 2048;
2x1+ x2 ≤ 2048;
x2 ≤ 480;
x1 ≥ 0;
x2 ≥ 0.

Данная модель – классическая модель линейного программирования.
Замечание: хотя мы и назвали задачу: «оптимизация структуры услуг…», это – типичная задача параметрической оптимизации.
Рассмотрим графическое решение этой модели (модель решается в электронной таблице Excel: см. соответствующую книгу).

Слайд 35

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

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

293

878

Месячный доход от хостинга $8

Месячный доход от подключения $6

Слайд 36

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

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

0

1024

Месячный доход от хостинга $8

Месячный доход от подключения снижаем до $3,9

Слайд 37

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

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

480

128

Месячный доход от хостинга снизился до $1,3

Месячный доход от подключения $6

Слайд 38

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

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

293

878

Доступный объем входящего трафика – 2048 Кбит/с

Доступный объем исходящего трафика – 2048 Кбит/с

Слайд 39

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

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

480

124

Доступный объем входящего трафика – 2048 Кбит/с

Доступный объем исходящего трафика сократился до 728 Кбит/с

Слайд 40

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

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

0

2048

Доступный объем входящего трафика – 2048 Кбит/с

Доступный объем исходящего трафика увеличился до 4096 Кбит/с

Слайд 41

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

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

728

4096

Слайд 42

1. Линейное программирование. 1.4.Принципы построения аналитических методов решения задачи ЛП Оптимизация структуры

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

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

Слайд 43

1. Линейное программирование. 1.4.Принципы построения аналитических методов решения задачи ЛП Методика поиска

1. Линейное программирование. 1.4.Принципы построения аналитических методов решения задачи ЛП Методика поиска
оптимального решения

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

Слайд 44

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП шаг 1

Все ограничения (включая ограничения неотрицательности

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

Слайд 45

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП шаг 2

Все варьируемые переменные должны быть

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

Слайд 46

1. Линейное программирование. 1.5.Стандартная форма задачи ЛП шаг 3

Целевую функцию следует минимизировать или

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

Слайд 47

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

max F(x1,

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

max F(x1, x2);
F(x1, x2) = 8x1 + 6x2;
x1+4 x2 + y1= 2048;
2x1+ x2 + y2 = 2048;
x2 + y3 = 480;
x1 ≥ 0; x2 ≥ 0;
y1 ≥ 0; y2≥ 0; y3 ≥ 0;

Слайд 48

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

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

Слайд 49

1. Линейное программирование. 1.6.Понятие базисного решения задачи ЛП Допустимые базисные решения

Задача ЛП в

1. Линейное программирование. 1.6.Понятие базисного решения задачи ЛП Допустимые базисные решения Задача
стандартной форме содержит m линейных равенств с n неизвестными переменными (mРазделим n переменных на два множества:
n-m переменных, которые положим равными нулю;
оставшиеся m переменных, значения которых определяются как решение системы из m линейных уравнений с m переменными.
Если решение полученной СЛАУ единственное, то соответствующие m переменных называют базисными, а остальные n-m нулевых переменных - небазисными. В этом случае результирующие значения переменных составляют базисное решение.
Если все переменные принимают неотрицательные значения, то такое базисное решение называют допустимым, в противном случае – недопустимым.
Нетрудно видеть, что количество всех допустимых базовых решений для m уравнений c n неизвестными не превосходит

Слайд 50

1. Линейное программирование. 1.6.Понятие базисного решения задачи ЛП Свободные переменные и базисные решения

Свободные

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

Слайд 51

1. Линейное программирование. 1.7. Основы симплекс-метода Идея алгоритма

Можно доказать, что решение задачи ЛП

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

Слайд 52

1. Линейное программирование. 1.7. Основы симплекс-метода Оптимизация структуры телекоммуникационных услуг. Математическая модель.

Вспомним математическую

1. Линейное программирование. 1.7. Основы симплекс-метода Оптимизация структуры телекоммуникационных услуг. Математическая модель.
формулировку задачи

x1 – число сопровождаемых сайтов, x2 – число подключаемых пользователей к Internet, x3 – неиспользуемая пропускная способность спутникового канала, x4 – неиспользуемая пропускная способность исходящего канала, x4 – неиспользуемая емкость портов

Слайд 53

1. Линейное программирование. 1.7. Основы симплекс-метода Оптимизация структуры телекоммуникационных услуг. Система уравнений

Перепишем уравнения

1. Линейное программирование. 1.7. Основы симплекс-метода Оптимизация структуры телекоммуникационных услуг. Система уравнений
в виде:

x1 – число сопровождаемых сайтов, x2 – число подключаемых пользователей к Internet, x3 – неиспользуемая пропускная способность спутникового канала, x4 – неиспользуемая пропускная способность исходящего канала, x4 – неиспользуемая емкость портов

Слайд 54

1. Линейное программирование. 1.7. Основы симплекс-метода Исходная таблица

Задачу ЛП в стандартной форме можно

1. Линейное программирование. 1.7. Основы симплекс-метода Исходная таблица Задачу ЛП в стандартной
представить в виде таблицы:

Решение: x1=0; x2=0; x3=2048; x4=2048; x5=480.

Слайд 55

1. Линейное программирование. 1.7. Основы симплекс-метода Начальное допустимое базисное решение на графике

293

878

Месячный доход

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

Месячный доход от подключения $6

Слайд 56

1. Линейное программирование. 1.7. Основы симплекс-метода Определение вводимой в базис переменной

Вводим в базис

1. Линейное программирование. 1.7. Основы симплекс-метода Определение вводимой в базис переменной Вводим
переменную, отрицательный коэффициент при которой в F-строке таблицы (положительный коэффициент в целевой функции) наибольший по абсолютной величине. Это - x1.

Слайд 57

293

878

Месячный доход от подключения $6

1. Линейное программирование. 1.7. Основы симплекс-метода Графическое нахождение наибольшего

293 878 Месячный доход от подключения $6 1. Линейное программирование. 1.7. Основы
значения, которое может принять вводимая переменная.

Месячный доход от хостинга $8

Месячный доход от подключения $6

X1=1024

Слайд 58

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

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

Симплекс-метод должен определять новую точку алгебраически.
Эта точка – точка пересечения прямых, соответствующих ограничениям, с координатной осью, соответствующей вводимой переменной (в данном случае – с осью 0x1.
Алгебраически эта точка – отношение правой части равенства (столбца «Решение») к коэффициенту при вводимой переменной (x1).
Разумеется, нас интересуют только неотрицательные отношения.
Чтобы точка лежала внутри ОДЗ надо из всех положительных выбрать наименьшее значение

Слайд 59

293

878

Месячный доход от подключения $6

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

293 878 Месячный доход от подключения $6 1. Линейное программирование. 1.7. Основы
значения, которое может принять вводимая переменная: графическая иллюстрация.

Месячный доход от хостинга $8

Месячный доход от подключения $6

X1=1024

X1=2048

Слайд 60

1. Линейное программирование. 1.7. Основы симплекс-метода Выбор исключаемой из базиса переменной

Исключается та переменная,

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

Слайд 61

1. Линейное программирование. 1.7. Основы симплекс-метода Определение ведущего столбца, ведущей строки и ведущего

1. Линейное программирование. 1.7. Основы симплекс-метода Определение ведущего столбца, ведущей строки и
элемента

Ведущий столбец – столбец, соответствующий вводимой в базис переменной.
Ведущая строка – строка, соответствующая исключаемой переменной.
Ведущий элемент – элемент, находящийся на пересечении ведущего столбца и ведущей строки.

Слайд 62

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 1.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 1.
новой ведущей строки
Новая ведущая строка = Текущая ведущая строка / ведущий элемент

Слайд 63

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)

Слайд 64

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)
Нулевая строка: коэффициент в ведущем столбце = -8.

Слайд 65

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)
Первая строка: коэффициент в ведущем столбце = 1.

Слайд 66

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)
Третья строка: коэффициент в ведущем столбце = 0.

Слайд 67

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление нового базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)
Третья строка: коэффициент в ведущем столбце = 0.

Решение: x1=1024; x2=0; x3=1024; x4=0; x5=480.

Слайд 68

293

878

Месячный доход от подключения $6

1. Линейное программирование. 1.7. Основы симплекс-метода Новое базисное решение

293 878 Месячный доход от подключения $6 1. Линейное программирование. 1.7. Основы
на графике.

Месячный доход от хостинга $8

Месячный доход от подключения $6

X1=1024

Слайд 69

1. Линейное программирование. 1.7. Основы симплекс-метода Определение вводимой в базис переменной

Вводим в базис

1. Линейное программирование. 1.7. Основы симплекс-метода Определение вводимой в базис переменной Вводим
переменную, отрицательный коэффициент при которой в F-строке таблицы (положительный коэффициент в целевой функции) наибольший по абсолютной величине. Это - x2.

Слайд 70

1. Линейное программирование. 1.7. Основы симплекс-метода Определение исключаемой переменной

Находим отношение правой части равенства

1. Линейное программирование. 1.7. Основы симплекс-метода Определение исключаемой переменной Находим отношение правой
(столбца «Решение») к коэффициенту при вводимой переменной (x2).
Рассматриваются только неотрицательные отношения.
Чтобы точка лежала внутри ОДЗ надо из всех положительных выбрать наименьшее значение

Слайд 71

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление следующего базисного решения: шаг 1.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление следующего базисного решения: шаг 1.
новой ведущей строки
Новая ведущая строка = Текущая ведущая строка / ведущий элемент

Слайд 72

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление следующего базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление следующего базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)

Слайд 73

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление следующего базисного решения: шаг 2.

Вычисление элементов

1. Линейное программирование. 1.7. Основы симплекс-метода Вычисление следующего базисного решения: шаг 2.
остальных строк
Новая строка = Текущая строка – (Ее коэффициент в ведущем столбце х Новая ведущая строка)
Результат:

Решение: x1=878; x2=293; x3=0; x4=0; x5=187.

Слайд 74

293

878

Месячный доход от подключения $6

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

293 878 Месячный доход от подключения $6 1. Линейное программирование. 1.7. Основы
решения.

Месячный доход от хостинга $8

Месячный доход от подключения $6

Слайд 75

1. Линейное программирование. 1.8. Анализ решения, полученного симплекс-методом Оптимальность решения

Так как отрицательных коэффициентов

1. Линейное программирование. 1.8. Анализ решения, полученного симплекс-методом Оптимальность решения Так как
в F – строке больше нет, полученное решение является оптимальным
Оптимальное число поддерживаемых сайтов x1=878
Оптимальное число пользователей Internet x2=293

Решение: x1=878; x2=293; x3=0; x4=0; x5=187.

Слайд 76

1. Линейное программирование. 1.8. Анализ решения, полученного симплекс-методом Дефицитные ресурсы

Неиспользованный входящий трафик x3=0
Неиспользованный

1. Линейное программирование. 1.8. Анализ решения, полученного симплекс-методом Дефицитные ресурсы Неиспользованный входящий
входящий трафик x4=0
Эти ресурсы являются дефицитными, и увеличение объема разрешенного входящего и исходящего трафика приведет к улучшению решения (получению дополнительного дохода)

Решение: x1=878; x2=293; x3=0; x4=0; x5=187.

Слайд 77

1. Линейное программирование. 1.8. Анализ решения, полученного симплекс-методом Недефицитные ресурсы

Неиспользованная емкость портов сервера

1. Линейное программирование. 1.8. Анализ решения, полученного симплекс-методом Недефицитные ресурсы Неиспользованная емкость
удаленного доступа (возможное число дополнительных подключений) x5=187
Этот ресурс не является дефицитными, и увеличение числа портов при данных объемах входящего и исходящего трафика не приведет к улучшению решения (получению дополнительного дохода)

Решение: x1=878; x2=293; x3=0; x4=0; x5=187.

Слайд 78

1. Линейное программирование. 1.9. Алгоритм симплекс-метода Базовый алгоритм

Найти начальное допустимое базисное решение (полный

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

Слайд 79

1. Линейное программирование. 1.9. Алгоритм симплекс-метода Правила выбора вводимых и исключаемых переменных

Условие оптимальности.

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

Слайд 80

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

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

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

Слайд 81

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

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

кластер 1


кластер 2


кластер M



i=1,2…m1

i=m1+1, m1+2…m2

i=mM-1+1, mM-1+2…N

Центр анализа данных

q2

q1

qm1

qi

qN

qi – время обработки 1 Мб данных i-й станцией

хi – объем данных, передаваемый на i-ю станцию

Слайд 82

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

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

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

Слайд 83

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

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

Слайд 84

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

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

Количество вычислительных кластеров M=3
Количество рабочих станций N=10
В первом кластере имеется 4 станции, во втором – 2, в третьем – 4.
Времена обработки 1Мб данных станциями:

Объем данных для обработки каждой станцией ограничен:

Объем данных для обработки каждым кластером ограничен :

Общий объем данных для обработки X=1000 Мб.
Времена обработки данных кластерами должны совпадать

Слайд 85

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

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

Слайд 86

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

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

Для приведения этой задачи к стандартной форме необходимо в ограничения вида ≤ с неотрицательной правой частью ввести дополнительные (остаточные) переменные:

Слайд 87

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

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

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

Слайд 88

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения.

Запишем задачу ЛП в

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

Слайд 89

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:
исходная задача и стандартная форма (из кн. Х.Таха)

min F(x1, x2);
F(x1, x2) = 4x1+x2;
3x1+ x2 = 3;
4x1+ 3x2 ≥ 6;
x1+2x2 ≤ 4;
x1 ≥ 0;
x2 ≥ 0.

min F(x1, x2);
F(x1, x2) = 4x1+x2;
3x1+ x2 = 3;
4x1+ 3x2 – x3 = 6;
x1+2x2+x4=4;
x1 ≥ 0; x2 ≥ 0;
x3 ≥ 0; x4 ≥ 0;

Слайд 90

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:
введение искусственных переменных

min F(x1, x2);
F(x1, x2) = 4x1+x2;
3x1+ x2 = 3;
4x1+ 3x2 – x3 = 6;
x1+2x2+x4=4;
x1 ≥ 0; x2 ≥ 0;
x3 ≥ 0; x4 ≥ 0;

min F(x1,x2,r1,r2);
F(x1, x2) = 4x1+x2+Mr1+Mr2;
3x1+ x2+r1= 3;
4x1+ 3x2 – x3 +r2= 6;
x1+2x2+x4=4;
x1 ≥ 0; x2 ≥ 0; r1 ≥0;
x3 ≥ 0; x4 ≥ 0; r2 ≥0;

Слайд 91

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:
симплекс-таблица

В модифицированной задаче переменные x4, r1 и r2 можно использовать в качестве начального допустимого базисного решения

Решение: x1=0; x2=0; x3=0; r1=3; r2=6; x4=4.
Однако, F-строка нуждается в согласовании: при полученных значениях переменных F=3M+6M=9M, а не 0. Это получилось потому, в этой с троке коэффициенты при r1 и r2 не равны 0.

Слайд 92

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:
измененная симплекс-таблица

Умножим элементы строк r1 и r2 на M и сложим эти строки с нулевой F – строкой.

Теперь значение F при значениях x1=0; x2=0; x3=0; r1=3; r2=6; x4=4 равно, как и следует 9М.
Эта таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости.

Слайд 93

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:

1. Линейное программирование. 1.11. М-метод нахождения искусственного начального решения. Пример использования М-метода:
решение

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

Слайд 94

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

Использование штрафа

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

Слайд 95

1. Линейное программирование. 1.12. Двухэтапный метод. Базовый алгоритм

Найти допустимое базисное решение
Записать задачу

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

Слайд 96

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода.

min F(x1, x2);
F(x1,

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

min U(r1,r2);
U(r1, r2) = r1+r2;
3x1+ x2+r1= 3;
4x1+ 3x2 – x3 +r2= 6;
x1+2x2+x4=4;
x1 ≥ 0; x2 ≥ 0; r1 ≥0;
x3 ≥ 0; x4 ≥ 0; r2 ≥0;

Слайд 97

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: симплекс-таблица

В модифицированной

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: симплекс-таблица В
задаче переменные x4, r1 и r2 можно использовать в качестве начального допустимого базисного решения

Решение: x1=0; x2=0; x3=0; r1=3; r2=6; x4=4.
Однако, U-строка нуждается в согласовании: при полученных значениях переменных U=3+6=9, а не 0. Это получилось потому, в этой строке коэффициенты при r1 и r2 не равны 0.

Слайд 98

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: измененная симплекс-таблица

Умножим

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: измененная симплекс-таблица
элементы строк r1 и r2 на M и сложим эти строки с нулевой U – строкой.

Теперь значение F при значениях x1=0; x2=0; x3=0; r1=3; r2=6; x4=4 равно, как и следует 9М.
Эта таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости.

Слайд 99

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: оптимальное решение

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: оптимальное решение
1-го этапа

Оптимальное решение выглядит следующим образом (проверьте):

Искусственные переменные исключены из базиса и их столбцы можно удалить из симплекс-таблицы.

Слайд 100

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: измененная исходная

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: измененная исходная
задача

min F(x1,x2); F(x1, x2) = 4x1+x2;
x1+ 1/5 x3= 3/5; x1 ≥ 0; x2 ≥ 0;
x2 – 3/5x3 = 6/5; x3 ≥ 0; x4 ≥ 0;
x3+x4=1;

Слайд 101

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: симплекс-таблица измененной

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: симплекс-таблица измененной
задачи

Поскольку базисные переменные имеют ненулевые коэффициенты в F-строке, эту строку следует преобразовать
Для этого вторую строку умножим на 4 и сложим с нулевой, а вторую – на 1 и также сложим с нулевой

Слайд 102

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: начальная таблица

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: начальная таблица
второго этапа

Так как решается задача минимизации, из условия оптимальности в базис вводим переменную x3. Коэффициент при этой переменной в строке положительный и наибольший, следовательно – в целевой функции отрицателен.
Из условия допустимости исключаем базисную переменную, для которой отношение правой части к положительному коэффициенту ведущего столбца минимально. Это – x4.

Слайд 103

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: расчет нового

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: расчет нового
базисного решения

Новая ведущая строка = текущая строка / ведущий элемент.
Для остальных строк: новая строка = текущая строка – ее коэффициент в ведущем столбце х новая ведущая строка

Слайд 104

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: оптимальное решение

Данное

1. Линейное программирование. 1.12. Двухэтапный метод. Пример использования двухэтапного метода: оптимальное решение
решение является оптимальным, так как в нулевой строке нет переменной с положительным коэффициентом.

Слайд 105

1. Линейное программирование. 1.12. Двухэтапный метод. Замечания по применению

Удаление искусственных переменных в

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

Слайд 106

1. Линейное программирование. 1.13. Особые случаи применения симплекс-метода

Вырожденность
Альтернативные оптимальные решения
Неограниченные решения
Отсутствие допустимых

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

Слайд 107

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

В ходе выполнения симплекс-метода

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

Слайд 108

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

Оптимальное вырожденное решение

x1+2x2 ≤

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

F=3x1+9x2

x2

x1

x1+4x2 ≤ 8; (избыточное)

Слайд 109

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

Возможные последствия вырожденности:
Зацикливание симплекс-метода

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

Слайд 110

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

Альтернативные оптимальные

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

Слайд 111

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

x1+2x2 ≤

1. Линейное программирование. 1.13. Особые случаи применения симплекс-метода Альтернативные оптимальные решения x1+2x2
5;

F=2x1+4x2

x2

x1

x1+x2 ≤ 4;

Слайд 112

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

Если в процессе

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

Слайд 113

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

2x1 ≤ 6;

F=2x1+x2

1. Линейное программирование. 1.13. Особые случаи применения симплекс-метода Неограниченные решения 2x1 ≤

x2

x1

x1-x2 ≤ 4;

Слайд 114

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

Правило выявления неограниченности

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

Слайд 115

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

Если ограничения

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

Слайд 116

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

2x1+x2 ≤

1. Линейное программирование. 1.13. Особые случаи применения симплекс-метода Отсутствие допустимых решений 2x1+x2
2;

F=3x1+2x2

x2

x1

3x1+4x2 ≥ 12;

Слайд 117

1. Линейное программирование. 1.14. Матричное представление стандартной задачи ЛП

В матричной форме стандартную

1. Линейное программирование. 1.14. Матричное представление стандартной задачи ЛП В матричной форме
задачу ЛП можно представить следующим образом: max F=Cх или min F=Cх при ограничениях вида (A,I)х=b, x≥0, где: I – единичная матрица размера m x m, х=(x1,x2,…,xn)T, C=(c1,c2,…cn)

Слайд 118

1. Линейное программирование. 1.14. Матричное представление стандартной задачи ЛП пример

max F=2x1+3x2 x1+x2 ≥ 5, x1+2x2

1. Линейное программирование. 1.14. Матричное представление стандартной задачи ЛП пример max F=2x1+3x2
= 7, 5x1-x2 ≤ 9, x1,x2 ≥ 0.

Эта задача имеет n=6 переменных и m=3 ограничений
x3 и x6 – дополнительные, x4 и x5 – искусственные переменные

Слайд 119

1. Линейное программирование. 1.14. Матричное представление стандартной задачи ЛП Базисные решения

Для системы из

1. Линейное программирование. 1.14. Матричное представление стандартной задачи ЛП Базисные решения Для
m уравнений (A,I)х=b с n неизвестными (mОпределим матрицу B размером m x m, состоящую из столбцов матрицы (A,I), соответствующих элементам вектора xB.
Если присвоить оставшимся элементам вектора x нулевые значения, то система (A,I)х=b будет сведена к системе BхB=b
Если столбцы матрицы B формируют в m-мерном векторном пространстве базис (т.е. det(B)≠0, эти вектор-столбцы линейно независимы и матрица B невырожденная), то мы имем единственное решение этой системы: хB=B-1b
В этом случае хB является базисным решением системы (A,I)х=b
Если выполняется неравенство хB=B-1b ≥ 0, то хB будет допустимым базисным решением.

Слайд 120

1. Линейное программирование. 1.15. Матричное представление симплекс-таблиц

Мы утверждаем, что конечное оптимальное решение

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

Слайд 121

1. Линейное программирование. 1.15. Матричное представление симплекс-таблиц

Тогда стандартную задачу ЛП можно записать

1. Линейное программирование. 1.15. Матричное представление симплекс-таблиц Тогда стандартную задачу ЛП можно
в следующем виде:

Для любой симплексной итерации будем обозначать через xB текущий базисный вектор переменных, а через CB – вектор коэффициентов целевой функции, соответствующий этому базису.
Так как все небазисные переменные равны 0, стандартная задача ЛП сводится к задаче с целевой функцией F=CBxB и ограничениями BxB = b.
Текущее решение удовлетворяет уравнению:

Слайд 122

1. Линейное программирование. 1.15. Матричное представление симплекс-таблиц

Преобразованную симплекс-таблицу получаем, домножив обе части

1. Линейное программирование. 1.15. Матричное представление симплекс-таблиц Преобразованную симплекс-таблицу получаем, домножив обе части на B-1:
на B-1:

Слайд 123

1. Линейное программирование. 1.15. Матричное представление симплекс-таблиц

Представленная симплекс-таблица является основой всех вычислительных

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

Слайд 124

1. Линейное программирование. 1.16. Модифицированный симплекс-метод

В модифицированном симплекс-методе вместо процедуры преобразования строк

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

Слайд 125

1. Линейное программирование. 1.16. Модифицированный симплекс-метод

Рассмотрим пример решения задачи ЛП (Х.А.Таха): максимизировать F=x1+4x2+7x3+5x4 при

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

Слайд 126

1. Линейное программирование. 1.16. Модифицированный симплекс-метод

B=(P1,P2), то есть xB=(x1,x2)T и CB=(1,4)

1. Линейное программирование. 1.16. Модифицированный симплекс-метод B=(P1,P2), то есть xB=(x1,x2)T и CB=(1,4)

Слайд 127

1. Линейное программирование. 1.16. Модифицированный симплекс-метод

Так как целевая функция максимизируется, наличие отрицательного

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

Вычислим коэффициенты при небазисных переменных x3 и x4 в F-строке:

Слайд 128

1. Линейное программирование. 1.16. Модифицированный симплекс-метод

Найдем исключаемую переменную. Для нахождения выражения

вычисляем

вектор B-1P4

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

Слайд 129

1. Линейное программирование. 1.16. Модифицированный симплекс-метод

Итак, в базисе B вектор P1 будет

1. Линейное программирование. 1.16. Модифицированный симплекс-метод Итак, в базисе B вектор P1
заменен на P2, что приводит к новому базису

Новое значение целевой функции F = старое значение (19) – коэффициент при вводимой переменной x4 в F-строке (-3) х значение вводимой переменной (3/2) = 23,5

Имя файла: Воротницкий-Ю.И.-Исследование-операций..pptx
Количество просмотров: 408
Количество скачиваний: 1