35840

Линейное программирование. Задачи линейного программирования

Шпаргалка

Информатика, кибернетика и программирование

Симплексный метод решения задачи линейного программирования ЛП Симплексный метод СМ – алгебраический метод позволяющий решить задачу ЛП с помощью итераций. Идея СМ – начиная с некоторого исходного опорного решения начальной точки с учетом ограничений осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному к точке глобального оптимума угловая точка такая что при перемещении в любую другую точку допустимой области решений значение ЦФ не убывает для задач на mx и не возрастает – на min....

Русский

2013-09-20

769.1 KB

102 чел.

11. Симплексный метод решения задачи линейного программирования (ЛП)

Симплексный метод (СМ) – алгебраический метод, позволяющий решить задачу ЛП с помощью итераций. СМ является универсальным, т.к. позволяет решить практически любую задачу ЛП, заданную в каноническом виде. Идея СМ – начиная с некоторого исходного опорного решения (начальной точки с учетом ограничений) осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному (к точке глобального оптимума - угловая точка такая, что при перемещении в любую другую точку допустимой области решений значение ЦФ не убывает для задач на max и не возрастает – на min). Т.к. число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.

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

1. Задача ЛП должна бать приведена к каноническому виду. Преобразовать все ограничения равенства к виду, при котором правая часть ограничений – неотрицательное число.

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

3. Набор есть – разбить переменные на 2 группы – базисные и не базисные. Базисные соответствуют столбцам, образующим ед.матрицу, остальные – не базисные. Полагая всякую не базисную переменную = 0, а базисную = правой части ограничений, в которых эта переменная присутствует, получаем опорное решение.

4. Построить симплекс таблицу, отвечающую полученному опорному решению. Все строки таблицы 1-го шага, за исключением строки оценок ∆j (индексная строка), заполняем по данным системы ограничений и ЦФ.

5. Сделать вывод для построения начальной симплекс-таблицы, применить метод искусственного базиса.

Пусть дана задача ЛП:

Прибавляем дополнительную переменную для приведения к каноническому виду:

             

Выписываем матрицу ограничений:

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

Т1

0

0

0

Строка оценок

1

2

j

n

F(x)

Индексная строка ∆j для переменных находится по формуле:

; При этом возможны следующие случаи решения задачи на максимум:

• если все оценки (для задачи на max), то найденное решение оптимальное;

•  если хотя бы одна оценка  но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как F(x)→∞, т. е. ЦФ не ограничена в ОДР;

•  если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

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

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

6. Заполнить симплексную таблицу 2-го шага: меняем местами базисную и небазисную переменные, разрешающий элемент заменяем на обратный, элементы разрешающей строки делим на разрешающий элемент, все элементы разрешающего столбца делим на разрешающий элемент и записываем с обратным знаком. Остальные элементы рассчитываем по правилу прямоугольника. Опорное решение проверяем на оптимальность и т.д.

12. Двойственный симплексный метод решения задач линейного программирования.

С каждой задачей ЛП тесно связана другая линейная задача, называемая двойственной. Решение одной задачи двойственной пары может быть получено из решения другой. Мат.апарат ЛП позволяет не только получать с помощью эффективных вычислительных методов оптимальный план, но и делать ряд содержательных экономических выводов, основанных на свойствах двойственных задач. Переменные двойственной задачи называют объективно обусловленными оценками, ценами ресурсов, теневыми ценами. Каждая из задач двойственной пары является самостоятельной задачей ЛП, которая м.б. решена независимо от другой. Использование двойственного симплекс-метода для решения задач линейного программирования обусловлено его возможностью находить допустимые и оптимальные планы в условиях, когда прямой симплекс-метод не может быть использован. Двойственный симплекс-метод использует видоизмененные условия допустимости и оптимальности, что обеспечивает ему продвижение к общему с прямой задачей решению с внешней стороны многоугольника ограничений.

 В зависимости от структуры модели исходной задачи различают симметричные (стандартные), несимметричные (канонические) и смешанные двойственные задачи.

1.  Симметричные двойственные задачи: пусть дана прямая задача

 

 X .

В стандартной задаче векторы C, B и матрица A предполагаются заданными. Используя те же данные, но другое множество переменных можно сформулировать следующую задачу:

 

 

 Y ,

двойственную к исходной. Правила построения симметричной двойственной пары задач:

- Каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную . Число неравенств в системе ограничений одной задачи совпадает с числом переменных другой.

- Коэффициентами ЦФ двойственной задачи являются свободные члены системы ограничений прямой.

- Задача на max ЦФ переходит в задачу на min и наоборот

- Коэффициенты системы ограничений двойственной задачи образуют транспонированную матрицу коэффициентов системы ограничений прямой задачи.

- Свободными членами системы ограничений двойственной задачи становятся коэффициенты ЦФ прямой.

- Знаки неравенств функциональных ограничений меняются на противоположные

- Ограничения на не отрицательность не изменяются

2. Несимметричные двойственные задачи

 Сущность двойственного симплекс-метода с учетом существующей взаимосвязи с прямым методом заключается в получении вначале недопустимого, но «лучшего», чем искомое оптимальное решение, а затем в систематическом “приближении” решения к области допустимых при выполнении условия оптимальности.

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

Условие допустимости. В качестве исключаемой переменной выбирается базисная переменная, решение для которой отрицательное и наибольшее по абсолютной величине. Если все базисные переменные неотрицательные, процесс вычислений заканчивается, так как полученное решение допустимое и оптимальное.

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

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

13. Геометрическая интерпретация решения задачи линейного программирования в R2. Графический метод решения задач ЛП.

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

Множество планов основной задачи ЛП является выпуклым, если оно не пусто. Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений – вершиной. Если задача ЛП имеет оптимальный план, то ЦФ задачи принимает max(min) значение в одной из вершин многогранника решений. Если max(min) значение достигается более, чем в 1 вершине, то ЦФ принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин.

Непустое множество планов задачи ЛП образует выпуклый многогранник, каждая вершина которого определяет опорный план. Для одного из опорных планов значение ЦФ является max(min) при условии, что функция ограничена сверху(снизу) для задачи на максимум(минимум). Вершину многогранника можно найти только для задач ЛП с двумя переменными.

Пересечение полуплоскостей, определяемое системой линейных неравенств, называется областью решения системы, а если она удовлетворяет условиям не отрицательности вектора j, областью допустимых решений задачи. Если система решений совместна, то ОДР является выпуклое множество, которое является многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенства на знак =.

Гиперплоскостью в n-мерном Евклидовом пространстве называется множество точек, удовлетворяющих равенству: const. Гиперплоскость делит пространство на полупространства. Градиент функции – вектор, координаты которого равны частным производным первого порядка

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

Линия уровня – прямая, перпендикулярная градиенту (антиградиенту).

Алгоритм геометрического решения задачи ЛП:

1. Строим на плоскости систему координат

2. Для каждого ограничения находим геометрическое место точек, удовлетворяющее этому ограничению.

3. Выделяем пересечение полученных множеств.

4. Если ограничения противоречивы, то ОДР является пустым множеством, иначе в задаче ЛП ОДР – всегда выпуклое замкнутое множество. Иногда множество ОДР является ограниченным, а иногда нет.

Если ОДР – пустое множество – имеет место неразрешимость 1го рода, алгоритм завершает работу.

5. Находим градиент ЦФ: , рисуем вектор-градиент, исходящий из начала координат.

6. Проводим линию уровня, разбивающую ОДР на 2 части.

7. Перемещаем линию уровня по направлению grad для max (в обратном для min) до последней точки, при которой ОДР располагается по 1 сторону линии уровня.

8. Если при сколь угодном перемещении такое положение недостижимо, то имеет место неограниченность ЦФ в ОДР сверху при max (снизу при min) – неразрешимость 2го рода, алгоритм завершает работу.

9. Если указанное в п.7 положение найдено, то в этом положении находим точки, лежащие на пересечении линии уровня и ОДР. Они являются оптимальным решением задачи.

Значение координат определяется аналитически, затем вычисляется оптимальное значение ЦФ

14. Правила построения двойственной задачи линейного программирования. Экономическая интерпретация двойственных оценок.

С каждой задачей ЛП тесно связана другая линейная задача, называемая двойственной. Решение одной задачи двойственной пары может быть получено из решения другой. Мат.апарат ЛП позволяет не только получать с помощью эффективных вычислительных методов оптимальный план, но и делать ряд содержательных экономических выводов, основанных на свойствах двойственных задач. Переменные двойственной задачи называют объективно обусловленными оценками, ценами ресурсов, теневыми ценами. Каждая из задач двойственной пары является самостоятельной задачей ЛП, которая м.б. решена независимо от другой. Использование двойственного симплекс-метода для решения задач линейного программирования обусловлено его возможностью находить допустимые и оптимальные планы в условиях, когда прямой симплекс-метод не может быть использован. Двойственный симплекс-метод использует видоизмененные условия допустимости и оптимальности, что обеспечивает ему продвижение к общему с прямой задачей решению с внешней стороны многоугольника ограничений.

 В зависимости от структуры модели исходной задачи различают симметричные (стандартные), несимметричные (канонические) и смешанные двойственные задачи.

Пусть дана прямая задача , , X . В стандартной задаче векторы C, B и матрица A предполагаются заданными. Используя те же данные, но другое множество переменных можно сформулировать следующую задачу: , , Y , двойственную к исходной. Правила построения симметричной двойственной пары задач:

-Каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную . Число неравенств в системе ограничений одной задачи совпадает с числом переменных другой.

-Коэффициентами ЦФ двойственной задачи являются свободные члены системы ограничений прямой.

-Задача на max ЦФ переходит в задачу на min и наоборот

-Коэффициенты системы ограничений двойственной задачи образуют транспонированную матрицу коэффициентов системы ограничений прямой задачи.

-Свободными членами системы ограничений двойственной задачи становятся коэффициенты ЦФ прямой.

-Знаки неравенств функциональных ограничений меняются на противоположные

-Ограничения на не отрицательность не изменяются

Двойственность – формальное мат. соотношение, для любой задачи ЛП можно построить двойственную. Если прямая задача выражает реальную проблему, то и двойственная обладает экономической интерпретацией.

Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов. Рассмотрим задачу об использовании ресурсов:

Задача 1 (исходная)

Задача 2 (двойственная)

при ограничениях:

и условии неотрицательности

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

при ограничениях:

и условии неотрицательности

Найти такой набор цен (оценок) ресурсов , при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

В приведенной модели  обозначает запас ресурса ;
– число единиц ресурса  потребляемого при производстве единицы продукции ;
- прибыль (выручка) от реализации единицы продукции  (или цена продукции ). Предположим, что некоторая организация решила закупить ресурсы  и необходимо установить оптимальные цены на эти ресурсы . Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах  no ценам соответственно  были минимальны, т.е . С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции , должны быть не менее ее цены , т.е. . Аналогично можно составить ограничения в виде неравенств по каждому виду продукции. Цены ресурсов в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, "ненастоящие" цены. В отличие от внешних цен  на продукцию, известных, как правило, до начала производства, цены ресурсов  являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

15. Постановка задачи об использовании ресурсов (задача планирования производства). Методы решения задачи. Постановка задачи составления рациона. Экономическая интерпретация задачи. 

Задача производственного планирования: Предприятие выпускает продукцию, для этого оно использует ресурсы ограниченного количества. Известно  кол-во ресурсов каждого вида, используемых для изготовления каждого вида продукции. Известен доход от каждой единицы всех видов продукции. Предприятие намерено выпускать продукцию в таких объемах, которые дадут max доход. Задача имеет следующий вид:

Где m – виды ресурсов на предприятии; n – число видов выпускаемой продукции; – кол-во единиц i-го ресурса, требуемого для изготовления одной единицы j-го вида продукции ();  – max кол-во ресурсов i-го вида, имеющегося в распоряжении предприятия;  – цены (доход) от одной единицы j-го товара;  – запланированный уровень выпуска j-го вида продукции.

(Методы решения: симплексный, графический в сл. 2х видов продукции, решение на компе, например, в экселе)

Задача составления рациона (задача о диете, задача о смесях): Имеется два вида корма I и II, содержащие питательные вещества (витамины) . Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ:

Питательное вещество (витамин)

Необходимый min питательных веществ

Число ед. питательных веществ в 1 кг корма

I

II

9

3

1

8

1

2

12

1

6

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб. Необходимо составить дневной рацион, имеющий min стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела. Решение: Составим экономико-математическую модель задачи.

Обозначим ,  — кол-во кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать () единиц питательного вещества , () ед. вещества  и () ед. питательного вещества . Так как содержание питательных веществ  в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств:

Кроме того, переменные     (2)

Общая стоимость рациона составит (в руб.):   (3)

Итак, экономико-математическая модель задачи: составить дневной рацион  удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает минимальное значение.

Для формулировки задачи в общей постановке обозначим: () - число единиц корма n-го вида; () - необходимый минимум содержания в рационе питательного вещества ;  - число единиц питательного вещества  в единице корма j-го вида;  - стоимость ед. корма j-го вида. Тогда экономико-мат. модель задачи примет вид: найти такой рацион , удовлетворяющий системе:

16. Экономико-математическая модель транспортной задачи (ТЗ). Методы решения.

Транспортная задача – одна из распространенных задача ЛП. Цель – разработка наиболее рациональных путей и способов транспортировки товара, устранение чрезмерно дальних, встречных и повторных перевозок. Результаты решения дают возможность предприятию уменьшить затраты, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

В общем виде транспортную задачу можно представить: В m пунктах производства  имеется однородный груз в количествах соответственно . Его необходимо доставить в n пунктов назначения  соответственно в количествах . Стоимость перевозки одной ед. груза (тариф) из пункта в пункт равна  д.е. Требуется определить план перевозок,  позволяющий перевезти все грузы, полностью удовлетворить потребность и имеющий min стоимость. В зависимости от соотношения между суммарными затратами, между потребностями и поставками ТЗ бывает открытого и закрытого типа.

Определение: Если сумма запасов груза равна суммарной потребности в нем, то ТЗ является задачей закрытого типа . Если сумма запасов груза НЕ равна суммарной потребности в нем, то ТЗ является задачей открытого типа.

Рассмотрим закрытую ТЗ. Обозначим через  кол-во груза, перевезенного из пункта в пункт . Математическая модель задачи:

При ограничениях:

 – уравнение баланса по строкам

– уравнение баланса по столбцам

Оптимальным решением ТЗ явл-ся матрица, удовлетворяющая системе ограничений и доставляющая min ЦФ.

Теорема: Для решения ТЗ необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления равнялись суммарным заявкам пунктов назначения, т.е. выполнялось равенство:

Симплексный метод не является оптимальным для решения ТЗ из-за большого количества уравнений. Решение ТЗ осуществляется по следующим шагам:

1. Нахождение исходного опорного плана

2. Проверка на оптимальность

3. Переход от одного опорного решения к другому

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

Существуют 2 метода построения первоначального опорного плана: 1. Метод северо-западного угла; 2. Метод min элемента (тарифа).

Опорный план является оптимальным, если ему соответствует система (m+n) действительных чисел  и , удовлетворяющих условиям:

Числа  и  называют потенциалами.

17. Первая и вторая теоремы двойственности. Экономическая интерпретация прямой и двойственной задач.

Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности. Вначале рассмотрим вспомогательные утверждение.

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

Достаточный признак оптимальности. Если   и  - допустимые решения взаимно двойственных задач, для которых выполняется равенство , то X* - оптимальное решение исходной задачи I, a Y* - двойственной задачи II

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

Если ЦФ одной из задач не ограничена, то условия другой – противоречивы. Обратное неверно, из того, что условия исходной задачи противоречивы НЕ следует, что ЦФ двойственной задачи не ограничена.

Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: ,  

Экономический смысл первой (основной) теоремы двойственности. План производства   и набор цен (оценок) ресурсов  оказываются оптимальными ТТТ, когда прибыль (выручка) от реализации продукции, найденная при "внешних" ценах , равна затратам на ресурсы по "внутренним " ценам . Для всех же других планов X и Y обеих задач в соответствии с основным неравенством теории двойственности прибыль (выручка) от продукции всегда меньше затрат на ресурсы.

Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану  и получить максимальную прибыль (выручку)  либо продавать ресурсы по оптимальным ценам  и возместить от продажи равные ей минимальные затраты на ресурсы .

Величина  характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов. Из I теоремы двойственности следует, что при оптимальных производственной программе и вектора оценок ресурсов потери равны 0.

Пусть даны две взаимно двойственные задачи. Если каждую решать симплексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений прямой задачи необходимо ввести т неотрицательных переменных , а в систему ограничений двойственной задачи – n  неотрицательных переменных:   

Системы ограничений прямой и двойственной задач соответственно примут вид: ;   

Установим соответствие между переменными прямой и двойственной задач в таблице соответствия:

II Теорема двойственности. Для оптимальных планов  и  прямой и двойственной задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений:

 

Данное условие позволяет, зная решение одной из двойственных задач найти оптимальное решение другой задачи, т.е. из II теоремы двойственности следуют такие требования на оптимальную производственную программу  и : 1) если , то , ; 2) если , то , ; 3) если , то , ; 4) если , то ,

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

18. Алгоритм решения транспортной задачи (метод северо-западного угла, метод минимального элемента).

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

1. Метод "северо-западного" угла (на рис): В угловую клетку записывается min из 2х элементов , затем зачеркиваем строку или столбец, содержащий min элемент. В оставшейся(-мся) пишем разницу , затем след. клетка (угловая) и т.д. Если , берем любое из них.

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

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

Число переменных ТЗ = рангу матрицы системы ЛУ (число линейно-независимых уравнений в системе ограничений). Теорема: Ранг системы ограничений и  при условии  :    , опорное решение содержит  клетку.

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

Далее проверяем опорный план на оптимальность методом потенциалов (критерий оптимальности): Если опорное решение ТЗ является оптимальным, то ему соответствует система  действительных чисел
и , удовлетворяющих условиям:    

Числа  и  называют потенциалами. Потенциалы являются переменными двойственной задачи ТЗ и обозначают плату за перевозку единицы груза в пунктах отправления (поставщиками) и пунктах назначения (потребителями). Поэтому их сумма = транспортному тарифу. А условия для потенциалов получены на основании II теоремы двойственности. Потенциалы  и  находятся из равенства  , справедливого для занятых клеток. Всегда полагается, что , тогда остальные потенциалы определяются однозначно для базисных переменных:

;  

Обозначим  оценкой свободных клеток. Если все оценки свободных клеток ≤ 0, то решение является оптимальным. Если хотя бы одна из оценок больше 0 – решение не является оптимальным и мы должны перераспределить грузы (перейти к другому опорному решению):

Меняем местами базисные и небазисные переменные. Для свободной клетки, имеющей max отклонение от тарифа  (max) (на рис. клетка m1) строится цикл (ломанная), вершины к. лежат в заполненных клетках, а начало и конец в выбранной клетке. При этом в любой строке таблицы лежит ровно 2 вершины ломанной. Соединение идет только по строкам и столбцам. Около свободной клетки, к. вводится в базис, ставится знак «+», затем поочередно ставится «-» и «+».. Определяется min величина  по всем клеткам цикла со знаком «-». По всем клеткам со знаком «+» данное значение добавляется, со знаком «-» - вычитается. В результате получаем новый опорный план. Его решение проверяется на оптимальность методом потенциалов до тех пор, пока не будет получено оптимальное решение.

19. Метод искусственного базиса для решения задач линейного программирования.

Понятие об М-методе (методе искусственного базиса)

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

 

 X 

1.  Приводим задачу к каноническому виду (с помощью дополнительных переменных):

-в системе ограничений ≤ добавляем слабую переменную

-в ограничениях ≥ вычитаем неотрицательную искусственную переменную

-в ограничениях = добавляем неотрицательную искусственную переменную

2. Для дальнейшего рассуждения считаем, что система ограничений вообще не содержит базисных переменных, т.е. единичных столбцов. Тогда:

 

 X , V , W 

3. Для получения начального плана после ввода искусственных мы используем новую задачу:

или   – необходимо найти min сумму неотр. переменных

Лемма: Множество дополнительных решений исходной задачи не пусто ТТТ, когда оптимальное значение ЦФ вспомогательной задачи = 0:

Возможны 2 варианта:

А) Если искусственные переменные не базисные, т.е. = 0, то значение ЦФ вспомогательной задачи = 0, следовательно, мы построили симплекс-таблицу, оптимальную для вспомогательной задачи и первоначальную для решения исходной.

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

Б) Таблица оптимальна, но значение ЦФ не равно 0, следовательно, не удалось исключить все искусственные переменные из базиса. Имеет место неразрешимость 1го рода (означает несовместность системы ограничений, следовательно, множество допустимых решений исходной задачи пусто, задача решена).

Пример:

Ограничение «=», следовательно, добавляем неотрицательную искусственную переменную:

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

20. Общая постановка задачи линейного программирования. Методы решения ЗЛП.

Задача линейного программирования – оптимизация линейной функции в области, задаваемой линейными ограничениями. В общем случае ЗЛП звучит так. Дана система линейных уравнений и неравенств с переменными:

     (1)

линейная функция . Необходимо найти такое решение системы , где  при котором линейная функция  принимает оптимальное (т.е. максимальное или минимальное) значение. Система (1) называется системой ограничений, а функция  - линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

Необходимо найти такой вектор , при котором линейная функция принимает оптимальное значение.

Допустимым решением задачи называется вектор , удовлетворяющий всем ограничениям задачи. Допустимые решения образуют область допустимых решений (ОДР).

Оптимальным решением (или оптимальным планом) задачи ЛП называется ДР, доставляющее ЦФ наибольшее (наименьшее) значение. системы ограничений (1.20), удовлетворяющее условию (1.22), при котором линейная функция (1.21) принимает оптимальное (максимальное или минимальное) значение.

Термины "решение" и "план" - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй - о содержательной стороне (экономической интерпретации).

Задачи ЛП бывают неразрешимы. Неразрешимость бывает 2х типов: 1. ОДР – пустое множество; 2. Не существует max (min) f(x),  – неограниченность ЦФ сверху (снизу).

Решить задачу ЛП – это:

1) если задача разрешима – в ОДР определить оптимальное решение и вычислить значение ЦФ

2) если задача неразрешима – определить причину

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

Теорема. Всякому решению   неравенства  соответствует определенное решение  уравнения , в котором  

И, наоборот, каждому решению  уравнения ( и неравенства   соответствует определенное решение  неравенства .

Записи задачи ЛП приблизительны в том смысле, что путем математических преобразований можно перейти от одной формы к другой.  Правила перехода:

1. Если задача на max, то

2. Переход от неравенства к равенству происходит с помощью введения дополнительной переменной

 

,

или искусственной переменной:

 

,


 

А также другие работы, которые могут Вас заинтересовать

38752. СИЛА МОМЕНТА РУКОВОДСТВО ПО ДУХОВНОМУ ПРОСВЕТЛЕНИЮ 986.5 KB
  ДИКАРЛО ВВЕДЕНИЕ ПЕРВОПРИЧИНА ЭТОЙ КНИГИ ИСТИНА КОТОРАЯ ВНУТРИ ТЕБЯ ГЛАВА ПЕРВАЯ: ТЫ ЭТО НЕ ТВОЙ УМ САМОЕ БОЛЬШОЕ ПРЕПЯТСТВИЕ НА ПУТИ К ПРОСВЕТЛЕНИЮ ОСВОБОЖДЕНИЕ СЕБЯ ОТ УМА ПРОСВЕТЛЕНИЕ: ВОСХОЖДЕНИЕ НАД МЫШЛЕНИЕМ ЭМОЦИЯ: РЕАКЦИЯ ТЕЛА НА СОСТОЯНИЕ УМА ГЛАВА ВТОРАЯ: СОЗНАНИЕ: ПУТЬ ПРОЧЬ ОТ БОЛИ ПЕРЕСТАНЬ СОЗДАВАТЬ БОЛЬ В НАСТОЯЩЕМ БОЛЬ ИЗ ПРОШЛОГО: РАСТВОРЕНИЕ ТЕЛА БОЛИ ОТОЖДЕСТВЛЕНИЕ ЭГО С ТЕЛОМ БОЛИ ПЕРВОПРИЧИНА СТРАХА КАК ЭГО ИЩЕТ ЦЕЛОСТНОСТЬ ГЛАВА ТРЕТЬЯ: УГЛУБЛЯЯСЬ В МОМЕНТ СЕЙЧАС НЕ ИЩИ СЕБЯ В УМЕ ПОКОНЧИ С ИЛЛЮЗИЕЙ ВРЕМЕНИ НИЧТО НЕ...
38756. Осторожно! Вредные продукты 2.96 MB
  Когда начинаешь говорить о последствиях наступивших в результате употребления некоторых продуктов питания которых и продуктамито назвать затруднительно люди часто отмахиваются: Да ведь живем же. Вообще история развития диетологии напоминает политический детектив: различные виды продуктов то подвергались гонениям то возводились на пьедестал. Но ныне диетология остепенилась и окончательно стала тем чем собственно она всегда и была мощным средством одурачивания в руках недобросовестных производителей продуктов питания. Но На...
38757. Отношение человека к собственному телу 155.5 KB
  Что происходило в Ваших отношениях с другими вследствие этой травмы Как изменились Ваши отношения с коллегами друзьями родителями любимыми в ситуации травмы Какой у Вас появился опыт преодоления травмы Изменилось ли Ваше обращение с собственным телом Какой способ обхождения с травмами и болью Вы получили Изменились ли Ваши цели планы надежды в связи с травмой Обратитесь к своему телу или части тела которая была повреждена и причиняла страдания. Что бы Вы могли сказать этой части тела Мысленно осмотрите свое тело и...
38758. Ораторское искусство 411 KB
  Критерием качества усвоения той или иной темы является умение подмечать ошибки допускаемые в собственной речи и или в речах других людей глубоко и всесторонне анализировать язык и стиль публичных выступлений ярко образно аргументированно и убедительно излагать те или иные положения. Тема 1Предмет и функции ораторского искусства В научной литературе понятия риторика красноречие мастерство публичного выступления ораторское искусство нередко используются как родственные. Разделяет ее в частности отечественная философская...
38759. Экономика и управление на предприятии ОАО «Новосибирская макаронная фабрика» 126.5 KB
  Королева Отчет по преддипломной практике по предприятию ОАО Новосибирская макаронная фабрика по специальности Экономика и управление на предприятие Выполнила: Детюченко В. Данную работу можно разделить на несколько разделов: 1 Уставные характеристики организации 2 История предприятия ОАО Новосибирская макаронная фабрика 3 Приоритетные направления деятельности ОАО Новосибирская макаронная фабрика 4 Анализ структуры предприятия 5 Анализ системы закупок Заключение Список использованной литературы Содержание...