Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5:

0.5x1 + 0.7x2 + 0.6x3 + 1x4 + 0x5 = 370

0.1x1 + 0.3x2 + 0.2x3 + 0x4 + 1x5 = 90

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

 

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

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

Решим систему уравнений относительно базисных переменных: x4, x5.

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0, 0, 0, 370, 90)

Базисное решение называется допустимым, если оно неотрицательно.

 

Базис В x1 x2 x3 x4 x5
x4   0.5 0.7 0.6    
x5   0.1 0.3 0.2    
F(X0)   -5 -8 -6    

 

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

 

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (0.3) и находится на пересечении ведущего столбца и ведущей строки.

 

Базис В x1 x2 x3 x4 x5 min
x4   0.5 0.7 0.6     528.57
x5   0.1 0.3 0.2      
F(X1)   -5 -8 -6      

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=0.3.

На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

 

B x1 x2
     
90 / 0.3 = 300 0.1 / 0.3 = 0.33 0.3 / 0.3 = 1
     

 

x3 x4 x5
     
0.2 / 0.3 = 0.67 0 / 0.3 = 0 1 / 0.3 = 3.33
     

 

После преобразований получаем новую таблицу:

 

Базис В x1 x2 x3 x4 x5
x4   0.27   0.13   -2.33
x2   0.33   0.67   3.33
F(X1)   -2.33   -0.67   26.67

Итерация №1.

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

 

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.27) и находится на пересечении ведущего столбца и ведущей строки:

 

Базис В x1 x2 x3 x4 x5 min
x4   0.27   0.13   -2.33  
x2   0.33   0.67   3.33  
F(X2)   -2.33   -0.67   26.67  

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=0.27.

На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x1 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

 

B x1 x2
160 / 0.27 = 600 0.27 / 0.27 = 1 0 / 0.27 = 0
     
     

 

x3 x4 x5
0.13 / 0.27 = 0.5 1 / 0.27 = 3.75 -2.33 / 0.27 = -8.75
     
     

 

После преобразований получаем новую таблицу:

 

Базис В x1 x2 x3 x4 x5
x1       0.5 3.75 -8.75
x2       0.5 -1.25 6.25
F(X2)       0.5 8.75 6.25

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

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

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

 

Базис В x1 x2 x3 x4 x5
x1       0.5 3.75 -8.75
x2       0.5 -1.25 6.25
F(X3)       0.5 8.75 6.25

 

Оптимальный план можно записать так:

x1 = 600 (партий);

x2 = 100 (партий).

F(X) = 5 • 600 + 8 • 100 = 3800 (усл.ед.).

 

3. Построим двойственную задачу по следующим правилам.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

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

Расширенная матрица A:

0.5 0.7 0.6  
0.1 0.3 0.2  
       

Транспонированная матрица AT:

0.5 0.1  
0.7 0.3  
0.6 0.2  
     

 

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Неравенства, соединенные стрелочками (↔), называются сопряженными.

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Выясним экономический смысл двойственной задачи. Заметим, что каждое слагаемое в левой части ограничений должно измеряться в тех же единицах, что и правая.

у1 – цена одной единицы первого ресурса (1 часа работы продавца).

у2 – цена одной единицы второго ресурса (1 м2 площади торгового зала).

0, 5y1+0, 1y2 – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого вида.

0, 7у1+0, 3у2 это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий второго вида.

370y1+90y2 – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого и второго вида.

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

Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj:

0.5y1+0.1y2≥ 5

0.7y1+0.3y2≥ 8

0.6y1+0.2y2≥ 6

370y1+90y2 → min

y1 ≥ 0, y2 ≥ 0.

 

Исходная задача I   Двойственная задача II
x1 ≥ 0 0.5y1+0.1y2≥ 5
x2 ≥ 0 0.7y1+0.3y2≥ 8
x3 ≥ 0 0.6y1+0.2y2≥ 6
5x1+8x2+6x3 → max 370y1+90y2 → min
0.5x1+0.7x2+0.6x3≤ 370 y1 ≥ 0
0.1x1+0.3x2+0.2x3≤ 90 y2 ≥ 0

 

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

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

Из первой теоремы двойственности следует, что Y = C*A-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис:

 

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

 

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A-1 =

 

Оптимальный план двойственной задачи равен:

y1 = 8.75;

y2 = 6.25.

Z(Y) = 370*8.75+90*6.25 = 3800 (усл.ед.)

4. Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

0.5*600 + 0.7*100 + 0.6*0 = 370 = 370

0.1*600 + 0.3*100 + 0.2*0 = 90 = 90

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1> 0).

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2> 0).

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

 

5. Обоснование эффективности оптимального плана.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

0.5*8.75 + 0.1*6.25 = 5 = 5

0.7*8.75 + 0.3*6.25 = 8 = 8

0.6*8.75 + 0.2*6.25 = 6.5 > 6

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый продукт экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1> 0).

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый продукт экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2> 0).

3-ое ограничение выполняется как строгое неравенство, т.е. продукцию 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x3 = 0.

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

При этом разница между ценами (6.5 - 6 = 0.5) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.

Анализ устойчивости оптимального плана.

Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.

Чувствительность решения к изменению коэффициентов целевой функции.

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

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

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

1-ый параметр целевой функции может изменяться в пределах:

∆ c1- = min [yk/d1k] для d1k> 0.

∆ c1+ = |max [yk/d1k]| для d1k< 0.

 

 

где в знаменателе коэффициенты столбцов свободных переменных в оптимальном плане (коэффициенты структурных сдвигов, элементы обратной матрицы к базису оптимального плана).

Таким образом, 1-параметр может быть уменьшен на 2.33 или увеличен на 0.71.

Интервал изменения равен:

(c1 - ∆ c1-; c1 + ∆ c1+)

[5-2.33; 5+0.71] = [2.67; 5.71]

Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится.

2-ый параметр целевой функции может изменяться в пределах:

∆ c2- = min [yk/d2k] для d2k> 0.

∆ c2+ = |max [yk/d2k]| для d2k< 0.

 

 

Таким образом, 2-параметр может быть уменьшен на 1 или увеличен на 7.

Интервал изменения равен:

(c2 - ∆ c2-; c2 + ∆ c2+)

[8-1; 8+7] = [7; 15]

Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится.

 

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.022 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал