Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


Симплексные таблицы

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

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

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

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

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

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

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

7. Если пункты 4-6 алгоритма не выполняются, находят новое опорное решение с использованием условий нахождения оптимального решения.

Пример.Решить задачу табличным симплексным методом.

F(Х) = 9х1+5х2+4х3 +3х4 +2х5 →max.

Решение.Приводим задачу к каноническому виду. Для этого в левую часть первого ограничения-неравенства типа «≤» вводим дополнительную переменную х6 с коэффициентом +1. В целевую функцию переменная х6 входит с коэффициентом 0 (т.е. не входит). Получаем

F(Х) = 9х1 +5х2+4х3 +3х4 +2х5 +0 х6→max.

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1=х2=х3=0. Получаем опорное решение Х1= (0, 0, 0, 24, 30, 6) с единичным базисом Б1 = (А4 , А5, А6).



Вычисляем оценки разложений векторов условий по базису опорного решения, используя формулу (Δк=СбХкк, где Сб=(с12,…,ст) ― вектор коэффициентов целевой функции при базисных переменных; Хк=(х1к, х2к,…, хтк)-вектор коэффициентов разложения вектора по базису опорного решения; ск ― коэффициент целевой функции при переменной хк):

Δ1= СбХ1 - с1= (0, 3, 2) · (1, 1, 2) - 9 = 0 + 3 + 4 - 9 = -2;

Δ2 = СбХ22= (0, 3, 2) · (-2, 2, 1) - 5 = 0 + 6 + 2 - 5 = 3;

Δ3 = СбХ3- с3= (0, 3, 2) · (2, 1, -4) - 4 = 0 + 3 - 8 - 4 = -9;

Δ 4 = СбХ4- с4 = (0, 3, 2) · (0, 1, 0) - 3 = 0 + 3 + 0 - 3 = 0;

Δ 5 = СбХ5 - с5 = (0, 3, 2) · (0, 0, 1) - 2 = 0 + 0 + 2 - 2 = 0;

Δ 6 = СбХ6 - с6 = (0, 3, 2) ·(1, 0, 0) - 0 = 0 + 0 + 0 - 0 = 0.

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

В последней строке таблицы с оценками Δ к в столбце «А0» записывается значение целевой функции на опорном решении F(X1).

9 5 ↓4 3 2 0

Б Сб А0 А1 А2 А3 А4 А5 А6 θ1 θ3
←А6 -2
А4
А5 -4 -
Δ к -2 -9  

Начальное опорное решение не является оптимальным, так как оценки Δ1=-2, Δ3 = -9 для векторов А1 и А3 противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращения целевой функции найдем по формуле ΔFk = -θ0к Δ к. Вычислим значения параметра -θ0к для первого и третьего столбцов по формуле θ0к=, при хik>0, где к ― номер вектора, вводимого в базис; l - номер вектора, выводимого из базиса; хi0 ― координаты опорного решения; хik - коэффициент разложения вектора Ак по базису опорного решения. Получаем θ01 = 6 при l=1 (где l — номер строки) и θ03 = 3 при l = 1. Находим приращение целевой функции при введении в базис первого вектора ΔF1 = -6·(-2) = 12 и третьего вектора ΔF3= -3·(-9) = 27. Следовательно, для наиболее быстрого нахождения оптимального решения необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).

Далее выполним преобразование с элементом х13 = 2, получим второе опорное решение Х2=(0,0,3,21,42,0) с базисом Б2 = (A3 , A4, А5) (следующая таблица). Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = -6. Для улучшения решения необходимо ввести вектор А2 в базис опорного решения.

 

Б Сб А0 А1 А2 А3 А4 А5 А6 θ2
А3 ½ -1 ½ -
←А4 ½
А5 -3 -
Δ к 5/2 -6 9/2  

Определим номер вектора, выводимого из базиса. Для этого вычислим параметр θ02 для второго столбца, он равен 7 при l =2. Следовательно, из базиса выводим второй вектор базиса А4. Выполним преобразование с элементом х22 = 3, получим третье опорное решение Х3 = (0, 7, 10, 0, 63, 0) с базисом Б2 = (А3, А2, А5). Это единственное оптимальное решение, так как для всех векторов, не входящих в базис, оценки разложений по базису опорного решения положительны: Δ1=7/2, Δ4=2, Δ6=7/2.



Б Сб А0 А1 А2 А3 А4 А5 А6
А3 2/3 1/3 1/3
←А2 1/6 1/3 -1/6
А5 9/2 3/2
Δ к 7/2 7/2

Ответ: max F(X) = 201 при X * = (0, 7,10, 0, 63).

Задачи решить симплексным методом:

 

9. Кирпичный завод выпускает кирпичи двух марок (I и II). Для производства кирпича применяется глина трех видов (А, В и С). По месячному плану завод должен выпустить 10 усл. ед. кирпича марки I и 15 усл. ед. кирпича марки II. В таблице указаны расход различных видов глины для производств 1 усл. ед. кирпича каждой марки и месячный запас глины. Какова наибольшая прибыль, если известно, что от реализации 1 усл. ед. кирпича марки I завод получает прибыль, равную 4 ден. ед., а марки II — 7 ден. ед.?

  Марка кирпича   Количество глины для производства 1 усл. ед. кирпича
А В С
I
II
Запасы глины, усл. ед.

 

10. Для производства стали определенной марки, в которую в качестве легирующих веществ должны входить химические элементы К, L, Р, можно закупать шихту двух видов (I и II). В таблице указано, сколько требуется каждого из этих элементов для производства 100 т стали (по технологии можно немного больше, но меньше — нельзя). Содержание этих элементов в каждой тонне шихты, а также стоимость 1 т шихты каждого вида также приведены в таблице.

  Вид шихты Стоимость 1 т шихты Легирующие вещества
К L Р
I
II
Необходимое количество легирующих веществ

Определить наименьшие затраты для производства стали данной марки.

 

Ответы: 1. х1=1, х2=0, Fmax =1; 2. х1=12, х2=6, Fmax =84; 3. Задача не имеет решений, т.к. F не ограничена на области D сверху; 4. х1=х2=0, х3=10, Fmax=10; 5. х1=0, х2=1, Fmin =-1; 6. х1=2, х2=0, Fmin=-4; 7. х1=х4=х5=0, х2=4, х3=5, х6=11, Fmin=-11; 8. х1=3/2, х2=7/4, Fmax=-1; 9. Fmax=191 ден.ед.; 10. Fmin= 14 ден.ед.

<== предыдущая лекция | следующая лекция ==>
Симплекс-метод. Симплексный метод — это метод целенаправленного перебора опорных решений задачи линейного программирования | Виды математических моделей двойственных задач

Дата добавления: 2014-01-04; Просмотров: 435; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.006 сек.