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

Автор работы: Пользователь скрыл имя, 23 Апреля 2013 в 15:35, контрольная работа

Описание работы

Задачи 1 – 15. Цех выпускает два вида продукции П1 и П2, используя два вида полуфабрикатов – Р1 и Р2. Продукция используется при комплектации изделий, при этом на каждую единицу продукции первого вида требуется не более k единиц продукции второго вида. Известны нормы расхода aij полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объемы bi полуфабрикатов и прибыль pj от продажи единицы продукции (i = 1,2; j = 1,2). По данным табл. 7.1 определите план производства продукции П1 и П2, доставляющий максимум прибыли.

Файлы: 1 файл

задание 1..docx

— 66.22 Кб (Скачать файл)

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

Вариант 13.

 

Наиболее простым  и  наглядным методом линейного  программирования (ЛП) является графический  метод. Он применяется для решения  задач ЛП с двумя переменными.

Задачи 1 – 15. Цех выпускает два вида продукции П1 и П2, используя два вида полуфабрикатов – Р1 и Р2. Продукция используется при комплектации изделий, при этом на каждую единицу продукции первого вида требуется не более k единиц продукции второго вида. Известны нормы расхода aij полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объемы bi полуфабрикатов и прибыль pj от продажи единицы продукции (i = 1,2; j = 1,2). По данным табл. 7.1 определите план производства продукции П1 и П2, доставляющий максимум прибыли.

Таблица 1

Пара-

метр

Числовые данные для номеров задач

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

a11

1

2

1

2

10

11

10

1

2

2

2

3

1

2

4

a12

2

5

3

3

3

6

3

3

3

5

7

7

7

13

11

a21

6

5

4

2

2

3

2

2

3

7

10

9

8

11

9

a22

2

1

1

1

7

13

7

1

1

3

3

3

1

3

5

b1

800

1385

900

300

132

120

352

420

451

510

516

477

266

1250

925

b2

2400

645

1180

350

138

160

370

390

400

464

532

459

313

529

630

p1

10

12

10

8

3

12

3

1

5

6

7

15

2

3

2

p2

35

30

20

24

15

15

10

4

4

18

18

6

8

18

10

k

2

3

1

2

3

5

2

1

2

3

2

2

2

4

3


 

Решение: Пусть x = ( ) – план задачи. Тогда модель задачи примет вид

 

max Z =2 +8

 

Ограничения на полуфабрикаты:

 

+8 ≤266,

7 + ≤313

 

Условие комплектности  и неотрицательности переменных:

 

2 ≥

≥0, ≥0.

 

 

 

 

 

Таблица 2

Полуфабрикаты

Нормы затрат на единицу продукции

Объём полуфабриката

PI

PII

1

7

8

1

266

313

Прибыль

2

8

 

 

В первую очередь найдем область  допустимых значений, то есть точки  x1 и x2, которые удовлетворяют системе ограничений. По условию задачи x1≥0  и  x2 ≥0. Мы рассматриваем только те точки, которые принадлежат первой четверти.

Шаг первый:

Рассмотрим неравенство  первой системы ограничений:

X1+8X2≤266

Построим прямую.

Заменим знак неравенства  на знак равенства.

X1+8X2=266

Преобразуем уравнение следующим  образом:

+=266

Каждый член уравнения разделим на 266

+=1

Данное представление прямой называется уравнением прямой в отрезках и позволяет очень легко нарисовать данную прямую. На оси X1 рисуем точку с координатой 266, на оси X2 рисуем точку с координатой 133/4. Соединяем эти точки и получаем необходимую прямую.

Какие точки нас интересуют?

X1+8X2≤266

8X2≤-X1+266

X2≤-1/8X1+133/4

Знак неравенства меньше или равно нуля, следовательно, нас  интересуют точки, лежащие ниже построенной  прямой.

 

Рис. 1

 

 

Область допустимых значений выделена штриховкой. Точки, принадлежащие  области допустимых значений: А(0;0), В(0;266), С(133/4;0)

Шаг 2:

Рассмотрим неравенство  второй системы ограничений:

7X1+X2≤313

Построим прямую.

Заменим знак неравенства  на знак равенства

7X1+X2=313

Преобразуем уравнение следующим  образом:

+=313

Каждый член уравнения  разделим на 313

+=1

Аналогичным образом рисуем на оси X1 точку с  координатой 313/7, а на оси X2 точкус координатой 313.

Соединяем точки и получаем необходимую прямую.

Какие точки нас интересуют?

7X1+X2≤313

X2≤ -7X1+313

Знак неравенства меньше или равно нуля, следовательно, нас  интересуют точки, расположенные ниже построенной прямой.

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

Рис 2.

Область допустимых значений выделена штриховкой.

Точки, принадлежащие области  допустимых значений: А(0;0), D(313/7;0), С(0;133/4), Е (2238/55;1549/55)

Шаг 3:

Рассмотрим неравенство  третьей системы ограничений:

2X1-X2≥0

Построим прямую.

Заменим знак неравенства  на знак равенства.

2X1-X2=0

-X2=-2X1

X2=2X1

Прямая проходит через начало координат

Какие точки нас интересуют?

 

 

2X1-X2≥0

-2X1+X2≤0

X2≤2X1

Знак неравенства меньше или равно нуля, следовательно, нас  интересуют точки, расположенные ниже построенной прямой.

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

 

Рис. 3

Область допустимых значений выделена штриховкой.

Точки, принадлежащие области  допустимых значений: А(0;0), D(313/7;0), Е(2238/55;1549/55), F(266/17;532/17)

Шаг 4:

Вернемся к нашей исходной функции Z=2x1+8x2. Допустим, значение функции Z=1, тогда 1=2x1+8x2. Данное уравнение является уравнением прямой на плоскости. Из курса геометрии известно, что данная прямая перпендикулярна вектору, координатами которого являются коэффициенты функции, а именно вектору =(2;8). Следовательно, с геометрической точки зрения, исходная функция Z изображается как множество прямых, перпендикулярных вектору =(2;8).

На рисунке вектор изображен  красным цветом.( Вектор нарисован для наглядности)

Будем перемещать прямую перпендикулярно  вектору до тех пор, пока она полностью не пройдет область допустимых значений. Касание прямой, перед выходом  из области допустимых значений произойдет в т. Е(2238/55;1549/55). В данной точке значение функции будет наибольшим.

Рис. 4

 

 

 

 

Ответ:

Наибольшее значение функция  достигает при

X1=2238/55

X2=1549/55

Значение функции Z= 16868/55

Таким образом необходимо выпустить 41 единицу первого продукта и 29 единиц второго продукта, чтобы получить max Z=41*2+29*8=307ден.ед.


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