Шифр 14: задачи 37, 45. На трех базах имеется груз в количестве 270, 300, 230 единиц

  • ID: 27691 
  • 7 страниц

Фрагмент работы:

Шифр 14: задачи 37, 45. На трех базах имеется груз в количестве 27…

Задача 37.

На трех базах, имеется груз в количестве 270, 300, 230 единиц. Этот груз нужно перевезти в пять, пунктов в количестве 170, 110, 200, 140, 180 единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов :

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Решение:

Запишем данные задачи в виде матрицы перевозок.

bj

ai 1 2 3 4 5

170 110 200 140 180

1 270 25 12 7 18 10

2 300 35 13 12 15 3

3 230 30 16 11 25 16

Проверим, является ли задача закрытой:

=270+300+230=800

=170+110+200+140+180=800

=, Þ транспортная задача закрытая.

Заполним матрицу перевозок методом минимального тарифа.

bj

ai 1 2 3 4 5 ai

170 110 200 140 180

1 270 25 70 12 200 7 18 10 0

2 300 35 40 13 12 80 15 180 3 1

3 230 170 30 16 11 60 25 16 11

bj 19 12 7 14 2

Стоимость перевозок при таком плане

Z=12×70+7×200+13×40+15×80+3×180+30×170+25×60=11100 тыс. руб.

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

Пусть a1=0, тогда a2=1

a3=11

b1=19

b2=12

b3=7

b4=14

b5=2

Проверим на оптимальность пустые клетки:

клетка (1;1): 0+19 < 25

клетка (1;4): 0+14 < 18

клетка (1;5): 0+2 < 10

клетка (2;1): 1+19 < 35

клетка (2;3): 1+7 < 12

клетка (3;2): 11+12 > 16

клетка (3;3): 11+7 > 11

клетка (3;5): 11+2 < 16

Выберем в качестве неоптимальной клетку (3;3) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 ai

170 110 200 140 180

1 270 25 110 12 160 7 18 10 0

2 300 35 13 12 120 15 180 3 -6

3 230 170 30 16 40 11 20 25 16 4

bj 26 12 7 21 9

Найдем потенциалы.

Пусть a1=0, тогда a2=-6

a3=4

b1=26

b2=12

b3=7

b4=21

b5=9

Проверим на оптимальность пустые клетки:

клетка (1;1): 0+26>25

клетка (1;4): 0+21>18

клетка (1;5): 0+9 < 10

клетка (2;1): -6+26 < 35

клетка (2;2): -6+12 < 13

клетка (2;3): -6+7 < 12

клетка (3;2): 4+12=16

клетка (3;5): 4+9 < 16

Выберем в качестве неоптимальной клетку (1;4) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 ai

170 110 200 140 180

1 270 25 110 12 140 7 20 18 10 0

2 300 35 13 12 120 15 180 3 -3

3 230 170 30 16 60 11 25 16 4

bj 26 12 7 18 6

Найдем потенциалы.

Пусть a1=0, тогда a2=-3

a3=4

b1=26

b2=12

b3=7

b4=18

b5=6

Проверим на оптимальность пустые клетки:

клетка (1;1): 0+26>25

клетка (1;5): 0+6 < 10

клетка (2;1): -3+26 < 35

клетка (2;2): -3+12 < 13

клетка (2;3): -3+7 < 12

клетка (3;2): 4+12=16

клетка (3;4): 4+18 < 25

клетка (3;5): 4+6 < 16

Выберем в качестве неоптимальной клетку (1;1) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 ai

170 110 200 140 180

1 270 140 25 110 12 7 20 18 10 0

2 300 35 13 12 120 15 180 3 -3

3 230 30 30 16 200 11 25 16 5

bj 25 12 6 18 6

Найдем потенциалы.

Пусть a1=0, тогда a2=-3

a3=5

b1=25

b2=12

b3=6

b4=18

b5=6

Проверим на оптимальность пустые клетки:

клетка (1;3): 0+6 < 7

клетка (1;5): 0+6 < 10

клетка (2;1): -3+25 < 35

клетка (2;2): -3+12 < 13

клетка (2;3): -3+6 < 12

клетка (3;2): 5+12>16

клетка (3;4): 5+18 < 25

клетка (3;5): 5+6 < 16

Выберем в качестве неоптимальной клетку (3;2) и перейдем к следующей матрице перевозок.

bj

ai 1 2 3 4 5 ai

170 110 200 140 180

1 270 170 25 80 12 7 20 18 10 0

2 300 35 13 12 120 15 180 3 -3

3 230 30 30 16 200 11 25 16 4

bj 25 12 7 18 6

Найдем потенциалы.

Пусть a1=0, тогда a2=-3

a3=4

b1=25

b2=12

b3=7

b4=18

b5=6

Проверим на оптимальность пустые клетки:

клетка (1;3): 0+7=7

клетка (1;5): 0+6 < 10

клетка (2;1): -3+25 < 35

клетка (2;2): -3+12 < 13

клетка (2;3): -3+7 < 12

клетка (3;1): 4+25 < 30

клетка (3;4): 4+18 < 25

клетка (3;5): 4+6 < 16

Условие оптимальности выполняется для всех пустых клеток, поэтому план оптимальный. Стоимость перевозок при таком плане минимальна и равна:

Zmin=25×170+12×80+18×20+15×120+3×180+16×30+11×200=10590 тыс. руб.

Задача 45.

Составить экономико-математическую модель. Найти решение задачи линейного программирования при помощи средств Excel на ПК.

При подкормке посева нужно внести на 1 га почвы не менее 10 ед. химического вещества А, 25 ед. вещества Б, 20 ед. вещества В. Сельскохозяйственное предприятие закупает комбинированные удобрения четырех видов (I, II, III, IV). В таблице указаны содержание химических веществ и цена за единицу массы каждого вида удобрений. Минимизировать расходы по закупке необходимого количества удобрений.

Химическое вещество Содержание вещества в единице массы удобрения

I II III IV

А 1 5 2 1

Б 12 3 3 2

В 4 4 2 2

Цена 5 3 2 3

Решение:

Пусть x1, x2, x3, x4 – количество комбинированных удобрений каждого вида. Очевидно, что x1³0, x2³0, x3³0, x4³0.Составим ограничения по каждому химическому веществу:

А: x1+5x2+2x3+x4³10

Б: 12x1+3x2+3x3+2x4³25

В: 4x1+4x2+2x3+2x4³20

Требование минимизации затрат:

f=5x1+3x2+2x3+3x4®min

Требуется найти x1, x2, x3, x4, минимизирующие целевую функцию и удовлетворяющую указанным ограничениям, т.е. решить задачу линейного программирования:

f=5x1+3x2+2x3+3x4®min

Решим эту задачу с помощью Excel. Вводим в ячейки таблицы исходные данные:

A B C D E F G

1 1 5 2 1 0 10

2 12 3 3 2 0 25

3 4 4 2 2 0 20

4 5 3 2 3

5

6 x1 x2 x3 x4 f

7 0 0 0 0 0

8

9

10

В ячейках E1-E3 и E7 введены формулы.

E1: =СУММПРОИЗВ(A1:D1;A7:D7)

E2: =СУММПРОИЗВ(A2:D2;A7:D7)

E3: =СУММПРОИЗВ(A3:D3;A7:D7)

E7: =СУММПРОИЗВ(A7:D7;A7:D7)

Затем даем команду Сервис/Поиск решения:

Задаем следующие параметры:

в поле «Установить целевую ячейку»: $E$7

минимальное значение

в поле «Изменяя ячейки»: $A$7:$D$7

Далее задаем ограничения:

$A$7:$D$7³0

$E$1:$E$3³$F$1:$F$3

Затем нажимаем на кнопку «Выполнить».

Получаем ответ: x1=10/9, x2=35/9, x3=0, x4=0, fmin=155/9 (ден. ед.)