Технические темы
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.00 (1 Голос)

Задача линейного программирования с решением

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

Для решения задач линейного программирования разработаны симплекс-метод и его модификации.

Такие задачи, как и задачи нелинейного программирования, в Excel решают с помощью надстройки «Поиск решения..».

Пример задачи.

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

Решение задачи.

Исходные данные оформим на Листе:

 

A

B

C

D

E

F

G

Таблица 2.5. Состав тракторного парка

Марка трактора

Количество

     

Всего

Подлежит списанию

Останется

     

Т-4А

35

5

30

   

5

ДТ-75

47

7

40

   

6

МТЗ-50

43

3

40

   

7

Таблица 2.6. Состав парка сельскохозяйственных машин

Тип агрегата

Наличие машин на начало года к трактору

Из них подлежит списанию в текущем году

Т-4А

ДТ-75

МТЗ-50

Т-4А

ДТ-75

МТЗ-50

Плуги

34

40

7

4

5

1

Сеялочные агрегаты

35

41

10

2

3

3

Агрегаты для культивации

36

37

5

2

3

1

Агрегаты для боронования

35

44

0

3

5

0

Пропашные культиваторы

0

0

30

0

0

3

Таблица 2.7. Объемы и сроки выполняемых работ

Периоды, работы

Объем работ, га

Срок выполнения, дней

Выработка, га в день

   

Физических

Условных

   

Весенний по всем видам работ

 

13500

10

1350

 

21

в т.ч.: закрытие влаги

18000

 

6

3000

 

22

Предпосевная культивация

15000

 

5

3000

 

23

Сев зерновых

15000

 

5

3000

 

24

Летний по всем видам работ

 

10000

15

660

 

25

в т.ч.: междурядная обработка

1800

 

8

225

 

26

Осенний по всем видам работ

 

30000

25

1200

 

27

в т.ч. вспашка зяби

17000

 

25

680

 

28

Таблица 2.8. Выработка на трактор (физ.га за смену)

Работы

К-701

Т-4А

ДТ-75

МТЗ-50

   

Выработка в га условной пахоты

15.8

10.2

7

3

 

32

Закрытие влаги

72

47

32

0

 

33

Предпосевная культивация

68

45

31

0

 

34

Сев

78

50

35

0

 

35

Междурядная обработка пропашных

0

0

0

11.5

 

36

Вспашка зяби

12

7.6

5.5

0

 

37

A

B

C

D

E

F

G

                       

Расчет оформим на том же Листе, что и исходные данные:

A

B

C

D

E

F

G

Таблица 2.9. Потребное количество тракторов

Марка трактора

Количество

Годовые приведенные затраты, Грн

Коэффициент сменности

 

К-701

20

12000

2

 

50

Т-4А

30

9000

1

 

51

ДТ-75

40

6500

1

 

52

МТЗ-50

40

3500

1

 

53

Функция цели – минимальные суммарные годовые затраты:

975696,2

 

56

Таблица 2.10. Расчетный объем работ, выполненных за смену

Работы

Объем, га

Потребный объем, га

     

Выработка в га условной пахоты

1350

1350

   

60

Закрытие влаги

5624.684

3000

   

61

Предпосевная культивация

5361,646

3000

   

62

Сев

6079,241

3000

   

63

Междурядная обработка пропашных

460

225

   

64

Вспашка зяби

937,1139

680

   

65

.1В ячейки В60-В65 запишем формулы для выполняемых объемов работ:

, где (2.5)

Vi – объем работ данного вида (вспашка, закрытие влаги, культивация, сев, межрядная обработка, вспашка зяби); Eji – выработка в га/смену для j-го типа трактора на i-м виде работ; kj – коэффициент сменности для j-го типа трактора; Nj – количество тракторов j-го типа.

Формулы для ячеек:

B60=B32*$E$50*$B$50+C32*$E$51*$B$51+D32*$E$52*$B$52+E32*$E$53*$B$53

B61=B33*$E$50*$B$50+C33*$E$51*$B$51+D33*$E$52*$B$52+E33*$E$53*$B$53

B62=B34*$E$50*$B$50+C34*$E$51*$B$51+D34*$E$52*$B$52+E34*$E$53*$B$53

B63=B35*$E$50*$B$50+C35*$E$51*$B$51+D35*$E$52*$B$52+E35*$E$53*$B$53

B64=B36*$E$50*$B$50+C36*$E$51*$B$51+D36*$E$52*$B$52+E36*$E$53*$B$53

B65=B37*$E$50*$B$50+C37*$E$51*$B$51+D37*$E$52*$B$52+E37*$E$53*$B$53

  1. .2В ячейку Е56 занесем формулу для определения затрат на комплекс работ:

, где (2.6)

zj – годовые приведенные затраты для j-го типа трактора, Nj – количество тракторов j-го типа.

Формула для ячейки:

E56=C50*B50+C51*B51+C52*B52+C53*B53

  1. Вызовем надстройку «Поиск решения…» из меню «Сервис».
  2. .1В качестве целевой ячейки укажем Е56. Укажем маркер «Равной минимальному значению».
  3. .2Изменяемые параметры – ячейки В50:В53.
  4. .3Ограничения:

В50³0 - количество новых тракторов К-701 неотрицательно;

B51³D5, В52³D6, B53³D7 – все количество имеющихся в распоряжении тракторов должно быть задействовано;

B60³E21, B61³E22, B62³E23, B63³E24, B64³E26, B65³E28 – расчетные объемы работ по видам должны быть не меньше потребных.

  1. .4На вкладке «Параметры» установим маркер в поле «Линейная модель».
  2. .5Нажмем кнопку «Выполнить», Excel выполнит решение задачи и выведет на экран окно диалога «Результаты поиска решения». Если решение найдено, установим маркер на фразе «Сохранить найденное решение» и выделим все типы отчетов в окне «Тип отчета». После нажатия кнопки «ОК» в рабочей Книге создадутся Листы, содержащие выбранные типы отчетов.

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

Отчет по результатам

Целевая ячейка (Минимум)

       
 

Ячейка

Имя

Исходно

Результат

   
 

$E$56

Функция цели - миним.сумм.затраты

670000

975696,2

   

Изменяемые ячейки

       
 

Ячейка

Имя

Исходно

Результат

   
 

$B$50

К-701 Количество

0

20

   
 

$B$51

Т-4А Количество

30

30

   
 

$B$52

ДТ-75 Количество

40

40

   
 

$B$53

МТЗ-50 Количество

40

40

   

Ограничения

       
 

Ячейка

Имя

Значение

формула

Статус

Разница

 

$B$65

Вспашка зяби Объем, га

937,1

$B$65>=$E$28

не связан.

257,1

 

$B$60

Выработка в га условной пахоты Объем, га

1350

$B$60>=$E$21

связанное

0

 

$B$61

Закрытие влаги Объем, га

5624,68

$B$61>=$E$22

не связан.

2624,68

 

$B$62

Предпосевная культивация Объем, га

5361,65

$B$62>=$E$23

не связан.

2361,65

 

$B$63

Сев Объем, га

6079,24

$B$63>=$E$24

не связан.

3079,24

 

$B$64

Междурядная обработка пропашных Объем, га

460

$B$64>=$E$26

не связан.

235

 

$B$50

К-701 Количество

20

$B$50>=0

не связан.

20

 

$B$51

Т-4А Количество

30

$B$51>=$D$5

связанное

0

 

$B$52

ДТ-75 Количество

40

$B$52>=$D$6

связанное

0

 

$B$53

МТЗ-50 Количество

40

$B$53>=$D$7

связанное

0

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

Таблица «Ограничения» содержит зависимости, введенные в окно «Поиск решения», результирующие значения параметров-ограничений после нахождения оптимального решения, разницу между результирующими значениями и ограничивающей величиной (остаток неизрасходованного ресурса параметра), статус ограничения – если ресурс выбран полностью (равен 0), то указывается «связанное», иначе – «не связанное».

Отчет по устойчивости

Изменяемые ячейки

         
     

Результ.

Нормир.

Целевой

Допустимое

Допустимое

 

Ячейка

Имя

значение

стоимость

Коэфф-т

Увеличение

Уменьшение

 

$B$50

К-701 Количество

20

0

15000

12882,35

15000

 

$B$51

Т-4А Количество

30

4158

9000

1E+30

4158,23

 

$B$52

ДТ-75 Количество

40

3177

6500

1E+30

3177,21

 

$B$53

МТЗ-50 Количество

40

2076

3500

1E+30

2075,95

Ограничения

         
     

Результ.

Теневая

Огранич-е

Допустимое

Допустимое

 

Ячейка

Имя

значение

Цена

Пр.часть

Увеличение

Уменьшение

 

$B$65

Вспашка зяби Объем, га

937,1

0

680

257,11

1E+30

 

$B$60

Выработка в га условной пахоты Объем, га

1350

474,68

1350

1E+30

338,53

 

$B$61

Закрытие влаги Объем, га

5624,68

0

3000

2624,68

1E+30

 

$B$62

Предпосевная культивация Объем, га

5361,65

0

3000

2361,65

1E+30

 

$B$63

Сев Объем, га

6079,24

0

3000

3079,24

1E+30

 

$B$64

Междурядная обработка пропашных Объем, га

460

0

225

235

1E+30

Таблица «Изменяемые ячейки» содержит результирующие оптимальные значения изменяемых параметров.

Столбец «Целевой коэффициент» содержит коэффициент чувствительности функции цели к изменяемому параметру, то есть на сколько изменится значение целевой функции, если параметр увеличится-уменьшится на единицу). Другими словами – это значения частных производных целевой функции по параметру.

Таблица «Ограничения» содержит результирующие значения оптимального решения и исходные ограничивающие величины.

Столбец «Теневая цена» содержит коэффициент чувствительности функции цели к изменяемому параметру, то есть на сколько изменится значение целевой функции, если параметр увеличится-уменьшится на единицу). Другими словами – это значения частных производных целевой функции по параметру.

Как видно из таблицы, увеличение объема пахоты на единицу приведет к росту функции цели на 474,68 грн. Увеличение объема, например, сева не приведет к росту функции цели, так как располагаемый парк техники позволяет выполнять вдвое больший объем таких работ. Как только потребный объем по севу превысит 6079,24, потребуется увеличивать число тракторов и тем самым увеличивать значение целевой функции.

Отчет по пределам

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

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

   

Целевое

             
 

Ячейка

Имя

Значение

           
 

$E$56

Функция цели – миним. Суммарные годовые затраты

975696,2

           
   

Изменяемое

   

Нижний

Целевое

 

Верхний

Целевое

 

Ячейка

Имя

Значение

 

предел

результат

 

предел

результат

 

$B$50

К-701 Количество

20

 

20

975696

 

#Н/Д

#Н/Д

 

$B$51

Т-4А Количество

30

 

30

975696

 

#Н/Д

#Н/Д

 

$B$52

ДТ-75 Количество

40

 

40

975696

 

#Н/Д

#Н/Д

 

$B$53

МТЗ-50 Количество

40

 

40

975696

 

#Н/Д

#Н/Д

  1. .6После выхода из окна «Результаты поиска решения» на Листе в ячейках В50-В53 поместятся величины количества тракторов каждого типа, обеспечивающие минимальные затраты. В ячейке Е56 – величина затрат, а в ячейках В60-В65 – объемы работ по видам, которые сможет выполнить расчетное количество тракторов (см. таблицы 2.9 и 2.10).

Просмотр сценариев

Надстройка «Поиск решения…» дает возможность пошагово проследить за процессом поиска оптимального решения, для чего в окне диалога «Параметры поиска решения» устанавливается маркер на фразе «Показывать результаты итераций».

       
   
 


Теперь после нажатия кнопки «Выполнить» меню «Поиск решения» Excel выполняет итерацию расчета, выводя данные расчета в соответствующие ячейки рабочего Листа, и на экран выводится окно «Текущее состояние поиска решения», позволяющее управлять процессом решения задачи и сохранить данную итерацию как сценарий. При сохранении сценария следует в окне «Сохранение сценария» указать имя, под которым сценарий будет сохранен (см. рис.2.9).

Рис.2.9.

Анализ сценариев позволяет анализировать промежуточные решения. Для просмотра сценариев необходимо воспользоваться командой «Сценарии…» меню «Сервис».

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

Задания.

С помощью надстройки «Поиск решения…» решить приведенную выше задачу с учетом:

а) ограничений на сроки;

б) ограничений на сроки и суточные объемы;

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

Обновление 2018 Примеры решения ЗЛП

Пример 1 . Пусть задана некоторая задача линейного программирования, система ограничений которой имеет следующий вид:

x1 +2x2 ≤12

x1 + x2≤8

Решить данную задачу с помощью симплекс-метода, если целевая функция задана следующим уравнением:

2x1 + 3x2 = F{max}

Используя алгоритм решения ЗЛП, можно заметить,

что требования А. В,С, D выполнены, поэтому переходим к оператору L.

Построим таблицу, в строке которой, помеченной слева нулем, запишем коэффициенты целевой функции, а на ниже расположенных строках – коэффициенты уравнений системы линейных ограничений:

                           е

1ит

1

2

0

g

0

2

3

0

 

3

1

2

12

6

4

1

1

8

8


При решении задачи будем производить преобразования именно с этой таблицей. Решим задачу в соответствии с алгоритмом симплекс-метода:

1 итерация (k=1):\

Bычислим текущее допустимое решение:

x1=x2=0 x3=12 x4=8 F=0

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

В соответствии с алгоритмом найдем е-строку и

s-столбец:

e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:

е max(a01=2, a02=3)=2

Для определения s-строки необходимо, прежде всего, рассчитать столбец g.

g3=12/2=6, g4=8/1=8

Тогда, очевидно, что на данной итерации индекс

s =min (g3=6g4=8)=3

Далее произведем замену e-столбца и s-строки .L,2

L.2.1 a23=1/2

L.2.2 a21=1/2 a20=12/2=6

L.2.3 a03=-3/2 a43=-1/2

L.2.4 a01=2-1/2*3=1/2 a00=0-6*3= -18

a41=1- 1/2 = 1/2 a40=8-6=2

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

   

e

     
 

2ит

1

3

0

g

 

0

1/2

-3/2

-18

 
 

2

1/2

1/2

6

12

s

4

1/2

-1/2

2

4

Вычислим текущее допустимое решение:

x1=x3=0, x2= 6, x4 = 2, F =18

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

для чего найдем е-строку и s-столбец:

е = 1

Для определения s-строки необходимо, прежде всего, рассчитать столбец g

= 4

Результаты расчетов представлены в таблице 2 ит

Произведем замену e-столбца и s-строки. L.2

L,2.1 a14= 2

L.2.2 a13= -1 a10= 4

L,2.3 a24= -1 a04= -1

L.2.4 a03= -3/2-(-1)*1/2=-1 a00=-18 -4=-20

a23=1/2 -(-1)*1/2 = 1 a20=6-4*1/2=4

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

3ит

4

3

0

g

0

-1

-1

-20

 

2

-1

1

4

 

1

2

-1

4

 

В соответствии с выражением вычислим текущее допустимое решение:

x3=x4=0 x1=x2=4 F=20

Улучшить найденное решение невозможно.

Пример 2Найти решение ЗЛП

y1 + y2 ≥ 2

2y1 + y2 ≥ 3

12y1 + 8y2 = Ф[min]

Для решения ЗЛП выполним операторы M и N.

В результате получим симплекс-таблицу:

     

е

   
 

1ит

1

2

0

g

 

0

-12

-8

0

 

S

3

-1

-1

-2

2

 

4

-2

-1

-3

3

Используя K оператор найдем е-строку и s-столбец:

e =2, s = 3, a32 = -1.

L.3.1. a23=1/(-1)=-1

L.3.2. a21=(-1)/(-1)=1 a20=(-2/(-1)=2

L.3.3. a01=(-12)-1*(-8)=-4

a00=(0)-2*(-8)=16

a41=(-2)-1*(-1)= -1

a40=(-3)-2*(-1)= -1

Произведем замену e-столбца и s-строки. В результате получим таблицу 2ит:

   

e

     
 

2ит

1

3

0

g

 

0

-4

-8

16

 
 

2

1

-1

2

2

s

4

-1

-1

-1

1

В соответствии с формулами K алгоритма найдем е-строку и s-столбец:

e =1, s = 4, a41 = -1

Произведем замену e-столбца и s-строки.:

L.3.1 a14=1/(-1)= -1

L.3.2 a13=(-1)/(-1)=1 a10=(-1)/(-1)=1

L.3.3 a04=(-4)/(1) =-4 a24=(1)/(-1)=-1

L.3.4 a03=(-8) -1*(-4)=-4

a00=(16)-1*(-4)=20

a23= (-1)-1*(1)= -2

a20= (2) -1*(-1)= 1

 

3ит

4

3

0

 

0

-4

-4

20

 

2

-1

-2

1

 

1

-1

1

1

у3 = у4 = 0, у1 = у2 =1Ф = 20

Пример 3Найти решение ЗЛП

x1 + 2x2 ≤ 12

x1 + x2 ≥ 8

---------------------

2x1 + 3x2 = Ф[max]

Для решения ЗЛП выполним операторы M и N.

В результате получим симплекс-таблицу 1ит

Т. к. условие D не выполнено проводим оператор K

   

е

     
 

1ит

1

2

0

g

 

0

2

3

0

 
 

3

1

2

12

12

s

4

-1

-1

-8

8

Т. к. условие D выполнено проводим оператор L и получаем таблицу 3ит.

               e

2ит

4

2

0

g

0

2

1

-16

 

3

1

1

4

4

1

-1

1

8

-8

3ит

3

2

0

0

-2

-1

-24

4

1

1

4

1

1

0

12


Которая позволяет определить решение:

R: x3=x2=0, x4=4, x1=12, F=24

Пример 4. Решить ЗЛП, которая явяется двойственной к задаче примера 3.

Решение.

Построим необходимую задачу:

x1 + 2x2 ≤ 12                      у1 - у2 ≥ -2

x1 + x2 ≥ 8          →         2у1 - у2 ≥ 3

---------------------        ---------------------

2x1 + 3x2 = Ф[max]    12у1 - 8у2 = F{min}

Применим операторы M, N,K и получим таблицу 1ит:

1ит

1

2

0

g

0

-12

8

0

 

3

-1

1

-2

2

4

-2

1

-3

1.5

 

Используя K оператор найдем е-строку и s-столбец:

e =1, s = 4, a41 = -2

Произведем замену e-столбца и s-строки. В результате получим таблицу 2ит:

2ит

4

2

0

g

0

-6

2

18

 

3

-0,5

0,5

-0,5

1

1

-0,5

-0,5

1,5

-3


Используя K оператор найдем е-строку и s-столбец:

e =4, s = 3, a34 = -0,5

Произведем замену e-столбца и s-строки. В результате получим таблицу 3ит:

3ит

3

2

0

0

-12

-4

24

4

-2

-1

1

1

-1

-1

2

Задача по линейному программированию - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

Google