Математический расчет объема выпуска продукции

Методы определения объемов выпуска изделий каждой модели, при которых прибыль будет максимальна Составление математической модели задачи целочисленного программирования. Решение задачи симплекс-методом. Поиск целочисленного решения методом отсечения.

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 30.01.2011
Размер файла 156,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Задача №11

G=5

N=25

Завод выпускает изделия трех моделей (1, 2 и 3). Для изготовления используются 2 вида ресурсов А и В, запасы которых составляют 400 и 600 единиц. Расход ресурсов на одно изделие каждой модели приведен в таблице:

Расход ресурса на одно изделие

Изделие 1

Изделие 2

Изделие 3

Ресурс А

G=5

3

5

Ресурс В

4

2

7

Трудоемкость изготовления изделия 1 вдвое больше, чем изделия модели 2 и в трое больше, чем модели 3. Численность рабочих завода позволяет выпускать 150 изделий модели 1 (если не одновременно изделия моделей 2 и 3). Анализ условий сбыта показывает, что минимальный спрос на продукцию завода составляет 50, 50 и 30 изделий моделей 1, 2 и 3 соответственно. Удельные прибыли от реализации изделий 1, 2 и 3 составляют N=25, 20 и 50$ соответственно.

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

Необходимо:

Составить математическую модель задачи целочисленного программирования.

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

Произвести постоптимальный анализ.

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

Найти целочисленное решение методом отсечения (достаточно пяти итераций).

1) Составим математическую модель задачи целочисленного программирования

Пусть х1 -выпущенное количество изделий модели 1

х2- выпущенное количество изделий модели 2

х3- выпущенное количество изделий модели 3

Хотим найти такой ассортимент выпускаемых товаров, при котором прибыль будет максимальна Прибыль от продаж 1 единицы каждого изделия 25, 20 и 50$ Записываем функцию цели:

Сырье которое используем в ходе производства ограничено запасами, построим ограничения по сырью, используя данные приведенные в таблице:

Численность рабочих позволяет выпускать только 150 единиц товара №1 если не производить в это же время товары 2 и 3.

Трудоемкость товара 1 вдвое больше чем товара 2 и втрое больше чем товара 3

По условию задачи сказано, что минимальный спрос на продукцию завода составляет 50, 50 и 30 изделий моделей 1, 2 и 3 соответственно:

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

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

Перепишем условие мат. Модели таким образом, чтоб все ограничения задачи имели один знак. Для классической задачи МАКСИМУМ, знак ограничений должен быть типа «?»

Для того что б последние 3 неравенства были такие как нам надо, домножаем их на «-1»

Перейдем к каноническому виду, для этого необходимо от неравенств-ограничений перейти к ограничениям-равенствам. Вводим дополнительные переменные. Так как все неравенства типа «?», то дополнительные переменные вводим со знаком «+»

х1, х2, х3- свободные переменные

х4, х5, х6, х7, х8, х9- базисные переменные

Составим и заполним 1-ую симплексную таблицу

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A4

0

400

5

3

5

1

0

0

0

0

0

2

A5

0

600

4

2

7

0

1

0

0

0

0

3

A6

0

150

1

1/2

1/3

0

0

1

0

0

0

4

A7

0

-50

-1

0

0

0

0

0

1

0

0

5

A8

0

-50

0

-1

0

0

0

0

0

1

0

6

A9

0

-30

0

0

-1

0

0

0

0

0

1

?j=W(j)-cj

0

-25

-20

-50

0

0

0

0

0

0

Находим пробное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi

Свободные переменные

Базисные переменные

X1=0

X2=0

X3=0

X4=400

X5=600

X6=150

X7=-50

X8=-50

X9=-30

Решение пробное.

Но так как в столбце bi есть отрицательные коэффициенты, то решение не ОПОРНОЕ.

Для решение задачи двойственным симплекс методом для начала необходимо добиться, что б решение было ОПОРНЫМ.

Находим в столбце Bi минимальный отрицательный коэффициент.

Bi=min{bi<0}=min{-50;-50;-30}= -50

Соответствует сразу двум строкам А7 и А8. Одна из этих строк будет разрешающей.

Для того что б определиться какую из двух строк выбрать в качестве разрешающей, для каждой найдем разрешающий столбец, а затем проверим при замене какой пары (разрешающая строка + разрешающий столбец) изменение функции цели будет больше (ту пару и будем менять)

1) А7- разрешающая строка

Ищем разрешающий столбец по правилу:

(так как среди оценочной строки имеются отрицательные оценки плана (задача максимизации), то среди отрицательных коэффициентов аij разрешающей строки выбирается разрешающий элемент аrs для которого

соответствует столбцу А1

Если заменим А1--А7 то функция цели изменится на:

2) А8- разрешающая строка

соответствует столбцу А2

Если заменим А2--А8 то функция цели изменится на:

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

Переходим к новой симплекс таблице по следующему правилу:

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

2. заполняем базисные столбцы

3. все остальные элементы симплекс таблицы находим по формуле:

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A4

0

150

0

3

5

1

0

0

5

0

0

2

A5

0

400

0

2

7

0

1

0

4

0

0

3

A6

0

100

0

1/2

1/3

0

0

1

1

0

0

4

A1

25

50

1

0

0

0

0

0

-1

0

0

5

A8

0

-50

0

-1

0

0

0

0

0

1

0

6

A9

0

-30

0

0

-1

0

0

0

0

0

1

?j=W(j)-cj

1250

0

-20

-50

0

0

0

-25

0

0

Новое решение

Свободные переменные

Базисные переменные

X2=0

X3=0

X7=0

X1=50

X4=150

X5=400

X6=100

X8=-50

X9=-30

Решение все еще не опорное, так как все еще есть bi<0

Находим разрешающую строку:

Bi=min{bi<0}=min{-50;-30}= -50

Соответствует строке А8

Разрешающий столбец:

соответствует столбцу А2

Меняем А2--А8

Переходим к новой симплекс таблице:

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A4

0

0

0

0

5

1

0

0

5

3

0

2

A5

0

300

0

0

7

0

1

0

4

2

0

3

A6

0

75

0

0

1/3

0

0

1

1

1/2

0

4

A1

25

50

1

0

0

0

0

0

-1

0

0

5

A2

20

50

0

1

0

0

0

0

0

-1

0

6

A9

0

-30

0

0

-1

0

0

0

0

0

1

?j=W(j)-cj

2250

0

0

-50

0

0

0

-25

-20

0

Новое решение

Свободные переменные

Базисные переменные

X3=0

X7=0

X8=0

X1=50

X2=50

X4=0

X5=300

X6=75

X9=-30

Решение все еще не опорное, так как все еще есть bi<0

В качестве разрешающей строки берем А9

Разрешающий столбец А3

Меняем А3--А9

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A4

0

-150

0

0

0

1

0

0

5

3

5

2

A5

0

90

0

0

0

0

1

0

4

2

7

3

A6

0

65

0

0

0

0

0

1

1

1/2

1/3

4

A1

25

50

1

0

0

0

0

0

-1

0

0

5

A8

20

50

0

1

0

0

0

0

0

-1

0

6

A9

0

30

0

0

1

0

0

0

0

0

-1

?j=W(j)-cj

2400

0

0

0

0

0

0

-25

-20

-50

Новое решение

Свободные переменные

Базисные переменные

X9=0

X7=0

X8=0

X1=50

X2=50

X3=30

X4= -150

X5=90

X6=65

Решение все еще не опорное, так как все еще есть bi<0

В строке №1 появился отрицательный коэффициент -150. Берем в качестве разрешающей строки строку №1.

Так как в строке №1 нет ни одного отрицательного коэффициента то решения НЕТ!

Возможно в условии задачи вместо МИНИМАЛЬНОГО спроса имели ввиду МАКСИМАЛЬНЫЙ.

Решим задачу для условия, что максимальный спрос на изделия составляет 50, 50 и 30единиц.

Тогда математическая модель задачи:

Канонический вид задачи линейного программирования:

х1, х2, х3- свободные переменные

х4, х5, х6, х7, х8, х9- базисные переменные

Составим и заполним 1-ую симплексную таблицу для нового условия задачи:

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A4

0

400

5

3

5

1

0

0

0

0

0

2

A5

0

600

4

2

7

0

1

0

0

0

0

3

A6

0

150

1

1/2

1/3

0

0

1

0

0

0

4

A7

0

50

1

0

0

0

0

0

1

0

0

5

A8

0

50

0

1

0

0

0

0

0

1

0

6

A9

0

30

0

0

1

0

0

0

0

0

1

?j=W(j)-cj

0

-25

-20

-50

0

0

0

0

0

0

Находим пробное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi

Свободные переменные

Базисные переменные

X1=0

X2=0

X3=0

X4=400

X5=600

X6=150

X7=50

X8=50

X9=30

Решение ОПОРНОЕ, так как все коэффициенты в столбце bi>=0.

Для того что бы задача МАКСИМУМ имела оптимальное решение, необходимо, что б все коэффициенты в строке функции цели ?j=W(j)-cj были не отрицательные (?j?0). У нас в этой строке есть отрицательные коэффициенты, поэтому решение НЕ ОПТИМАЛЬНОЕ.

Всего у нас три столбца у которых оценка плана отрицательна А1, А2 и А3.

Рассмотрим каждый из них и выберем тот который более выгодно ввести в базис. (Другими слова, при вводе какого вектора функция цели будет иметь наибольшее изменение)

А1 столбец:

Функция цели меняется по формуле:

Для столбца А1:

Тогда Если будем вводить вектор А1, то функция цели увеличится на 1250 единиц

=0-(-1250)=1250

А2 стролбец:

Функция цели меняется по формуле:

Для столбца А2: =-20

Тогда

Если будем вводить вектор А2, то функция цели увеличится на 1000 единиц

=0-(-1000)=1000

А3 столбец:

Функция цели меняется по формуле:

Для столбца А3: =-50

Тогда Если будем вводить вектор А3, то функция цели увеличится на 1500 единиц

=0-(-1500)=1500

Больше всего функция цели увеличится, если введем вектор А3.

Поэтому А3 - разрешающий столбец

Находим разрешающую строку по правилу:

соответствует строке 6 и вектору А9

Меняем А3--A9

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A4

0

250

5

3

0

1

0

0

0

0

-5

2

A5

0

390

4

2

0

0

1

0

0

0

-7

3

A6

0

140

1

1/2

0

0

0

1

0

0

-1/3

4

A7

0

50

1

0

0

0

0

0

1

0

0

5

A8

0

50

0

1

0

0

0

0

0

1

0

6

A3

50

30

0

0

1

0

0

0

0

0

1

?j=W(j)-cj

1500

-25

-20

0

0

0

0

0

0

50

Новое решение

Свободные переменные

Базисные переменные

X1=0

X2=0

X9=0

X3=30

X4=250

X5=390

X6=140

X7=50

X8=50

Решение опорное, но пока еще не оптимальное, так как есть отрицательные коэффициенты в строке функции цели.

Так как в двух столбцах оценка плана отрицательна рассмотрим изменение функции цели при вводе этих столбцов в базис:

А1 столбец:

Функция цели меняется по формуле:

Для столбца А1:

Тогда Если будем вводить вектор А1, то функция цели увеличится на 1250 единиц

=1500-(-1250)=2750

А2 стролбец:

Функция цели меняется по формуле:

Для столбца А2: =-20

Тогда

Если будем вводить вектор А2, то функция цели увеличится на 1000 единиц

=1500-(-1000)=2500

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

Разрешающий столбец А1

Ищем разрешающую строку:

соответствует строке 1и 5 (векторам А4 и А8)

Возьмем в качестве разрешающей строки строку №1 и вектор А4

Меняем А4 и А8

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A1

25

50

1

0,6

0

0,2

0

0

0

0

-1

2

A5

0

190

0

-0.4

0

-0,8

1

0

0

0

-3

3

A6

0

90

0

-0.1

0

-0,2

0

1

0

0

2/3

4

A7

0

0

0

-0.6

0

-0,2

0

0

1

0

1

5

A8

0

50

0

1

0

0

0

0

0

1

0

6

A3

50

30

0

0

1

0

0

0

0

0

1

?j=W(j)-cj

2750

0

-5

0

5

0

0

0

0

25

Находим пробное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi

Свободные переменные

Базисные переменные

X2=0

X4=0

X9=0

X1=50

X3=30

X5=190

X6=90

X7=0

X8=50

Решение опорное, но не оптимальное.

Разрешающий столбец № 2 (вектор А2 так как только у него есть отрицательная оценка плана)

Найдем разрешающий столбец:

БП

C1=25

С2=20

C3=50

C4=0

C5=0

C6=0

C7=0

C8=0

C9=0

Сб

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A1

25

20

1

0

0

0,2

0

0

0

-0,6

-1

2

A5

0

210

0

0

0

-0,8

1

0

0

0.4

-3

3

A6

0

95

0

0

0

-0,2

0

1

0

0,1

2/3

4

A7

0

30

0

0

0

-0,2

0

0

1

0.6

1

5

A2

20

50

0

1

0

0

0

0

0

1

0

6

A3

50

30

0

0

1

0

0

0

0

0

1

?j=W(j)-cj

3000

0

0

0

5

0

0

0

5

25

соответствует строке №5 и вектору А8

Меняем А8--А5

Находим пробное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi

Свободные переменные

Базисные переменные

X4=0

X8=0

X9=0

X1=20

X2=50

X3=30

X5=210

X6=95

X7=30

Решение ОПОРНОЕ и ОПТИМАЛЬНОЕ! Все коэффициенты в строке ?j?0

Для получения максимальной прибыли необходимо выпускать товар в следующем ассортименте:

Изделия 1-го типа в размере х1=20 шт

Изделия 2-го типа в размере х2=50шт

Изделия 3-го типа в размере х3=30шт

При таком выпуске получим максимальную прибыль в размере W*=3000$

3. Изменение коэффициентов целевой функции

Базисная переменная

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

Если нет коэффициентов то

Если нет коэффициентов то

1) X1

c1=25

2) X2

C2=20

Нет коэффициентов то

3) X3

C3=50

Нет коэффициентов то

4) X5

C5=0

5) X6

C6=0

6) X7

C7=0

Небазисная переменная

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

где

-оценка плана переменной , отвечающее оптимальному решению.

1) x4 с4=0

=5

2) Х8 с8=0

=5

3) Х9 с9=0

=25

4. Изменение компонент вектора ограничений

базисная дополнительная переменная.

Если дополнительная переменная i-го ограничения базисная, то ее значение дает диапазон изменения, в котором соответствующая компонента bi может уменьшаться (увеличиваться, если ограничение ?)

Решение остается оптимальным в диапазоне:

где

для ограничения ?

для ограничения ?

где -значение соответствующее дополнительной пересенной

1) Х5 в2=600

ограничение ?

2) Х6 в3=150

3) Х7 в4=50

Небазисная дополнительная переменная:

1) x4

b1=400

2) x8

b5=50

3) x9

b6=30

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

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

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

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

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

- Ограничения двойственной задачи будут иметь знак ?

Прямая задача

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

Для удобства перехода между прямой и двойственной задачами подпишем внутри последней симплекс-таблицы соответствующие переменные двойственной задачи

БП

U7

U8

U9

U1

U2

U3

U4

U5

U6

Двойств

Вi

A1

А2

A3

A4

A5

A6

A7

A8

A9

1

A1

U7

20

1

0

0

0,2

0

0

0

-0,6

-1

2

A5

U2

210

0

0

0

-0,8

1

0

0

0.4

-3

3

A6

U3

95

0

0

0

-0,2

0

1

0

0,1

2/3

4

A7

U4

30

0

0

0

-0,2

0

0

1

0.6

1

5

A2

U8

50

0

1

0

0

0

0

0

1

0

6

A3

U9

30

0

0

1

0

0

0

0

0

1

?j=W(j)-cj

3000

0

0

0

5

0

0

0

5

25

Итоговая симплекс-таблица двойственной задачи:

БП

Сбаз

Вi

C1=400

С2=600

C3=150

C4=50

C5=50

C6=30

C7=0

C8=0

C9=0

U1

U2

U3

U4

U5

U6

U7

U8

U9

1

U1

400

5

1

0.8

0.2

0.2

0

0

-0.2

0

0

2

U5

50

5

0

-0.4

-0.1

-0.6

1

0

0.6

-1

0

3

U6

30

25

0

3

-2/3

-1

0

1

1

0

-1

?j=Z(j)-cj

0

-210

-95

30

0

0

-20

-50

-30

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

Свободные переменные

Базисные переменные

U2=0

U3=0

U4=0

U7=0

U8=0

U9=0

U1=5

U5=5

U6=25

5) Целочисленное решение методом отсечения.

Так как в ходе решения нами было найдено целочисленное решение задачи максимум, то поставленная перед нами задача полностью решена!

Для получения максимальной прибыли рекомендуется выпускать изделия в следующем ассортименте:

Изделия Типа 1 в размере х1=20 шт

Изделия Типа 2 в размере х2=50 шт

Изделия Типа 3 в размере х3=30 шт

При таком выпуске прибыль будет максимальна и составит W*=3000 $


Подобные документы

  • Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.

    задача [26,1 K], добавлен 27.11.2015

  • Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.

    задача [58,6 K], добавлен 16.02.2016

  • Вычисление определителя, алгебраических дополнений. Выполнение действий над матрицами. Решение систем линейных уравнений по формулам Крамера, методом Гауса. Определение плана выпуска химикатов на заводе. Составление экономико-математической модели задачи.

    контрольная работа [184,8 K], добавлен 25.03.2014

  • Составление плана выпуска продукции с целью получения максимальной прибыли при ее реализации. Вид и запас сырья, прибыль от единицы продукции и общее количество. Приведение системы ограничений к каноническому виду. Составление симплексной таблицы.

    практическая работа [12,8 K], добавлен 24.05.2009

  • Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.

    курсовая работа [219,4 K], добавлен 17.04.2013

  • Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.

    курсовая работа [65,3 K], добавлен 30.11.2010

  • Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.

    курсовая работа [197,1 K], добавлен 09.04.2013

  • Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.

    курсовая работа [67,5 K], добавлен 25.11.2011

  • Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.

    дипломная работа [351,2 K], добавлен 01.06.2015

  • Теоретические положения симплекс-метода и постоптимального анализа. Построение математической модели задачи. Нахождение ценностей ресурсов. Определение относительных и абсолютных диапазонов изменения уровней запасов дефицитных и недефицитных ресурсов.

    курсовая работа [86,7 K], добавлен 19.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.