🗊Презентация Методы оптимальных решений в линейном программировании

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача математического программирования: найти экстремум целевой функции F(X) =f (х1, х2, ..., хп) → max (min) (1.1) при системе ограничений

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

F(X) = с1 х1 + с2 х2 + ... + сп хп→max, F(X) = с1 х1 + с2 х2 + ... + сп хп→max,

В задаче на нахождение минимального значения целевой функции математическая модель её запишется в виде F(X) = с1 х1 + с2 х2 + ... В задаче на нахождение минимального значения целевой функции математическая модель её запишется в виде F(X) = с1 х1 + с2 х2 + ... + сп хп→min,

РАССМОТРИМ ВАРИАНТЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ДЛЯ СЛЕДУЮЩИХ ЗАДАЧ Задача 1. (Планирование производства.) Некоторое предприятие выпускает три типа продукции П1,П2,П3 двумя технологическими способами S1 и S2. Количество продукции j-гo вида (j = 1,2,3), произведенного i -м способом (i = 1,2) за единицу времени задано таблицей

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

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ Обозначим через хi j — время, затраченное на изготовление продукции Пj (j = 1,2,3) i -м способом. Тогда план производства будет иметь вид:

При этом продукции 1-го вида будет выпущено 20х11+ 30х21 , 2-го вида 25х12+20х22 , 3-го вида 30х13+ 15х23. При этом продукции 1-го вида будет выпущено 20х11+ 30х21 , 2-го вида 25х12+20х22 , 3-го вида 30х13+ 15х23. Стоимость всей продукции (обозначим ее за F) равна 5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) и она должна быть максимальной. Но при этом есть ограничения по времени: х11+ х12 + х13 ≤10, х21+ х22 + х23 ≤8 и очевидно, все хi j ≥ 0.

ОКОНЧАТЕЛЬНО ПОЛУЧАЕМ МАТЕМАТИЧЕСКУЮ МОДЕЛЬ ЗАДАЧИ F=5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) → max,

ЗАДАЧА 2. (ЗАДАЧА О СМЕСИ.) Известно, что при правильном питании человек должен получать в день не менее 20 единиц витамина А, не менее 15 единиц витамина В. Содержание этих витаминов в одной единице каждого из продуктов П1, П2, П3 задано таблице. Составить наиболее дешевый рацион питания. Все данные занесены в таблицу.

Математическая модель задачи Математическая модель задачи Пусть хi — количество продукта Пi, потребляемого в день (i=1,2,3), тогда стоимость всех продуктов (обозначим F) будет равна F=25х1 +30x2 + +20х3. При этом количество витамина А равно 4x1 + 5х2 + 2х3 , витамина В — 5x1 + 2х2 + 6х3, получаем математическую модель:

ЗАДАЧА 3. (О РАСКРОЕ МАТЕРИАЛА.)

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАССМОТРИМ ВОЗМОЖНЫЕ ВАРИАНТЫ РАСПИЛИВАНИЯ ДОСОК.

Обозначим через хi— количество досок, распиленных i-м способом, тогда заготовок по 2 м получится 3x1+ 2х2 + 2х3 + х4, по 2,5 м — x2 + 2x4 + х5; по 3 м — х 3 + x5 + 2x6. Обозначим через к — число полученных изделий, тогда Обозначим через хi— количество досок, распиленных i-м способом, тогда заготовок по 2 м получится 3x1+ 2х2 + 2х3 + х4, по 2,5 м — x2 + 2x4 + х5; по 3 м — х 3 + x5 + 2x6. Обозначим через к — число полученных изделий, тогда

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Алгоритм решения ЗЛП с двумя переменными графическим методом: Алгоритм решения ЗЛП с двумя переменными графическим методом: Строится область допустимых решений. Строится вектор = (с1, с2) с точкой приложения в начале координат. Перпендикулярно вектору проводится одна из линий уровня, например линия уровня, соответствующая уравнению с1х1 + с2х2 = 0. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться максимум или минимум функции.

Пример 1. Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max, Пример 1. Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max,

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

Перпендикулярно вектору построим одну из линий уровня (на рис. она проходит через начало координат). Так как задача на максимум, то перемещаем линию Перпендикулярно вектору построим одну из линий уровня (на рис. она проходит через начало координат). Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой.

В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т.е. через точку В = L1∩L2. Для определения координат точки В решаем систему уравнений В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т.е. через точку В = L1∩L2. Для определения координат точки В решаем систему уравнений

Пример 2. Найти минимум функции F(X)=2x1+x2→ min при ограничениях Пример 2. Найти минимум функции F(X)=2x1+x2→ min при ограничениях

ДВОЙСТВЕННАЯ ЗАДАЧА В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи):

Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи симметричной пары двойственных задач: Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи симметричной пары двойственных задач: F(X) = х1 + 4х2 +3 х3→min,

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

ТРАНСПОРТНАЯ ЗАДАЧА Формулировка транспортной задачи Однородный груз сосредоточен у т поставщиков в объемах a1, a2,..., ат. Данный груз необходимо доставить п потребителям в объемах b1, b2, ..., bn. Известны сij, i= 1, 2, ..., m, j = 1, 2, ..., п — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице:

ОПОРНОЕ РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Свойство системы ограничений транспортной задачи: Свойство системы ограничений транспортной задачи: ранг системы векторов ― условий транспортной задачи равен N=т + п — 1.

Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными.

МЕТОДЫ ПОСТРОЕНИЯ НАЧАЛЬНОГО ОПОРНОГО РЕШЕНИЯ МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла. В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель.

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно т + п — 1 и векторы-условия, соответствующие этим клеткам, линейно независимы. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно т + п — 1 и векторы-условия, соответствующие этим клеткам, линейно независимы. Теорема. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.

ПЕРЕХОД ОТ ОДНОГО ОПОРНОГО РЕШЕНИЯ К ДРУГОМУ В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку, и освобождается одна из занятых клеток, получается новое опорное решение.

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

Сдвигом по циклу на величину θ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов пере­возок во всех четных клетках, отмеченных знаком «—», на θ. Сдвигом по циклу на величину θ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов пере­возок во всех четных клетках, отмеченных знаком «—», на θ. Теорема. Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину θ = получится опорное решение.

МЕТОД ПОТЕНЦИАЛОВ

Числа Δij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи, Числа Δij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи,

ОСОБЕННОСТИ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ С НЕПРАВИЛЬНЫМ БАЛАНСОМ

Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами bn+1, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами bn+1, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза

Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами ат+1, равными разно суммарным запросам потребителей и запасам поставщиков, и нулевыми стоимостями перевозок единиц груза Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами ат+1, равными разно суммарным запросам потребителей и запасам поставщиков, и нулевыми стоимостями перевозок единиц груза

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

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

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

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину θ=

Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным т+п—1. Возвращаются к пункту 3. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным т+п—1. Возвращаются к пункту 3.

ПРИМЕР. РЕШИТЬ ТРАНСПОРТНУЮ ЗАДАЧУ, ДАННЫЕ ПРИВЕДЕНЫ В ТАБЛИЦЕ

2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С: 2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С:

3. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости 3. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости ( ). Записываем систему уравнений для нахождения потенциалов:

Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть и2 = 0. Остальные потенциалы находятся однозначно: Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть и2 = 0. Остальные потенциалы находятся однозначно:

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

В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно т + п — 1 = 7, в клетки с номерами (1, 1) и (2, 3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3, 4). Вычисляем значение целевой функции на втором опорном решении: В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно т + п — 1 = 7, в клетки с номерами (1, 1) и (2, 3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3, 4). Вычисляем значение целевой функции на втором опорном решении: F(X) = 0·1 + 100·1 + 100·2 + 100·3 + 0·4 + 300·7 + 200·0 = 2700.

6. Проверяем второе опорное решение Х2 на оптимальность. Находим, потенциалы и оценки. Решение не является оптимальным, так как имеются положительные оценки Δ31=2, Δ32=2, Δ42=1 и Δ43=2. Наибольшая из них равна 2 одновременно для трех клеток (3, 1), (3, 2) и (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак «+». Для этой клетки строим цикл и находим величину груза по циклу: θ=min{100,300}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение Х3. 6. Проверяем второе опорное решение Х2 на оптимальность. Находим, потенциалы и оценки. Решение не является оптимальным, так как имеются положительные оценки Δ31=2, Δ32=2, Δ42=1 и Δ43=2. Наибольшая из них равна 2 одновременно для трех клеток (3, 1), (3, 2) и (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак «+». Для этой клетки строим цикл и находим величину груза по циклу: θ=min{100,300}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение Х3.

Вычисляем значение целевой функции на третьем опорном решении: Вычисляем значение целевой функции на третьем опорном решении: F(X3)= 0·1 + 100·1 + 100·2 + 100·4 + 100·4 + 200·7 + 200·0 =2500. 7. Решение не является оптимальным, так как имеются положительные оценки Δ31=2 и Δ43=2. Ставим знак «+» пусть в клетку (3, 1), Для этой клетки строим цикл и находим величину груза для перераспределения по циклу: θ=min{100,200}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем четвертое опорное решение Х4:

Вычисляем значение целевой функции на четвертом опорном решении: F(Х4) = 0·l + 100·1 +200·4+ 100·3 + 100·4+ 100·7 + 200·0 =2300. Вычисляем значение целевой функции на четвертом опорном решении: F(Х4) = 0·l + 100·1 +200·4+ 100·3 + 100·4+ 100·7 + 200·0 =2300. 8. Проверяем решение Х4 на оптимальность. Находим потенциалы и оценки. Они приведены в таблице. Положительными являются оценки Δ13=2, Δ42=1 и Δ43=4. Для клетки (4, 3), которой соответствует наибольшая оценка, строим цикл и находим величину груза для перераспределения по циклу: θ=min{200,0,100}=0. Осуществляем сдвиг по циклу на величину θ=0. Получаем пятое опорное решение Х5:

Решение Х5 является оптимальным, так как все оценки отрицательные. Значение целевой функции F(X5) = F(X4) = 2300. Решение Х5 является оптимальным, так как все оценки отрицательные. Значение целевой функции F(X5) = F(X4) = 2300. Ответ: min F(Х)=2300 при