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

Задача №11

G=5

N=25

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

Расход ресурса на одно изделие
Изделие 1Изделие 2Изделие 3
Ресурс АG=535
Ресурс В427

Трудоемкость изготовления изделия 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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A40400535100000
2A50600427010000
3A6015011/21/3001000
4A70-50– 100000100
5A80-500-10000010
6A90-3000-1000001
∆j=W(j)-cj0– 25-20-50000000

Находим пробное решение, для этого все свободные переменные приравниваем к 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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A40150035100500
2A50400027010400
3A6010001/21/3001100
4A12550100000-100
5A80-500-10000010
6A90-3000-1000001
∆j=W(j)-cj12500-20-50000-2500

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

Свободные переменныеБазисные переменные

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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A400005100530
2A50300007010420
3A6075001/300111/20
4A12550100000-100
5A220500100000-10
6A90-3000-1000001
∆j=W(j)-cj225000-50000-25-200

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

Свободные переменныеБазисные переменные

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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A40-150000100535
2A5090000010427
3A606500000111/21/3
4A12550100000-100
5A820500100000-10
6A903000100000-1
∆j=W(j)-cj2400000000-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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A40400535100000
2A50600427010000
3A6015011/21/3001000
4A7050100000100
5A8050010000010
6A9030001000001
∆j=W(j)-cj0-25-20-50000000

Находим пробное решение, для этого все свободные переменные приравниваем к 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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A4025053010000-5
2A5039042001000-7
3A6014011/2000100-1/3
4A7050100000100
5A8050010000010
6A35030001000001
∆j=W(j)-cj1500-25-2000000050

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

Свободные переменныеБазисные переменные

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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A1255010,600,20000-1
2A501900-0.40-0,81000-3
3A60900-0.10-0,201002/3
4A7000-0.60-0,200101
5A8050010000010
6A35030001000001
∆j=W(j)-cj27500-505000025

Находим пробное решение, для этого все свободные переменные приравниваем к 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=20C3=50C4=0C5=0C6=0C7=0C8=0C9=0
СбВiA1А2A3A4A5A6A7A8A9
1A125201000,2000-0,6-1
2A50210000-0,81000.4-3
3A6095000-0,20100,12/3
4A7030000-0,20010.61
5A22050010000010
6A35030001000001
∆j=W(j)-cj30000005000525

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

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

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

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

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

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

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

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

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

БПU7U8U9U1U2U3U4U5U6
ДвойствВiA1А2A3A4A5A6A7A8A9
1A1U7201000,2000-0,6-1
2A5U2210000-0,81000.4-3
3A6U395000-0,20100,12/3
4A7U430000-0,20010.61
5A2U850010000010
6A3U930001000001
∆j=W(j)-cj30000005000525

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

БПСбазВiC1=400С2=600C3=150C4=50C5=50C6=30C7=0C8=0C9=0
U1U2U3U4U5U6U7U8U9
1U1400510.80.20.200-0.200
2U55050-0.4-0.1-0.6100.6-10
3U6302503-2/3-10110-1
∆j=Z(j)-cj0-210-953000-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 $


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