47281 (571978), страница 2
Текст из файла (страница 2)
Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.
Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.
Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.
Задание 2
Задача 29
Условие:
Решение задачи линейного программирования.
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ( (B,
где (( = ( (1 (2 . . . (6 (( , В( = ( b1 b2 . . . b6 (( ,
(( = ( (1 (2 . . . (6(( , А= ((((( ((=1,6; (=1,3).
| № вар. | С1 | с2 | с3 | с4 | с5 | с6 | b1 | b2 | b3 |
| 29 | 0 | 5 | 1 | –1 | 1 | 0 | 2 | 2 | 10 |
| Знаки ограничений | a11 | a12 | a13 | a14 | ||||||
| 1 | 2 | 3 | ||||||||
| –1 | 1 | 1 | 0 | |||||||
| a15 | a16 | a21 | a22 | a23 | a24 | a25 | a26 |
| 0 | 0 | 1 | –2 | 0 | 1 | 0 | 0 |
| a31 | a32 | a33 | a34 | a35 | a36 | Тип экстрем. |
| 2 | 1 | 1 | 1 | 2 | 0 | max |
Решение:
Составим систему:
_ EMBED Equation.3 ___
Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max
Приведем систему ограничений к виду основной задачи линейного программирования.
_ EMBED Equation.3 ___
Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q= 0-(-5x2-x3 +x4- x5)
_ EMBED Equation.3 ___
Составим симплекс-таблицу:
Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.
Таблица 2.1
|
| b | x1 | x2 | x3 | x4 | x5 | |||||||||||||
| Q | 0 |
| 0 |
| -5 |
| -1 |
| 1 |
| -1 |
| |||||||
|
| 10 |
| -5 |
| 5 |
| 5 |
| 0 |
| 0 | ||||||||
| x6 | 2 |
| -1 |
| 1 |
| 1 | 0 |
| 0 |
| 2/1=2min | |||||||
|
| 2 |
| -1 |
| 1 | 1 |
| 0 |
| 0 | |||||||||
| x7 | 2 |
| 1 |
| -2 |
| 0 |
| 1 |
| 0 |
| |||||||
|
| 4 |
| -2 |
| 2 |
| 2 |
| 0 |
| 0 | ||||||||
| x8 | 10 |
| 2 |
| 1 |
| 1 | 1 |
| 2 |
| 10/2=5 | |||||||
|
| -2 |
| 1 |
| -1 |
| -2 |
| 0 |
| 0 | ||||||||
Меняем x2 и x6.
Таблица 2.2
|
| b | x1 | x6 | x3 | x4 | x5 | |||||||
| Q | 10 |
| -5 |
| 5 |
| 4 |
| 1 |
| -1 |
| |
|
| 4 | 1,5 |
| -1 | -1 |
| 0,5 | 0,5 | |||||
| x2 | 2 |
| -1 |
| 1 |
| 1 |
| 0 |
| 0 |
| |
|
| 0 |
| 0 |
| 0 |
| 0 |
| 0 |
| 0 | ||
| x7 | 6 |
| -1 | 2 |
| 2 | 1 |
| 0 |
| |||
|
| 0 |
| 0 |
| 0 |
| 0 |
| 0 | 0 | |||
| x8 | 8 |
| 3 | -1 |
| -1 | 1 | 2 |
| ||||
|
| 4 |
| 6 |
| -2 |
| -2 |
| 2 |
| 0,5 | ||
Меняем x5 и x8.
Таблица 2.3
|
| b | x1 | x6 | x3 | x4 | x8 | |||||||||||
| Q | 14 |
| -3.5 |
| 4,5 |
| 3,5 |
| 1,5 |
| 0,5 |
| |||||
|
| 21 | 5,25 |
| -2,625 | -2,625 |
| 2,625 |
| 2,625 | ||||||||
| x2 | 2 |
| -1 |
| 1 |
| 1 |
| 0 |
| 0 |
| |||||
|
| 8/3 |
| 2/3 |
| -1/3 |
| -1/3 |
| 1/3 |
| 1/3 | ||||||
| x7 | 6 |
| -1 | 2 |
| 2 | 1 | 0 |
| ||||||||
|
| 8/3 | 2/3 |
| -1/3 |
| -1/3 |
| 1/3 |
| 1/3 | |||||||
| x5 | 4 | 1,5 | -0,5 |
| -1 | 0,5 | 0,5 |
| |||||||||
|
| 8/3 |
| 2/3 |
| -1/3 |
| -1/3 |
| 1/3 |
| 1/3 | ||||||
Меняем x5 и x1.
Таблица 2.4
| b | x5 | x6 | x3 | x4 | x8 | |
| Q | 35 | 5,25 | 1,875 | 0,875 | 4,125 | 3,125 |
| x2 | 14/3 | 2/3 | 2/3 | 2/3 | 1/3 | 1/3 |
| x7 | 26/3 | 2/3 | 5/3 | 5/3 | 4/3 | 1/3 |
| x1 | 8/3 | 2/3 | -1/3 | -1/3 | 1/3 | 1/3 |
Получили оптимальное решение, т.к. все коэффициенты положительны.
Следовательно Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Ответ: Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Задание 3
Задача 9
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
Таблица 1
| №вар. | а1 | а2 | а3 | 1 | 2 | 3 | 4 | 5 | с11 | с12 | с13 |
| 9 | 300 | 700 | 1000 | 200 | 100 | 400 | 600 | 200 | 23 | 40 | 10 |
| с14 | с15 | с21 | с22 | с23 | с24 | с25 | с31 | с32 | с33 | с34 | с35 |
| 12 | 21 | 25 | 21 | 20 | 50 | 18 | 15 | 30 | 32 | 25 | 50 |
Решение:
Составим таблицу транспортной задачи.
Таблица 2
|
| B1 | B2 | B3 | B4 | B5 | a |
| A1 |
|
|
|
|
|
|
| 23 | 40 | 10 | 12 | 21 | 300 | |
| A2 |
|
|
| |||
| 25 | 21 | 20 | 50 | 18 | 700 | |
| A3 |
|
|
|
|
|
|
| 15 | 30 | 32 | 25 | 50 | 1000 | |
| b | 200 | 100 | 200 | 600 | 200 |
|
Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.
Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.
Таблица 3
|
| B1 | B2 | B3 | B4 | B5 | В6 | a |
| A1 |
|
|
| 300 |
|
|
|
| 23 | 40 | 10 | 12 | 21 | 0 | 300 | |
| A2 | 100 | 200 |
| 200 | 200 |
| |
| 25 | 21 | 20 | 50 | 18 | 0 | 700 | |
| A3 | 200 |
|
| 300 |
| 500 |
|
| 15 | 30 | 32 | 25 | 50 | 0 | 1000 | |
| b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Это будет опорный план.
Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___
Таблица 4
|
| B1 | B2 | B3 | B4 | B5 | В6 | a |
| A1 |
|
|
| 300 |
|
| 300 |
| 23 | 40 | 10 | 12 | 21 | 0 | ||
| A2 |
| 100 | 200 |
| 200 | 200 | 700 |
| 25 | 21 | 20 | 50 | 18 | 0 | ||
| A3 | 200 |
|
| 300 |
| 500 | 1000 |
| 15 | 30 | 32 | 25 | 50 | 0 | ||
| b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
Таблица 5
|
| β1=2 | β2=8 | β3=7 | β4=12 | β5=6 | β6=-13 | a |
| α1=0 |
|
|
| 300 |
|
| 300 |
| 23-2>0 | 40-8>0 | 10-7>0 | 12-12=0 | 21-6>0 | 0-(-13)>0 | ||
| α2=13 | 100 | 200 |
| 200 | 200 | 700 | |
| 25-13-2>0 | 21-8-13=0 | 20-7-13=0 | 50-12-13>0 | 18-6-13=0 | 0-13+13=0 | ||
| α2=13 | 200 |
|
| 300 |
| 500 | 1000 |
| 15-13-2=0 | 30-13-8>0 | 32-13-7>0 | 25-13-2=0 | 50-13-6>0 | 0-13+13=0 | ||
| b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.
Тогда сумма всех перевозок:
L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800
Ответ:
|
| B1 | B2 | B3 | B4 | B5 | В6 | a |
| A1 |
|
|
| 300 |
|
|
|
| 23 | 40 | 10 | 12 | 21 | 0 | 300 | |
| A2 | 100 | 200 |
| 200 | 200 |
| |
| 25 | 21 | 20 | 50 | 18 | 0 | 700 | |
| A3 | 200 |
|
| 300 |
| 500 |
|
| 15 | 30 | 32 | 25 | 50 | 0 | 1000 | |
| b | 200 | 100 | 200 | 600 | 200 | 700 | 2000 |
Задание 4
Задача 54
Условие:
Определить экстремум целевой функции вида
( = (11(12+(22(22+(12(1(2+(1(1+(2(2
при условиях:
(11(1+(12(2(1
(21(1+(22(2(2 .
Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
Составить функцию Лагранжа.
Получить систему неравенств в соответствии с теоремой Куна-Таккера.
Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
-
Дать ответ с учетом условий дополняющей нежесткости.
| № | b1 | b2 | c11 | c12 | c22 | extr | a11 | a12 | a21 | a22 | p1 | p2 | Знаки огр. 1 2 | |
| | –7 | –2 | 4 | 1.5 | –2 | min | –2 | 1.5 | 4 | –3 | 18 | 9 | ||
Решение:
1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min
Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max
Ограничения g1(x) и g2(x): _ EMBED Equation.3 ___ →_ EMBED Equation.3 ___
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
