Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Контрольная работа по прикладной математике (вариант 8) - файл №8.doc


Лабораторная работа - Контрольная работа по прикладной математике (вариант 8)
скачать (65 kb.)

Доступные файлы (1):

№8.doc383kb.17.04.2009 18:36скачать

содержание
Загрузка...

№8.doc

Реклама MarketGid:
Загрузка...
Задача №6

Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить а11 кг. сырья 1 типа, а21 кг. сырья 2 типа, а31 кг. сырья 3 типа. На изготовление единицы Изделия 2 требуется затратить а12 кг. сырья 1 типа, а22 кг. сырья 2 типа, а32 кг. сырья 3 типа.

Производство обеспечено сырьем каждого типа в количестве b1, b2, b3 кг. соответственно.

Рыночная цена единицы Изделия 1 = С1 тыс. руб., Изделия 2 = С2 тыс. руб.

Требуется:

  1. Построить математическую модель задач.

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

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

  4. Исследовать на устойчивость злп, при изменении ресурсов на ∆ bi = 0,1bi и определить двойственные оценки y1, y2, y3. Проверить правильность решения задачи: Zmax = fmin. Определить новые значения базисных решений. Посчитать Zнов max , fнов min и проверить Zнов max = fнов min.

а11 = 5 а12 = 4 b1 = 810

а21 = 4 а22 = 2 b2 = 980

а31 = 2 а32 = 6 b3 = 786

C1 = 34 C2 = 36

^ Построение экономико-математической модели задачи

Составим следующую таблицу:




Изделие 1

Изделие 2

Изделие 3

Сырье 1

5

4

810

Сырье 2

4

2

980

Сырье 3

2

6

786

Цены на изд.

34

36




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

Пусть выпущено х1 шт. Изделия 1 и х2 шт. Изделия 2.

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

F = 34x1 + 36x2 max

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

Сырье 1: 5х1 + 4х2 (кг)

Сырье 2: 4х1 + 2х2 (кг)

Сырье 3: 2х1 + 6х2 (кг)

Мы не можем израсходовать сырья больше, чем имеется в наличии. Кроме того, по смыслу задачи, х1 ≥ 0, х2 ≥ 0. в результате получаем систему линейных ограничений данной задачи:



Целевая функция F вместе с системой ограничений представляет собой экономико-математическую модель данной задачи.

^ Решение производственной задачи графическим методом.

Построение множества решений системы линейных ограничений.

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

1 + 4х2 = 810

х1 0 162

х2 202,5 0
1 + 2х2 = 980

х1 0 245

х2 490 0
1 + 6х2 ≤ 786

х1 0 393

х2 131 0
Решением системы является многоугольник OABC. Найдем координаты вершин OABC:

О (0;0), А (0;131), С (162;0)

Координаты точки B, решив систему уравнений:



По правилу Крамера:

х1 =
х2 =
Т. о. B (78;105)

Вычисляем значение угловой функции F в каждой вершине и выбираем наибольшее:

О =› F (0;0) = 34*0 + 36*0 = 0

А =› F (0;131) = 34*0 + 36-131 = 4716

В =› F (78;105) = 34*78 - 36*105 = 6432

С =› F (162;0) = 34*162 + 36*0 = 5508

Т. о оптимальный план выпуска изделий соответствует точке В и равен х1 = 78 шт., х2 = 105 шт. Выручка от реализации в этом случае будет максимальной и составит 6432 тыс. руб.

Найдем остатки сырья каждого типа х3, х4, х5:

х3 = 810 – 5х1 – 4х2 = 810-5*78-4*105=0

х4 = 980 – 4х1 – 2х2 = 980-4*78-2*105=458

х5 = 768 – 2х1 – 6х2 = 768-2*78-6*105=0

^ Симплексный метод решения задачи.

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

- остатки сырья первого типа;

- остатки сырья второго типа;

- остатки сырья третьего типа.

Тогда система ограничений задачи примет вид:



Полученные уравнения выражают собой баланс сырья в процессе производства.
Построение симплекс-таблицы № 1.

Симплекс-таблица № 1




Неизвестные




Базис

x1

x2

x3

x4

x5

bi

x3

5

4

1

0

0

810

x4

4

2

0

1

0

980

x5

2

6

0

0

1

786

-F

34

36

0

0

0

0


1)Последняя строка таблицы называется индексной. В ней размещены стоимости выпускаемых изделий в соответствующих столбцах, а в последнем столбце этой индексной строки стоит -F, получаемая сумма с обратным знаком от реализации предполагаемого к выпуску количества изделий.

Для первой симплекс-таблицы свободными переменными будут х1, x2, которые «автоматически» приравниваются к нулю. Очевидно, что это соответствует нулевому плану выпуска изделий, поэтому базисные переменные будут равны x3 = 810, x4 = 980, x5 = 786.

Значение целевой функции при этом, естественно, равно нулю:

.

Построение симплекс-таблицы № 2.

1) В индексной строке таблицы № 1 находим максимальный положительный элемент. Это число 36, оно соответствует второму столбцу. Второй столбец будем называть ключевым, ему соответствует переменная х2.

2) Составляем отношения элементов последнего столбца к соответствующим элементам ключевого столбца:

.

Среди этих трёх чисел выбираем наименьшее, это число 131, соответствующее предпоследней строке таблицы. Эту строку будем называть ключевой строкой. Ей соответствует базисная переменная х5.

3) Элемент, расположенный на пересечении ключевой строки и ключевого столбца а*=6 , называется разрешающим.

4) Свободную переменную х2, соответствующую ключевому столбцу, вводим в базис вместо переменной x5, соответствующей ключевой строке.

5) Все элементы ключевой строки делим на разрешающий элемент а*=6, и результаты вносим в соответствующую строку новой таблицы №2.

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

7). Все остальные элементы преобразуем по правилу прямоугольника.

Сформулируем это правило: для каждого элемента aij составляем прямоугольник так, чтобы этот элемент и разрешающий элемент а* располагались на одной диагонали прямоугольника:



Через A и B обозначим элементы, лежащие на другой диагонали. Тогда новое значение элемента вычисляется по формуле: .

Пересчитываем первую строку:



Пересчитываем вторую строку:



Пересчитываем индексную строку:



8) В результате получаем симплекс-таблицу № 2.

Симплекс-таблица № 2




Неизвестные




Базис

x1

x2

x3

x4

x5

bi

x3



0

1

0



286

x4



0

0

1



718

x2



1

0

0



131

-F

22

0

0

0

-6

-4716

Симплекс-таблице № 2 соответствует следующее решение задачи линейного программирования:

x1=0 шт; x2=131 шт; x3=286 кг; x4=718 кг, x5=0 кг; F =4716 тыс. руб.

8) Проверяем симплекс-таблицу №2 на оптимальность.

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

3.3. Построение симплекс-таблицы № 3.

1) В индексной строке таблицы № 2 находим максимальный положительный элемент. Это число 22, оно соответствует первому столбцу. Первый столбец будем называть ключевым, ему соответствует переменная х1.

2) Составляем отношения элементов последнего столбца к соответствующим элементам ключевого столбца:



Среди этих трёх чисел выбираем наименьшее, это число 78, соответствующее первой строке таблицы. Первую строку будем называть ключевой строкой. Ей соответствует базисная переменная х3.

3) Элемент, расположенный на пересечении ключевой строки и ключевого столбца , называется разрешающим.

4) Свободную переменную х1, соответствующую ключевому столбцу, вводим в базис вместо переменной x3, соответствующей ключевой строке.

5) Все элементы ключевой строки делим на разрешающий элемент , и результаты вносим в соответствующую строку новой таблицы №3.

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

7) Все остальные элементы преобразуем по правилу прямоугольника.

Пересчитываем вторую строку:



Пересчитываем третью строку:



Пересчитываем индексную строку:



8) В результате получаем симплекс-таблицу № 3.

Симплекс-таблица № 3




Неизвестные




Базис

x1

x2

x3

x4

x5

bi

x1

1

0



0



78

x4

0

0



1



458

x2

0

1



1



105

-F

0

0

-6

0

-2

-6432

Симплекс-таблице № 3 соответствует следующее решение задачи линейного программирования:

x1=78 шт; x2=105 шт; x3=0 кг; x4=458 кг, x5=0 кг; F =6432 тыс. руб.

8) Проверяем симплекс-таблицу №3 на оптимальность.

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

^ Ответ: Оптимальный план выпуска изделий составляет x1=78 шт. Изделия 1 и x2=105 шт. Изделия 2. Выручка от их последующей реализации в этом случае будет максимальна и составит 6288 тыс. руб. При этом все запасы Сырья I и Сырья III будут израсходованы полностью, а остаток Cырья II составит 458 кг.


^ Двойственная задача.

Выпишем еще раз симплекс-таблицу № 3 и обратим внимание на те столбцы этой таблицы, которые соответствуют переменным x3, x4, x5.
Симплекс-таблица № 3




Неизвестные




Базис

x1

x2

x3

x4

x5

bi

x1

1

0



0



78

x2

0

0



1



458

x5

0

1



1



105

-F

0

0

-6

0

-2

-6432

На пересечении индексной строки и столбцов, соответствующих дополнительным переменным, расположены числа –6, 0, -2.

Эти числа представляют собой взятые с противоположным знаком двойственные оценки сырья первого, второго и третьего типа соответственно: y1=6; y2=0; y3=2.
Составим матрицу D, элементы которой находятся в столбцах первоначального базиса, определяющих базисными элементами в симплекс таблице:
D =

D-1 =

хбаз = D-1 * bисх = =

∆b1 = 0,1*810=81

∆b2 = 0,1*980=98

∆b3 = 0,1*786=78,6
bнов 1 = 810+81=891

bнов2 = 980+98=1078

bнов3 = 786+78,6=864,6


xнов = D-1 * bнов = = › 0 =› решение устойчивое
Zнов max = 6*85,8+0*503,8+2*115,5=745,8

Задача №7.

На 3 базах А1, А2, А3 находится однородный груз в количестве a1, а2, а3. Этот груз надо доставить пяти потребителям: В1, В2, В3, В4, В5, потребности которых составляют b1, b2, b3, b4, b5. Известны тарифы, т.е. затраты на перевозку 1 т. груза от каждого склада до каждого потребителя Сij тыс.руб/т и значение а1, а2, а3, b1, b2, b3, b4, b5, которые приведены в таблице №1. Требуется:

  1. Найти первый опорный план методом минимальных тарифов.

  2. Построить оптимальный план перевозок методом потенциалов.


Таблица № 1

Поставщики

Потребители

Запасы

В1

В2

В3

В4

В5

А1




5




8




15




20




9

240































А2




8




7




6




12




14

160































А3




16




11




19




10




5

200































Потребность

180

40

160

120

100





^ 1. Построение исходного опорного плана транспортной задачи методом минимальных тарифов.

В таблице №1 находим клетку с наименьшим тарифом. Это клетки (1,1) и (3,5). Например, будем заполнять первой клетку (1,1).

В нее вместо x11 надо записать поставку, которую находим как минимум значения а1 = 240 m запаса груза на первой базе и значения b1 = 180 т заявки от первого магазина, т.е. x11 = min{240, 180} =180. Потребности в грузе первого магазина удовлетворены. Поэтому заполняем оставшиеся клетки первого столбца нулями. Запасы груза у первого поставщика уменьшились на величину 180 m.

Среди оставшихся клеток снова находим пустую клетку с наименьшим тарифом. Это клетка (3,5), в ней c52=5. Вместо неизвестной поставки x35 записываем значение тin{100, 200} =100. Потребности в грузе пятого магазина удовлетворены, пустые клетки пятого столбца заполняем нулями. Запасы груза у третьего поставщика уменьшились на величину 100 m.

Аналогично заполняем остальные клетки таблицы.

В результате получим таблицу № 2.

Таблица № 2

Поставщики

Потребители

Запасы

В1

В2

В3

В4

В5

А1




5




8




15




20




9

240

180




40




0




20




0




А2




8




7




6




12




14

160

0




0




160




0




0




А3




16




11




19




10




5

200

0




0




0




100




100




Потребность

180

40

160

120

100




Проверим полученный опорный план на вырожденность. Считаем количество ненулевых клеток в таблице 2, их шесть. Значение m+n-1=3+5-1=7 равно семи, значит, полученный опорный план вырожденный. Вводим нулевую поставку в клетку (2, 2)

9. Вычисляем транспортные расходы при таком плане перевозок, перемножая значения, стоящие в нижних и верхних уголках каждой из ненулевых клеток:



^ II. Нахождение оптимального плана транспортной задачи методом потенциалов.

1. Определим потенциалы каждого поставщика Аi и каждого потребителя Вj. Для этого поставим в соответствие поставщикам А1, А2, А3, потенциалы 1, 2, , 3, а потребителям B1, B2 , B3 , B4, B5, потенциалы 1, 2, 3, 4, 5.

2. Для нахождения потенциалов составляем для каждой ненулевой клетки соотношения i + j = сij :


1 + 1 = с11 = 5;

1 + 2 = с12 = 8;

1 + 4 = с14 = 20;

2 + 2 = с22 = 7;

2 + 3 = с23 = 6;

3 + 4 = с34 = 10;

3 + 5 = с35 = 5;

Для решения системы полагаем 1=0. Тогда:

1 = 0

1 = 5

4 = 20

2 = -1

2 = 8

5 = 15

3 = -10

3 = 7





Занесем их в таблицу №2. В результате получим таблицу № 3.

Таблица № 3

Поставщики

Потребители

Запасы

В1

1=5

В2

2=-8

В3

3=7

В4

4=20

В5

5=15

А1 1=0




5




8




15




20




9

240

180




40










20










А22=-1




8




7




6




12




14

160







0




160
















А33=-10




16




11




19




10




5

200



















100




100




Потребность

180

40

160

120

100




Определим косвенные тарифы сij*=i + j.для каждой незаполненной клетки таблицы №3.

с13*= 1 + 3 = 0-+7 = 7,

с15* = 1 + 5=0 + 15 = 15,

с21* = 2 + 1 = -1 + 5 = 4,

с24* = 2 + 4 = -1 +20 = 19

с25* = 2 + 5 =-1 + 15 =1 4,

с31* = 3 + 1 = -10 + 5 = -5,

с32* = 3 + 2 = -10 + 8 = -2,

с33* = 3 + 3 = -10 + 7 = -3.

Определим для каждой незаполненной клетки критерий оптимальности :

13 = 7 – 15 = -8 0

15 = 15 – 9 = 6 > 0

21 = 4 – 8 = -4 0

24 = 19 – 12 = 7> 0

25 = 14– 14 = 0= 0

31 = -5 – 16 = -21 0

32 =-2 – 11 = -13 0

33 = -3 – 19 = -22 0.

Так как среди полученных оценок ij есть положительные то, план перевозок не оптимален и его необходимо улучшить.

Таблица № 4

Поставщики

Потребители

Запасы

В1

1=4

В2

2=-8

В3

3=6

В4

4=5

В5

5=7

А1 1=0




5




8




15




20




9

240

180




40










20










А22=3




8




7




6




12




14

160







0




160
















А33=13




16




11




19




10




5

200



















100




100




Потребность

180

40

160

120

100




Для клеток (1,5), (2,4) ij > 0. Среди них выбираем клетку с максимальным значением ij. Это клетка с номером (2, 4). Ставим в ней знак "+".

Для нее строим цикл, вычеркивая в таблице №4 те столбцы и строки, в которых есть только одна поставка, считая, что в клетке (2, 4) также есть поставка.

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

Каждой вершине цикла будут соответствовать чередующиеся знаки "+" или "-", расставлять которые надо, начиная с "+" в клетке (2, 4), для которой мы строим этот цикл.

Затем в тех вершинах, где стоит знак "-", находим наименьшую поставку min{0, 20}. Это 0 в вершине (2, 2).

Обозначим эту величину Δ = 0, и теперь величину Δ вычитаем из поставок в вершинах со знаком "-" и прибавляем в те вершины, где стоит "+".
(1,2) 40 + (1,4) 20 - (1,2) 40 (1,4) 20

(2,2) 0 - (2,4) 0 + (2,2) 0 (2,4) 0

старый цикл
Заменяя старый цикл в таблице №4 на новый, получаем таблицу №5.

Таблица № 5

Поставщики

Потребители

Запасы

В1

1

В2

2

В3

3

В4

4

В5

5

А1 1




5




8




15




20




9

240

180




40










20










А22




8




7




6




12




14

160













160




0










А33




16




11




19




10




5

200



















100




100




Потребность

180

40

160

120

100




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

Определяем потенциалы каждого поставщика Аi и каждого потребителя Вj. Для чего составляем для каждой заполненной клетки таблицы № 5 соотношения

i + j = сij

1 + 1 = 5;

1 + 2 = 8;

1 + 4 = 20;

2 + 3= 6

2 + 4 =12

3 + 4= 10

3 + 5= 5

Полагаем 1 = 0 и решаем систему уравнений. В результате получаем:

1 = 0

1 = 5

4 = 20

2 = -8

2 = 8

5 =15

3 = -10

3 = 14




Определим косвенные тарифы с*ij для каждой незаполненной клетки таблицы №5

с13* = 1 + 3= 0 + 14 = 14

с15* = 1 + 5 = 0 + 15 = 15

с21* = 2 + 1 = -8+5= -3

с22* = 2 + 2 = -8 +8=0,

с25 = 2 + 5= -8+15= 7,

с31* = 3 + 1 = -10 + 5 = -5,

с32* = 3 + 2 = -10 + 8 = -2,

с33* = 3 + 3 = -10 + 14 = 4.

Записываем рядом косвенные и истинные тарифы, а также критерий оптимальности:

с13* = 14, с13 = 15; 13 = 14 – 15 = -1 < 0,

с15* = 15, с15 = 9; 15 = 15 - 9 = 6 > 0,

с21* = -3, с21 = 8; 21 = -3 – 8 = -11 < 0,

с22* = 0, с22 = 7; 22 = 0 – 7 = -7 < 0,

с25* = 7, с25 = 14; 25 = 7 – 14 = -7 < 0,

с31* = -5, с31 = 16; 31 = -5 – 16 = -21 < 0,

с32* =-28, с32 = 11; 32 = -2 – 11 = -13 < 0,

с33* = 4, с33 = 19; 33 = 4 – 19 = -15 < 0.

Критерий оптимальности ij 0 выполнен не для всех клеток, значит план не оптимальный и его необходимо улучшить.

Для клетки (1,5) ij > 0. Для нее строим цикл, вычеркивая в таблице №5 те столбцы и строки, в которых есть только одна поставка, считая, что в клетке (1,5) также есть поставка.

Вычеркнутыми будут первый, второй и третий столбец, выделим их серым цветом. Все остальные заполненные клетки образуют цикл.
(1,4) 20 + (1,5) 0 - (1,4) 0 (1,5) 20

(3,4) 100 - 3,5) 100 + (3,4) 120 (3,5) 80

Заменяя старый цикл в таблице №5 на новый, получаем таблицу №6.

Таблица № 6

Поставщики

Потребители

Запасы

В1

1

В2

2

В3

3

В4

4

В5

5

А1 1




5




8




15




20




9

240

180




40
















20




А22




8




7




6




12




14

160













160




0










А33




16




11




19




10




5

200



















120




80




Потребность

180

40

160

120

100




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

Определяем потенциалы каждого поставщика Аi и каждого потребителя Вj. Для чего составляем для каждой заполненной клетки таблицы № 6 соотношения

i + j = сij

1 + 1 = 5;

1 + 2 = 8;

1 + 5 = 9;

2 + 3= 6

2 + 4 =12

3 + 4= 10

3 + 5= 5

Полагаем 1 = 0 и решаем систему уравнений. В результате получаем:

1 = 0

1 = 5

4 = 14

2 = -2

2 = 8

5 =9

3 = -4

3 = 8




Определим косвенные тарифы с*ij для каждой незаполненной клетки таблицы №5

с13* = 1 + 3= 0 + 8 = 8

с14* = 1 + 4 = 0 + 14 = 14

с21* = 2 + 1 = -2+5= 3

с22* = 2 + 2 = -2 +8=6,

с25 = 2 + 5= -2+9= 7,

с31* = 3 + 1 = -4 + 5 = 1,

с32* = 3 + 2 = -4 + 8 = 4,

с33* = 3 + 3 = -4 + 8 = 4.

Находим критерий оптимальности для каждой незаполненной клетки:

13 = 8 – 15 = -7 < 0,

14 = 14 - 20 =- 6 < 0,

21 = 3 – 8 = -5 < 0,

22 = 6 – 7 = -1 < 0,

25 = 7 – 14 = -7 < 0,

31 = 1 – 16 = -15 < 0,

32 = 4 – 11 = -7 < 0,

33 = 4 – 19 = -15 < 0.

Критерий оптимальности ij 0 выполнен для всех клеток, кроме того, все значения ij < 0. А это значит что полученный план перевозок оптимальный и единственный.

Вычисляем затраты на все планируемые перевозки:

Сравним найденное значение Fопт с затратами F, полученными при составлении первоначального опорного плана по методу наименьшей стоимости. Видим, что транспортные расходы уменьшились на величину:

F = F - Fопт = 4080 - 3960 = 120 (тыс. руб.).

Ответ: 1) Первоначальный опорный план перевозок, построенный по методу наименьшей стоимости, приведён в таблице № 2. При этом плане перевозок транспортные расходы составляют F=4080 тыс. руб.

2) Оптимальный план перевозок приведен в таблице № 6. При этом плане перевозок транспортные расходы составляют:Fопт=3960 тыс. руб. Экономия от улучшения этого опорного плана составляет F=F-Fопт=120тыс. руб.


Скачать файл (65 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации