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

Задача №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) Составить математическую модель задачи целочисленного программирования.

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

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

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

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

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 $


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