реферат
Главная

Рефераты по сексологии

Рефераты по информатике программированию

Рефераты по биологии

Рефераты по экономике

Рефераты по москвоведению

Рефераты по экологии

Краткое содержание произведений

Рефераты по физкультуре и спорту

Топики по английскому языку

Рефераты по математике

Рефераты по музыке

Остальные рефераты

Рефераты по авиации и космонавтике

Рефераты по административному праву

Рефераты по безопасности жизнедеятельности

Рефераты по арбитражному процессу

Рефераты по архитектуре

Рефераты по астрономии

Рефераты по банковскому делу

Рефераты по биржевому делу

Рефераты по ботанике и сельскому хозяйству

Рефераты по бухгалтерскому учету и аудиту

Рефераты по валютным отношениям

Рефераты по ветеринарии

Рефераты для военной кафедры

Рефераты по географии

Рефераты по геодезии

Рефераты по геологии

Рефераты по геополитике

Рефераты по государству и праву

Рефераты по гражданскому праву и процессу

Рефераты по делопроизводству

Рефераты по кредитованию

Рефераты по естествознанию

Рефераты по истории техники

Рефераты по журналистике

Рефераты по зоологии

Рефераты по инвестициям

Рефераты по информатике

Исторические личности

Рефераты по кибернетике

Рефераты по коммуникации и связи

Контрольная работа: Решение задач линейного программирования

Контрольная работа: Решение задач линейного программирования

Контрольная работа №2

Задание 1

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

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

Индивидуальное задание

Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).

Таблица 1

Номер варианта Целевая функция Ограничения задачи линейного программирования
6

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

Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:

x1+4x2=8, 2x1-x2=4, x1+x2­=1,x1=0,x2=0.

Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).



L

Рисунок 1. Графическое решение задачи ЛП

В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции Z=-2x1+4x2 , строим разрешающую прямую, приравнивая линейную форму нулю:Z=0. Строим  градиент целевой функции C(2;4).

Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.

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

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


Задание 2

Решение задач ЛП симплексным методом с использованием симплекс-таблиц

Цель задания: закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.

Индивидуальное задание

Найти максимум линейной формы

Z=c1x1+c2x2

при условиях:

Данные представлены в таблице 2.

Номер варианта

A11

A12

A21

A22

A31

A32

B1

B2

B3

C1

C2

6 4 1 3 6 8 7 43 74 76 7 4

Приведем  задачу ЛП к каноническому виду:

-Z’= -Z = -7x1 -4x2

при ограничениях

x3, x4, x5 — дополнительные переменные.

Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.

Постановка задачи в виде матрицы системы ограничений

Решение задачи ЛП с составленными симплекс-таблицами

Единичные векторы A3, A4, A5 образуют базис трехмерного пространства (m=3). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x3, x4, x5 входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x3, x4, x5 – базисные переменные, а остальные небазисные. Полагая небазисные переменные  в ограничениях равными нулю, получим исходное допустимое базисное решение:

X0=(0,0,43,-74,76).

Заполняем исходную симплекс-таблицу (таблица 2)

Таблица 2. Нулевая симплекс-таблица

i

Бx

Сб

A0

-7 -4 0 0 0 T

A1

A2

A3

A4

A5

1

A3

0 43

4

1 1 0 0

 2

A4

0 74 -3 -6 0 1 0
3

A5

0 76 -8 7 0 0 1
4 0 7 4 0 0 0

Так как среди разностей есть положительные, то X0 не является оптимальным решением. Строим новое базисное решение.

.

Выводим из базиса вектор A3,так как

.

Разрешающий элемент таблицы x12 выделим кругом, а разрешающий столбец и строку стрелками.

Таблица 3. Первая симплекс-таблица

i

Бx

A0

-7 -4 0 0 0 T

A1

A2

A3

A4

A5

1

A1

-7

1

0 0
2

A4

0

0

1 0
3

A5

0 162 0 9 2 0 1
4

0

0 0

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

.

Выводим из базиса вектор A4,так как

.

Таблица 4. Вторая симплекс-таблица

i

Бx

A0

-7 -4 0 0 0 T

A1

A2

A3

A4

A5

1

A2

-4 43 4 1 4 0 0
2

A4

0 736 21 0

1 0
3

A5

0 -225 -36 0 -34 0 1
4

-9 0

0 0

Так как все разности во второй таблице (таблица 4) неположительны: , т получено оптимальное решение:

    min(-Z)= -225.

Тогда max(Z)= -min(-Z)= 225

Анализ оптимального плана.

Использование переменной x1 нецелесообразно.


Задание 3

Моделирование и решение задач ЛП на ЭВМ

Цель задания:  приобрести практические навыки моделирования задач ЛП и их решения симплекс-методом с использованием прикладной программы SIMC.

Индивидуальное задание

Предприятие может работать по 5-ти технологическим процессам, причем кол-во единиц выпускаемой продукции по разным ТП за ед. времени соответственно равны 300, 260, 320, 400, 450 шт. затраты производственных факторов в гривнах при работе  по разным ТП в течение 1 ед. времени и располагаемые ресурсы этих факторов в табл.5.

Найти программу максимального выпуска продукции.

Таблица 5.

факторы Способ производства

Ресурсы,

грн

1 2 3 4 5
Сырье 12 15 10 12 11 1300
Эл.энергия 0,2 0,1 0,2 0,25 0,3 30
Зарплата 3 4 5 4 2 400
Накладные расходы 6 5 4 6 4 800

Математическая интерпретация задачи

Исходные массивы, записанные в виде, пригодном для решения задачи по программе SIMC

5

4

  12.000  15.000  10.000  12.000  11.000    <   1300.000

   0.200   0.100   0.200   0.250   0.300    <     30.000

   3.000   4.000   5.000   4.000   2.000    <    400.000

   6.000   5.000   4.000   6.000   4.000    <    800.000

  300.000 260.000 320.000 400.000 450.000

 1

Рисунок 2. Исходные массивы для решения задачи

Распечатка ЭВМ с результатом решения

ИТЕРАЦИЯ N=1                                                РЕШЕНИЕ НАЙДЕНО !!!

ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА          ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx    Cб       Po         1         2         3         4         5

 6    0.000 1300.000   12.000    15.000    10.000    12.000    11.000

 7    0.000   30.000    0.200     0.100     0.200     0.250     0.300

 8    0.000  400.000    3.000     4.000     5.000     4.000     2.000

 9    0.000  800.000    6.000     5.000     4.000     6.000     4.000

               0.000  300.000   260.000   320.000   400.000   450.000

КОД ОШИБКИ=0

ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ

ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ =  0.0000

ИТЕРАЦИЯ N=1                                                ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx    Cб       Po         1         2         3         4         5 

 6    0.000 1300.000   12.000    15.000    10.000    12.000    11.000 

 7    0.000   30.000    0.200     0.100     0.200     0.250     0.300 

 8    0.000  400.000    3.000     4.000     5.000     4.000     2.000 

 9    0.000  800.000    6.000     5.000     4.000     6.000     4.000 

               0.000 -300.000  -260.000  -320.000  -400.000  -450.000 

В БАЗИС ВВОДИТСЯ 5 СТОЛБЕЦ

ИЗ БАЗИСА ВЫВОДИТСЯ 7 СТОЛБЕЦ

ИТЕРАЦИЯ N=2                                                ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА

Бx    Cб       Po         1         2         3         4         7 

 6    0.000  200.000    4.667    11.333     2.667     2.833   -36.667 

 5  450.000  100.000    0.667     0.333     0.667     0.833     3.333 

 8    0.000  200.000    1.667     3.333     3.667     2.333    -6.667 

 9    0.000  400.000    3.333     3.667     1.333     2.667   -13.333 

            45000.000   -0.000  -110.000   -20.000   -25.000  1500.000 

В БАЗИС ВВОДИТСЯ 2 СТОЛБЕЦ

ИЗ БАЗИСА ВЫВОДИТСЯ 6 СТОЛБЕЦ

ИТЕРАЦИЯ N=3                                                ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА

Бx    Cб       Po         1         3         4         6         7 

 2  260.000   17.647    0.412     0.235     0.250     0.088    -3.235 

 5  450.000   94.118    0.529     0.588     0.750    -0.029     4.412 

 8    0.000  141.176    0.294     2.882     1.500    -0.294     4.118 

 9    0.000  335.294    1.824     0.471     1.750    -0.324    -1.471 

            46941.176   45.294     5.882     2.500     9.706  1144.118 

КОД ОШИБКИ=0

ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ

 X2=17.6471

 X5=94.1176

ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765

РЕШЕНИЕ НАЙДЕНО !!!


Оптимальный план. Экономическая интерпретация оптимального решения.

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

Задание 4

Моделирование транспортных задач и их решение методом потенциалов

Цель задания:  приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов.

Индивидуальное задание

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

Таблица 6. 06 вариант транспортной задачи

Вид механизма Себестоимость выполнения единицы работы механизма ,гр.

Количество единиц ai механизмов

B1

B2

B3

B4

A1

11 4 3 1 15

A2

6 8 9 7 10

A3

4 8 4 2 35

Потребности bj участков в механизмах

25 20 10 5

Математическая формулировка транспортной задачи

Пусть xij – количество единиц работы, выполненной механизмом вида ai, на участке работы bj.Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:

при ограничениях:

1) ; - все механизмы должны быть задействованы;

2); - все участки должны быть загружены;

3) ; - количество единиц работы не может быть отрицательным

Условие разрешимости задачи выполняется:

25+20+10+5=15+10+35; 60=60.

Исходный опорный план, составленный по методу северо-западного угла

Таблица 7

I

ai

B1

B2

B3

B4

A1

11

4

15

3 1 15

A2

6

5

8

5

9 7 10

A3

4

20

8

4

10

2

5

35

bj

25 20 10 5

Решение транспортной задачи методом потенциалов

Итак, видно что в число занятых клеток следует ввести клетку (2,1).

Получим новый улучшенный план таблица 8.

Таблица 8

 

I

ai

B1

B2

B3

B4

A1

11

4

15

3 1 15

A2

6

5

8

5

9 7 10

A3

4

20

8

4

10

5

5

35

bj

25 20 10 5

Введём в число занятых клетку (1,4) . Получим новый улучшенный план – Таблица 9.

Таблица 9

I

ai

B1

B2

B3

B4

A1

11

4

10

3

5

1 15

A2

6

8

10

9 7 10

A3

4

25

8

4

5

2

5

35

bj

25 20 10 5

Так как,  - то данный план является оптимальным и значение себестоимости по данному плану.

x12=15; x­21=5; x22=5; x­31=20;x33=10; x­34=5.

Z=15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ оптимального плана

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


Задание 5

Решение транспортной задачи на ЭВМ

Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2.

Индивидуальное задание:

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

Таблица 10. 06 вариант транспортной задачи

Вид механизма Себестоимость выполнения единицы работы механизма ,гр.

Количество единиц ai механизмов

B1

B2

B3

B4

A1

11 4 3 1 15

A2

6 8 9 7 10

A3

4 8 4 2 35

Потребности bj участков в механизмах

25 20 10 5

Исходные массивы для решения транспортной задачи по программе TRAN2

Распечатка с ЭВМ с результатом решения

Оптимальный план транспортной задачи

x12=15; x­21=5; x22=5; x31=20;x33=10; x­34=5.

Z=15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ результатов и выводы

Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.


Задание 6

Решение многоэтапных задач методом динамического программирования

Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования.

Индивидуальное задание.

В таблице 11 приведены значения gi(x) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x.

Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f4(100) выпуска продукции был максимальным. Для упрощения вычислений значения x  принимать кратными 20 тыс. гр.

Таблица 11

Предприятие Прирост выпуска продукции, тыс. гр. Средства c, тыс. гр. Номер варианта
20 40 60 80 100
1

G1(x)

11 21 40 54 62 6
2

G2(x)

13 20 42 45 61
3

G3(x)

12 22 34 55 60
4

G4(x)

10 27 33 57 69

Функциональное уравнение Беллмана для рассматриваемой задачи

f1(x)=max[g1(x)]=g1(x) – для первого предприятия;

 - для остальных предприятий.

Решение задачи оптимального распределения средств между предприятиями методом динамического программирования


Таблица 12

Средства с, тыс. гр. Предприятие
1 2 3 4

G1(x)

G2(x)

G3(x)

G4(x)

20 11 13 12 10
40 21 20 22 27
60 40 42 34 33
80 54 45 55 57
100 62 62 60 69

Таблица 13

X1*(c)

20 40 60 80 100

F1(c)

11 21 40 54 62

Таблица 14

x

С

0 20 40 60 80 100

F2(c)

X2*(c)

20 0+13 12+0 13 0
40 0+24 12+13 22+0 25 20
60 0+42 12+24 22+13 34+0 42 0
80 0+45 12+42 22+24 34+13 55+0 55 80
100 0+67 12+45 22+42 34+24 55+3 60+0 68 80

Таблица 15

x

С

0 20 40 60 80 100

F3(c)

X3*(c)

20 0+13 10+0 13 0
40 0+29 10+13 27+0 27 40
60 0+42 10+25 27+13 33+0 42 0
80 0+55 10+42 27+25 33+13 57+0 57 80
100 0+68 10+55 27+42 33+25 52+13 69+0 69 40

Таблица 16

С

X1*(c)

F1(c)

X2*(c)

F2(c)

X3*(c)

F3(c)

X4*(c)

F4(c)

0 0 0 0 0 0 0 0 0
20 20 11 20 13 0 13 0 13
40 40 21 20 24 20 25 40 27
60 60 40 60 42 0 42 0 42
80 80 54 80 45 80 55 80 57
100 100 62 20 67 80 68 40 69

Итак, из таблицы 16 видно, что наибольший прирост выпуска продукции, который могут дать четыре предприятия при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. При этом четвертому предприятию нужно выделить 40 тыс. грн., а остальным 60 тыс. грн.

Оптимальное распределение оставшихся 60 тыс. грн. между 3-мя предприятиями обеспечит прирост продукции на сумму 42 тыс. грн., при условии, что 3-му  предприятию не будут выделены средства. Остается 60 тыс. грн., которые надо распределить между 2-мя предприятиями. Выделив всю оставшуюся сумму (60 тыс. грн.) второму, прибыль составит 42 тыс. грн. первому предприятию средств не остается.  

Максимальный прирост выпуска продукции на четырех предприятиях при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. и будет получен, если первому  предприятию не выделять средств, второму — 60 тыс. грн., третьему не выделять, а четвертому — 40 тыс. грн.

Это решение можно записать в виде:

X*=(0,0,60,40); f*=f4(100)=69 тыс. гр.





© 2010 Интернет База Рефератов