Задача оптимального производства продукции

Автор работы: Пользователь скрыл имя, 14 Мая 2013 в 19:16, контрольная работа

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

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность aij на каждую единицу j-го вида продукции i-го вида сырья, запас bi соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей.

Файлы: 1 файл

Готовая работа.doc

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

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

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность aij на каждую единицу j-го вида продукции i-го вида сырья, запас bi соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей.

       

Виды

сырья

Виды продукции

Запасы

сырья

I

II

А

5

2

30

В

1

1

9

С

2

2

18

прибыль

3

6

 

план (ед.)

х1

х2

 
       

Для производства двух видов продукции I и II с планом х1 и х2 единиц составить целевую функцию прибыли Z и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n = 5 единиц обоих видов продукции.

В условиях задачи составить оптимальный план (х1; х2) производства продукции, обеспечивающий максимальную прибыль Zmax. Определить остатки каждого вида сырья. (Задачу решить симплекс-методом)

 

Решение.

Если производственный план –  ед. продукции I и ед. продукции II, то сырья будет израсходовано ед., сырья ед., сырья ед. Запасы сырья составляют 30, 9 и 18 ед. соответственно. Таким образом, получаем ограничения:

Требуется изготовить в сумме не менее 5 единиц обоих видов продукции:

.

Согласно смыслу задачи, и должны быть неотрицательными:

.

План  принесёт прибыль ден. ед. Поскольку надо найти такой план, при котором прибыль будет максимальна, то целевая функция будет иметь вид:

.

Запишем математическую модель задачи:

;

Решим задачу симплекс-методом.

Введём в систему ограничений дополнительные неотрицательные переменные так, чтобы получить систему уравнений:

.

Система уравнений имеет 4 независимых уравнения и 6 переменных, то есть, можно выразить 4 переменные (базисные) через 2 оставшиеся (свободные). В качестве базисных переменных выберем , , и . Тогда и − свободные.

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

.

Мы получили новую систему уравнений, эквивалентную исходной:

Выразим через свободные переменные и целевую функцию:

;

.

Запишем задачу в стандартной форме:

,

Теперь можно применять симплексный  метод.

Составим первую симплекс-таблицу.

 

Базис

Сбаз

Переменные 

1

0

0

-3

1

0

0

5

5

2

0

0

0

0

1

0

1

4

3

0

0

0

0

0

1

2

8

4

3

1

1

0

0

0

-1

5

5

0

-3

0

0

0

-3

15


Начальное базисное решение  − допустимое; .

В последней строке есть отрицательные оценки − решение неоптимальное.

Отрицательные оценки одинаковые, поэтому выбираем любую оценку, например, стоящую в шестом столбце. Шестой столбец – разрешающий.

Для положительных коэффициентов  разрешающего столбца составляем оценочные  отношения – отношения свободного члена к коэффициенту:

для первой строки:   ;

для второй строки:   ;

для третьей строки:   .

В качестве разрешающей  выбираем первую строку с наименьшим отношением.

Таким образом, разрешающий элемент:

.

Производим замену базиса – переводим  в базис  вместо .

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

Элементы первой строки делим на разрешающий элемент:

.

Из второй строки вычитаем новую первую строку:

 

Из третьей строки вычитаем новую первую строку, умноженную на 2:

К четвёртой строке прибавляем новую первую строку:

К последней строке прибавляем новую  первую строку, умноженную на 3:

 

Базис

Сбаз

Переменные 

1

0

0

-3/5

1/5

0

0

1

1

2

0

0

3/5

-1/5

1

0

0

3

3

0

0

6/5

-2/5

0

1

0

6

4

3

1

2/5

1/5

0

0

0

6

5

0

-24/5

3/5

0

0

0

18


Второе базисное решение − допустимое; .

В последней строке есть отрицательная  оценка − решение неоптимальное.

Второй столбец – разрешающий.

Оценочные отношения:

для второй строки:   ;

для третьей строки:   ;

для четвёртой строки:  .

Вторая строка – разрешающая.

Разрешающий элемент:

.

Производим замену базиса – переводим  в базис  вместо .

Заполняем третью симплекс-таблицу.

 

Базис

Сбаз

Переменные 

1

0

0

0

0

1

0

1

4

2

6

0

1

-1/3

5/3

0

0

5

3

0

0

0

0

-2

1

0

0

4

3

1

0

1/3

-2/3

0

0

4

5

0

0

-1

8

0

0

42


 

Третье базисное решение − допустимое; .

В последней строке есть отрицательная  оценка − решение неоптимальное.

Третий столбец – разрешающий.

Оценочные отношения:

для четвёртой строки:  .

Четвёртая строка – разрешающая.

Разрешающий элемент:

.

Производим замену базиса – переводим  в базис  вместо .

Заполняем четвёртую симплекс-таблицу.

 

Базис

Сбаз

Переменные 

1

0

0

0

0

1

0

1

4

2

6

1

1

0

1

0

0

9

3

0

0

0

0

-2

1

0

0

4

0

3

0

1

-2

0

0

12

5

3

0

0

6

0

0

54


Четвёртое базисное решение − допустимое; .

В последней строке нет отрицательных  оценок − решение оптимальное.

 

Выводы:

максимальная прибыль в размере  ден. ед. будет получена при производственном плане ед. продукции I и ед. продукции II;

Информация о работе Задача оптимального производства продукции