У вас вопросы?
У нас ответы:) SamZan.net

Определим минимальное значение целевой функции FX 3x1 6x2 при следующих условияхограничений

Работа добавлена на сайт samzan.net: 2015-07-10

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 20.2.2025

Симплекс-метод.

 

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

Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = - 3x1 + 6x2 при следующих условиях-ограничений.

5x1 - 2x2≤4

- x1 + 2x2≤4

x1 + x2≥4

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

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

5x1-2x2 + 1x3 + 0x4 + 0x5 = 4

-1x1 + 2x2 + 0x3 + 1x4 + 0x5 = 4

1x1 + 1x2 + 0x3 + 0x4-1x5 = 4

Введем искусственные переменные x: в 3-м равенстве вводим переменную x6;  

5x1-2x2 + 1x3 + 0x4 + 0x5 + 0x6 = 4

-1x1 + 2x2 + 0x3 + 1x4 + 0x5 + 0x6 = 4

1x1 + 1x2 + 0x3 + 0x4-1x5 + 1x6 = 4

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = -3x1+6x2+Mx6 → min

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

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

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

Из уравнений выражаем искусственные переменные:

x6 = 4-x1-x2+x5 

которые подставим в целевую функцию:

F(X) = -3x1 + 6x2 + M(4-x1-x2+x5) → min

или

F(X) = (-3-M)x1+(6-M)x2+(M)x5+(4M) → min

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

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

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

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

x3, x4, x6,

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

X1 = (0,0,4,4,0,4)

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

Базис

B

x1

x2

x3

x4

x5

x6

x3

4

5

-2

1

0

0

0

x4

4

-1

2

0

1

0

0

x6

4

1

1

0

0

-1

1

F(X0)

4M

3+M

-6+M

0

0

-M

0

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

Итерация №0.

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

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

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

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

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

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

и из них выберем наименьшее:

min (4 : 5 , - , 4 : 1 ) = 4/5 

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

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

Базис

B

x1

x2

x3

x4

x5

x6

min

x3

4

5

-2

1

0

0

0

4/5

x4

4

-1

2

0

1

0

0

-

x6

4

1

1

0

0

-1

1

4

F(X1)

4M

3+M

-6+M

0

0

-M

0

0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x3 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=5

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

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

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

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

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

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

B

x 1

x 2

x 3

x 4

x 5

x 6

4 : 5

5 : 5

-2 : 5

1 : 5

0 : 5

0 : 5

0 : 5

4-(4 • -1):5

-1-(5 • -1):5

2-(-2 • -1):5

0-(1 • -1):5

1-(0 • -1):5

0-(0 • -1):5

0-(0 • -1):5

4-(4 • 1):5

1-(5 • 1):5

1-(-2 • 1):5

0-(1 • 1):5

0-(0 • 1):5

-1-(0 • 1):5

1-(0 • 1):5

(0)-(4 • (3+M)):5

(3+M)-(5 • (3+M)):5

(-6+M)-(-2 • (3+M)):5

(0)-(1 • (3+M)):5

(0)-(0 • (3+M)):5

(-M)-(0 • (3+M)):5

(0)-(0 • (3+M)):5

 

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x6

x1

4/5

1

-2/5

1/5

0

0

0

x4

44/5

0

13/5

1/5

1

0

0

x6

31/5

0

12/5

-1/5

0

-1

1

F(X1)

-22/5+31/5M

0

-44/5+12/5M

-3/5-M

0

-M

0

Итерация №1.

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

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

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

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

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

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

и из них выберем наименьшее:

min (- , 44/5 : 13/5 , 31/5 : 12/5 ) = 22/7 

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

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

Базис

B

x1

x2

x3

x4

x5

x6

min

x1

4/5

1

-2/5

1/5

0

0

0

-

x4

44/5

0

13/5

1/5

1

0

0

3

x6

31/5

0

12/5

-1/5

0

-1

1

22/7

F(X2)

-22/5+31/5M

0

-44/5+12/5M

-3/5-M

0

-M

0

0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x6 в план 2 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=12/5 

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x2 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.

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

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

B

x 1

x 2

x 3

x 4

x 5

x 6

4/5-(31/5-2/5):12/5

1-(0 • -2/5):12/5

-2/5-(12/5-2/5):12/5

1/5-(-1/5-2/5):12/5

0-(0 • -2/5):12/5

0-(-1 • -2/5):12/5

0-(1 • -2/5):12/5

44/5-(31/5 • 13/5):12/5

0-(0 • 13/5):12/5

13/5-(12/5 • 13/5):12/5

1/5-(-1/5 • 13/5):12/5

1-(0 • 13/5):12/5

0-(-1 • 13/5):12/5

0-(1 • 13/5):12/5

31/5 : 12/5

0 : 12/5

12/5 : 12/5

-1/5 : 12/5

0 : 12/5

-1 : 12/5

1 : 12/5

(0)-(31/5 • (-44/5+12/5M)):12/5

(0)-(0 • (-44/5+12/5M)):12/5

(-44/5+12/5M)-(12/5 • (-44/5+12/5M)):12/5

(-3/5-M)-(-1/5 • (-44/5+12/5M)):12/5

(0)-(0 • (-44/5+12/5M)):12/5

(-M)-(-1 • (-44/5+12/5M)):12/5

(0)-(1 • (-44/5+12/5M)):12/5

 

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x6

x1

15/7

1

0

1/7

0

-2/7

2/7

x4

11/7

0

0

3/7

1

11/7

-11/7

x2

22/7

0

1

-1/7

0

-5/7

5/7

F(X2)

84/7

0

0

-12/7

0

-33/7

33/7-M

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

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

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

Базис

B

x1

x2

x3

x4

x5

x6

x1

15/7

1

0

1/7

0

-2/7

2/7

x4

11/7

0

0

3/7

1

11/7

-11/7

x2

22/7

0

1

-1/7

0

-5/7

5/7

F(X3)

84/7

0

0

-12/7

0

-33/7

33/7-M

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

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

x1 = 15/7 

x2 = 22/7 

F(X) = -3•15/7 + 6•22/7 = 84/7 

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 11/7 

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение -12/7 в столбце x3 означает, что теневая цена (двойственная оценка) равна -12/7.

Значение -33/7 в столбце x5 означает, что теневая цена (двойственная оценка) равна -33/7.

Значение 33/7-1M в столбце x6 означает, что теневая цена (двойственная оценка) равна 33/7-1M.

Ответы на вопросы преподавателя: 

1. По какому методу пересчитываются симплекс-таблицы? 

Используется правило прямоугольника (метод жордановских преобразований).

2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки? 

Можно не выбирать, но это может привести к зацикливанию алгоритма.

3. В индексной строке в n-ом столбце нулевое значение. Что это означает? 

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

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

 

 




1. Основи наукових досліджень Складання глосарію.html
2. В течение более чем двухтысячелетнего периода идет не только развитие представлений о душе
3. тема национального масштаба Основу системы GIE составляют карты и межбанковская сеть объединения банк.html
4. пуск Великий адронний коллайдер це грандіозна споруда створена для дослідження елементарних частинок
5. Вариант 13
6. Лабораторная работа 11 Исследование трехфазной цепи при соединении нагрузки звездой Для технических
7. Газпромкомплект ПНЕВМАТИЧЕСКАЯ СТРУБЦИНА ПСВ1 Инструкция по эксплуатации
8. Искусственное пополнение эксплуатационных запасов подземных вод
9. подлечить световую волну следует её какимто образом зафиксировать и обычная фотография для
10. Лабораторная работа 2 Текстовый процессор как инструмент информатики