Студопедия

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

КАТЕГОРИИ:

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






Задача 4. Смесь можно составить из n продуктов Сj (j=1,n)






Смесь можно составить из n продуктов Сj (j=1, n). В каждом из продуктов содержится m компонентов. Минимально допустимый объем содержания i-го компонента в смеси выражается величиной bi (i=1, 3). Содержание i-го компонента в единице j-го продукта выражается величиной аij . Цена единицы j-го продукта равна сj . Составить смесь, минимальную по стоимости, выбрав для решения данной задачи наиболее рациональный способ.

  C1 C2 C3 bi
cj        
a1j        
a2j        
a3j        

 

Смесь, минимальная по стоимости:

7x1 + 5x2 + 8x3 ≥ 70

8x1 + 2x2 + 3x3 ≥ 40

9x1 + 6x2 + 7x3 ≥ 50

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0

F = 9x1 + 6x2 + 7x3 → min

 

После транспонирования матрицы элементов aij, cсимметричная двойственная задача будет иметь вид:

S(y1, y2, y3) = 70y1 + 40y2 + 50y3 → max, при ограничениях:

7y1 + 8y2 + 9y3 ≥ 9

5y1 + 2y2 + 6y3 ≥ 6

8y1 + 3y2 + 7y3 ≥ 7

y1 ≥ 0; y2 ≥ 0; y3 ≥ 0

 

Для решения двойственной задачи линейного программирования симплекс – методом, приведём систему неравенств к виду системы уравнений:

7y1 + 8y2 + 9y3 + y4 ≥ 9

5y1 + 2y2 + 6y3 + y5 ≥ 6

8y1 + 3y2 + 7y3 + y6 ≥ 7

y1≥ 0; y2≥ 0; y3≥ 0; y1≥ 0; y2≥ 0; y3≥ 0

S(y1, y2, y3) = 70y1 + 40y2 + 50y3 → max

 

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

x1 x2 x3 x4 x5 x6

 

y1 y2 y3 y4 y5 y6

 

Первая симплексная таблица:

Базис Сб А0 y1 y2 y3 y4 y5 y6
y4                
y5                
y6                
      -70 -40 -50      

 

Вторая симплексная таблица:

Базис Сб А0 y1 y2 y3 y4 y5 y6
y4   23/8   43/8 23/8     -7/8
y5   13/8   1/8 13/8     -5/8
y1   7/8   3/8 7/8     1/8
    245/4   -55/4 45/4     35/4

 

Третья симплексная таблица:

Базис Сб А0 y1 y2 y3 y4 y5 y6
Y2   23/43     23/43 8/43   -7/43
y5   67/43     67/43 -1/43   -26/43
y1   29/43     29/43 -3/43   8/43
    2950/43     800/43 110/43   280/43

 

В последней таблице в строке Δ нет отрицательных элементов. В соответствии с критерием оптимальности точка максимума Smax = 2950/43 достигнута при значениях: y1 = 29/43; y2 = 23/43; y3 = 0.

По теореме двойственности: Fmin = Smax = 2950/43.

На основании правила соответствия между переменными, оптимальное решение прямой задачи:

y4 x1 = 110/43 y5 x2 = 0 y6 x3 = 280/43

Ответ: В смесь минимальной стоимости 2950/43 целесообразно включить 110/43 единиц продукта C1, 280/43 единиц продукта C3, а продукт C2 не включать.


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

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