Контрольная работа по "Математические методы и модели"

ЗАДАЧА №1

 

Предприятие выпускает два вида продукции A₁, A₂, для производства которых используют три вида сырья S₁, S₂, S₃. На производство единицы j-ого вида продукции требуется a_ij единиц i-ого вида сырья. Предприятие имеет запасы каждого вида сырья, соответственно, b₁,b₂,b₃ единиц. Прибыль предприятия от реализации единицы j-ого вида продукции составляет c денежных единиц. Требуется найти план производства x₁единиц первого вида продукции и  x₂единиц второго вида продукции, при котором суммарная выручка предприятия будет наибольшей. С этой целью:

 

1. Записать  задачу линейного программирования.

2. Решить  ее геометрическим способом.

3. Решить  задачу симплексным методом.

4. Сформулировать  двойственную задачу и решить  её.

 

Числовые  данные для каждого варианта приведены  в следующих таблицах:

 

Вид сырья	Число единиц сырья, затрачиваемых на изготовление единицы продукции		Запас сырья, bi
	А1	А2
S1	5	4	810
S2	4	2	630
S3	2	6	786
Прибыль от реализации единицы продукции	34 ден. ед.	36 ден. ед.

 

Решение

 

Обозначим через  х₁, х₂  число единиц продукции А₁ и А₂ соответственно, запланированных к производству. Связь между потреблением сырья и его запасами выразится системой неравенств:

 

5х₁ +4х₂  ≤ 810

4х₁ + 2х₂  ≤ 630

2х₁ + 6х₂  ≤ 786,  где х₁ ≥ 0, х₂  ≥ 0.

 

Прибыль предприятия от реализации готовой  продукции составит

 

f = 34х₁+ 36х₂ (ден.ед.)

 

1. Решение графическим способом

 

Найдём  множество решений каждого неравенства  системы ограничений

 

5х₁ +4х₂  ≤ 810

4х₁ + 2х₂  ≤ 630

2х₁ + 6х₂  ≤ 786,  где х₁ ≥ 0, х₂  ≥ 0.

 

Ограничения х₁ ≥ 0, х₂  ≥ 0 означают, что область решений системы будет лежать  в первой четверти декартовой системы координат х₁Ох₂

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

 

х1	0	280
x2	80	0

 

l₁:    5х₁ + 4х₂ = 810

 

 

х1	0	100
x2	100	0

l₂:    4х₁ + 2х₂ = 630

 

 

х1	0	67
x2	332	0

l₃:    2х₁ + 6х₂ = 786

 

 

Множество решений строгого неравенства –  одна из полуплоскостей, на которые  делит плоскость построенная  прямая. Какая из них является искомой, выясним при помощи контрольной  точки  (0; 0) и отметим их штриховкой (рис.1)

 

                 х₂

                         

                         

 

 

                 

                              

100

                          

D

                               

 0     c                                                             х₁

A

332

280

                                             

100

 

Рис.1

 

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

Построим  вектор N={34; 36} функции f = 34х₁+ 36х₂. Проведём прямую, перпендикулярную этому вектору (линию уровня функции f) через начало координат. Для определения максимума линию уровня перемещаем параллельно себе (вдоль области допустимых решений) в направлении вектора N до опорного положения.  В вершине С линия уровня опорная, тогда функция f принимает максимальное значение в этой угловой точке.

Найдём  координаты точки С, решив систему уравнений:

 

2х₁ + 6х₂  = 786

х₁ + х₂  = 100

 

х₁ = 100 - х₂

2(100 - 6х₂ ) + 6х₂  = 786

 

х₁ = 100 - х₂

500 - 5х₂  + х₂  = 332

 

х₁ = 100 - х₂

4х₂   = 168

 

х₁ = 58

х₂= 42

 

Итак, С(58; 42). Значит х₁ = 58; х₂ = 42 - план производства изделий А₁ и А₂, обеспечивающий максимальную прибыль от реализации готовой продукции:

 

f_max = 34∙58 + 36∙42 = 3484 (ден.ед.)

 

2. Решение симплекс-методом

 

Приведём  задачу к каноническому виду, введя  дополнительные переменные. Расширенная  система задачи имеет вид:

 

5x₁ + 4х₂ + х₃ = 810

4х₁ + 2х₂  + х₄ =  630

2х₁ + 6х₂  + х₅ = 786,  где х_i ≥ 0,  i =1,2,3,4,5.

 

Линейную  функцию представим в виде f =34х₁+ 36х₂ + 0∙х₃ + 0∙х₄ + 0∙х₅ или f - 34х₁ -36х₂ - 0∙х₃ - 0∙х₄ - 0∙х₅ = 0

 

Заполним  первую симплекс-таблицу:

Таблица 1

Базис	Свободный член	Переменные					Оценочное отношение
		х1	х2	х3	х4	х5
х3	810	2	7	1	0	0	810/2=405
х4	630	3	3	0	1	0	630/3=210
х5	786	5	1	0	0	1	786/157
f	0	-34	-36	0	0	0

 

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

- Наибольший  по модулю отрицательный коэффициент  последней строки (-55) определяет  разрешающий столбец 1.

- Находим  оценочные отношения и min{280; 100; 66,4}= 66,4, третья строка является разрешающей. На пересечении разрешающей строки и столбца стоит разрешающий элемент а₃₂ = 5.

-  Новый  базис  - переменные х₃, х₄, х₁

- В первой  строке все элементы получаются  делением на разрешающий элемент  а₃₂ = 5. Остальные клетки заполняем по правилу прямоугольника. Например, а₁₂ = 7 – (1∙2)/5 = 11/3.

 

 

Получим вторую симплекс-таблицу:

Таблица 2

Базис	Свободный член	Переменные					Оценочное отношение
		х1	х2	х3	х4	х5
х3	2136/5	0	33/5	1	0	-2/5	712/11
х4	504/5	0	12/5	0	1	-3/5	42
x1	332/5	1	1/5	0	0	1/5	332
f	3652	0	-24	0	0	11

 

Критерий  оптимальности снова не выполняется. Теперь первый столбец разрешающий; х₂ переходит в базисные, вторая строка разрешающая, а₁₂ = 12/5 разрешающий элемент. Третья симплекс-таблица имеет вид:

Таблица 3

Базис	Свободный член	Переменные
		х1	х2	х3	х4	х5
x3	150	0	0	1	-11/4	5/4
x2	42	0	1	0	5/12	-1/4
x1	58	1	0	0	-1/12	1/4
f	4660	0	0	0	10	5

 

Критерий  оптимальности для максимума  выполнен (все коэффициенты последней  строки неотрицательны), значит оптимальное базисное решение Х=(58; 42; 150; 0; 0), то есть х₁ = 58; х₂ = 42 - план производства изделий А₁ и А₂, обеспечивающий максимальную прибыль предприятия от реализации готовой продукции:

f_max = 55∙28 + 35∙72 = 4660 (ден.ед.)

 

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

 

Исходная  задача на максимизацию, и все неравенства  системы ограничений имеют вид  ≤ :

 

2х₁ +7х₂ ≤ 560

3х₁ + 3х₂ ≤ 300

5х₁ + х₂ ≤ 332,  где х₁ ≥ 0, х₂ ≥ 0

 

Составим  расширенную матрицу системы:

 

 

2	7	560
3	3	300
5	1	332
55	35	fmax

 

А= 

Найдём  матрицу Ат, транспонированную к матрице А:

 

 

 

2	3	5	55
7	3	1	35
560	300	332	zmin

 

А^т=

 

 

 

 

Сформулируем  двойственную задачу:

Найти минимум  функции z = 560y₁ +300y₂ + 332y₃ при ограничениях:

2y₁ + 3y₂ + 5y₃ ≥ 55

7y₁ + 3y₂ + y₃ ≥ 35, где y₁, y₂, y₃ ≥0

 

Канонический  вид задачи: найти минимум функции z = 560y₁ +300y₂ + 332y₃ + 0∙y₄ + 0∙y₅ при ограничениях

 

2y₁ + 3y₂ + 5y₃ - y₄ = 55

7у₁ + 3у₂ + у₃ - у₅ = 35, где у₁, у₂, у₃, у₄, у₅≥0

 

На основании  теоремы двойственности установим  соответствие между переменными: