X4≤20 – количество шкафов книжных.
Критерий эффективности
Цель задачи:Определить, какое количество изделий, выпускаемых фабрикой, удовлетворяющих последней системе, будет максимизировать прибыль.
Т.к. Прибыль от реализации единицы изделия – 60, 25, 140 и 160 р. соответственно организации операции и параметров, заданных выше, то целевая функция имеет вид: L(x) = 60x1+25x2 +140x3+160x4 (→max)
Стратегии ОС
Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся активных средств. В виду поставленной цели и имеющихся у меня в настоящий момент знаний, лучшая и выполнимая стратегия – рассчет оптимального количества изделий. ЛПР может перейти к другим стратегиям, путем введения новых ограничений, и активных средств. Так же можно предположить существование субъективных желаний исполнителя и заказчика, определяющее выбор стратегии ОС. Количество этих стратегий определяется многоугольником решений задачи. ЛПР может принять и выбрать любую из них.
3. Методы решения
Данная задача относится к типу целочисленных.
Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.
Математическая модель целочисленной задачи:
При решении полностью целочисленных задач линейного программирования используются:
- методы отсечений
- методы разветвлений
- приближенные методы (даны допустимые решения, хотя и в общем случае неоптимальные)
Небольшая размерность задачи позволяет применить метод динамического программирования и метод сечения Гомори. Т.к. в основе последнего лежит двойственный симплекс метод линейного программирования, позволяющий наряду с нахождением решения, выявить и чувствительность модели к изменению параметров, то решим задачу этим методом.
4. Решение задачи
Прежде чем приступить к решению задачи запишем ее в общем виде:
|
Максимизировать
при условиях
при 
.
Цель задачи – получение максимальной прибыли – может быть достигнута несколькими способами. Математическим выражением цели является критериальная функции L, структура которой отражает вклад каждого из способов достижения цели. В сформулированной задаче представлено n таких способов. Под способом достижения цели понимается получение информации о распределении ресурсов для максимизации прибыли. Коэффициент Cj представляет собой удельную прибыль применения j-того способа достижения цели (прибыль от продажи одного изделия j-того типа). Переменные Хj – искомые величины, представляющие собой интенсивность использования j-того способа достижения цели ( количество изделий j-того типа).
Для достижения цели имеем: m- виды ресурсов, bi – возможный объем потребления i-того ресурса (максимальное количество древесного ресурса и трудового фактора). Коэффициент aij – расход
i-того ресурса для производства одного изделия j-того типа.
Метод Гомори
Решим задачу с нецелочисленными переменными:
Максимизировать
L(x) = 60x1+25x2 +140x3+160x4
при ограничениях
5x1 + x2 + 12x3 + 15x4≤1500
3x1 + 2x2 + 6x3 + 5x4≤1000
7x1 + 5x2 + 10x3 + 12x4≤3200
x1≥40
x2≥120
x3≥20
x4≤20
хi≥0
Этап 1
Приведем модель к стандартному виду: введем балансовые переменные x5, x6, x7, x8, x9, x10, x11, не имеющие физического смысла для приведения неравенств к равенствам.
Максимизировать
L(x) = 60x1+25x2 +140x3+160x4
при ограничениях
5x1 + x2 + 12x3 + 15x4 + x5 = 1500
3x1 + 2x2 + 6x3 + 5x4 + x6 = 1000
7x1 + 5x2 + 10x3 + 12x4+x7 = 3200
x1 -x8 = 40
x2 -x9 = 120
x3-x10 = 20
x4 +x11 = 20
X1… x11≥0
Решение системы производится путём ввода искусственных переменных Хi. Для исключения из базиса этих переменных, их вводят в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных. Таким образом, из исходной получается новая M-задача.
Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей L(x), а другая – для составляющей M. При составлении симплекс таблицы полагают, что исходные переменные являются небазисными, а дополнительные (xn+m) и искусственные(Xi)- базисными.
Этап 2
Введем искусственные переменные x12, x13, x14
5x1 + x2 + 12x3 + 15x4 + x5 = 1500
3x1 + 2x2 + 6x3 + 5x4+x6 = 1000
7x1 + 5x2 + 10x3 + 12x4 +x7 = 3200
x1 -x8 +x12 = 40
x2 -x9 + x13 = 120
x3 -x10 + x14 = 20
x4 +x11 = 20
Целевая функция:
L(X) = 60x1+25x2+140x3+160x4 - Mx12 - Mx13 - Mx14 → max
Из уравнений выражаем искусственные переменные:
x12 = 40-x1+x8
x13 = 120-x2+x9
x14 = 20-x3+x10
подставим в целевую функцию:
L(X) = (60+M)x1+(25+M)x2+(140+M)x3+(160)x4+(-M)x8+(-M)x9+(-M)x10+
+(-180M) x11
Этап 3
Прежде чем приступить к симплекс-преобразованиям, запишем исходные данные:
1.Размерность матрицы А – m x n, m=7, n=14.
2.Матрица А:
| -1 | |||||||||||||
| -1 | |||||||||||||
| -1 | |||||||||||||
3.Вектор свободных членов в уравнениях ограничений bi, i=1…m:
b=(1500,1000,3200,40,120,20,20)
4.Коэффициенты при переменных в критериальной функции Cj:
C=(60+M, 25+M, 140+M,160,0,0,0,-M,-M,-M, -180M,0,0,0)
Этап 4
Симплекс преобразования.
Решим систему уравнений относительно базисных переменных:
x5, x6, x7, x12, x13, x14, x11,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,1500,1000,3200,0,0,0,20,40,120,20)
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x5 | |||||||||||||||
| x6 | |||||||||||||||
| x7 | |||||||||||||||
| x12 | -1 | ||||||||||||||
| x13 | -1 | ||||||||||||||
| x14 | -1 | ||||||||||||||
| x11 | |||||||||||||||
| L(X0) | -180M | -60-M | -25-M | -140-M | -160 | M | М | M |
Итерация №0.
Первый опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x3, так как это наибольший коэффициент по модулю. Вычислим значения Ѳ по строкам как частное от деления:
bi / ai3 и из них выберем наименьшее: x14 - разрешающая строка
Разрешающий элемент = 1.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x5 | ||||||||||||||||
| x6 | 1662/3 | |||||||||||||||
| x7 | ||||||||||||||||
| x12 | -1 | - | ||||||||||||||
| x13 | -1 | - | ||||||||||||||
| x14 | -1 | |||||||||||||||
| x11 | - | |||||||||||||||
| L(X1) | -180M | -60-M | -25-M | -140-M | -160 | M | M | M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x5 | -12 | ||||||||||||||
| x6 | -6 | ||||||||||||||
| x7 | -10 | ||||||||||||||
| x12 | -1 | ||||||||||||||
| x13 | -1 | ||||||||||||||
| x3 | -1 | ||||||||||||||
| x11 | |||||||||||||||
| L(X1) | 2800-160M | -60-M | -25-M | -160 | M | M | -140 | 140+M |
Итерация №1.
Данный опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x1, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai1
и из них выберем наименьшее: строка x12
Разрешающий элемент = 1
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x5 | -12 | |||||||||||||||
| x6 | -6 | 2931/3 | ||||||||||||||
| x7 | -10 | 4284/7 | ||||||||||||||
| x12 | -1 | |||||||||||||||
| x13 | -1 | - | ||||||||||||||
| x3 | -1 | - | ||||||||||||||
| x11 | - | |||||||||||||||
| L(X2) | 2800-160M | -60-M | -25-M | -160 | M | M | -140 | 140+M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x5 | -5 | -12 | |||||||||||||
| x6 | -3 | -6 | |||||||||||||
| x7 | -7 | -10 | |||||||||||||
| x1 | -1 | ||||||||||||||
| x13 | -1 | ||||||||||||||
| x3 | -1 | ||||||||||||||
| x11 | |||||||||||||||
| L(X2) | 5200-120M | -25-M | -160 | -60 | M | -140 | 60+M | 140+M |
Итерация №2.
Текущий план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai2
и из них выберем наименьшее: x13 строка является разрешающей.
Разрешающий элемент =1
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x5 | -5 | -12 | ||||||||||||||
| x6 | -3 | -6 | ||||||||||||||
| x7 | -7 | -10 | ||||||||||||||
| x1 | -1 | - | ||||||||||||||
| x13 | -1 | |||||||||||||||
| x3 | -1 | - | ||||||||||||||
| x11 | - | |||||||||||||||
| L(X3) | 5200-120M | -25-M | -160 | -60 | M | -140 | 60+M | 140+M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x5 | -5 | -1 | -12 | ||||||||||||
| x6 | -3 | -2 | -6 | ||||||||||||
| x7 | -7 | -5 | -10 | ||||||||||||
| x1 | -1 | ||||||||||||||
| x2 | -1 | ||||||||||||||
| x3 | -1 | ||||||||||||||
| x11 | |||||||||||||||
| L(X3) | -160 | -60 | -25 | -140 | 60+M | 25+M | 140+M |
Итерация №3.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x4, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai4
и из них выберем наименьшее: строка x11
Разрешающий элемент =1.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x5 | -5 | -1 | -12 | 622/3 | ||||||||||||
| x6 | -3 | -2 | -6 | |||||||||||||
| x7 | -7 | -5 | -10 | 1762/3 | ||||||||||||
| x1 | -1 | - | ||||||||||||||
| x2 | -1 | - | ||||||||||||||
| x3 | -1 | - | ||||||||||||||
| x11 | ||||||||||||||||
| L(X4) | -160 | -60 | -25 | -140 | 60+M | 25+M | 140+M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x5 | -15 | -5 | -1 | -12 | |||||||||||
| x6 | -5 | -3 | -2 | -6 | |||||||||||
| x7 | -12 | -7 | -5 | -10 | |||||||||||
| x1 | -1 | ||||||||||||||
| x2 | -1 | ||||||||||||||
| x3 | -1 | ||||||||||||||
| x4 | |||||||||||||||
| L(X4) | -60 | -25 | -140 | 60+M | 25+M | 140+M |
Итерация №4.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x10, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai10
и из них выберем наименьшее: строка x5 разрешающая.
Разрешающий элемент =12.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x5 | -15 | -5 | -1 | -12 | 531/3 | |||||||||||
| x6 | -5 | -3 | -2 | -6 | ||||||||||||
| x7 | -12 | -7 | -5 | -10 | ||||||||||||
| x1 | -1 | - | ||||||||||||||
| x2 | -1 | - | ||||||||||||||
| x3 | -1 | - | ||||||||||||||
| x4 | - | |||||||||||||||
| L(X5) | -60 | -25 | -140 | 60+M | 25+M | 140+M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x10 | 531/3 | 1/12 | 5/12 | 1/12 | -11/4 | -5/12 | -1/12 | -1 | |||||||
| x6 | -1/2 | 1/2 | 11/2 | 21/2 | -1/2 | -11/2 | |||||||||
| x7 | 13462/3 | -5/6 | 25/6 | 41/6 | 1/2 | -25/6 | -41/6 | ||||||||
| x1 | -1 | ||||||||||||||
| x2 | -1 | ||||||||||||||
| x3 | 731/3 | 1/12 | 5/12 | 1/12 | -11/4 | -5/12 | -1/12 | ||||||||
| x4 | |||||||||||||||
| L(X5) | 188662/3 | 112/3 | -12/3 | -131/3 | -15 | 12/3+M | 131/3+M | M |
Итерация №5.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец переменной x11, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai11
и из них выберем наименьшее: x4 разрешающая строка.
Разрешающий элемент = 1.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x10 | 531/3 | 1/12 | 5/12 | 1/12 | -11/4 | -5/12 | -1/12 | -1 | - | |||||||
| x6 | -1/2 | 1/2 | 11/2 | 21/2 | -1/2 | -11/2 | ||||||||||
| x7 | 13462/3 | -5/6 | 25/6 | 41/6 | 1/2 | -25/6 | -41/6 | 26931/3 | ||||||||
| x1 | -1 | - | ||||||||||||||
| x2 | -1 | - | ||||||||||||||
| x3 | 731/3 | 1/12 | 5/12 | 1/12 | -11/4 | -5/12 | -1/12 | - | ||||||||
| x4 | ||||||||||||||||
| L(X6) | 188662/3 | 112/3 | -12/3 | -131/3 | -15 | 12/3+M | 131/3+M | M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x10 | 781/3 | 11/4 | 1/12 | 5/12 | 1/12 | -5/12 | -1/12 | -1 | |||||||
| x6 | -21/2 | -1/2 | 1/2 | 11/2 | -1/2 | -11/2 | |||||||||
| x7 | 13362/3 | -1/2 | -5/6 | 25/6 | 41/6 | -25/6 | -41/6 | ||||||||
| x1 | -1 | ||||||||||||||
| x2 | -1 | ||||||||||||||
| x3 | 981/3 | 11/4 | 1/12 | 5/12 | 1/12 | -5/12 | -1/12 | ||||||||
| x11 | |||||||||||||||
| L(X6) | 191662/3 | 112/3 | -12/3 | -131/3 | 12/3+M | 131/3+M | M |
Итерация №6.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x9, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai9
и из них выберем наименьшее: строка x6 разрешающая.
Разрешающий элемент равен =11/2
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x10 | 781/3 | 11/4 | 1/12 | 5/12 | 1/12 | -5/12 | -1/12 | -1 | ||||||||
| x6 | -21/2 | -1/2 | 1/2 | 11/2 | -1/2 | -11/2 | 331/3 | |||||||||
| x7 | 13362/3 | -1/2 | -5/6 | 25/6 | 41/6 | -25/6 | -41/6 | 3204/5 | ||||||||
| x1 | -1 | - | ||||||||||||||
| x2 | -1 | - | ||||||||||||||
| x3 | 981/3 | 11/4 | 1/12 | 5/12 | 1/12 | -5/12 | -1/12 | |||||||||
| x11 | - | |||||||||||||||
| L(X7) | 191662/3 | 112/3 | -12/3 | -131/3 | 12/3+M | 131/3+M | M |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 |
| x10 | 755/9 | 17/18 | 1/9 | -1/18 | 7/18 | -7/18 | -1 | ||||||||
| x9 | 331/3 | -12/3 | -1/3 | 2/3 | 1/3 | -1/3 | -1 | ||||||||
| x7 | 11977/9 | 64/9 | 5/9 | -27/9 | 14/9 | -14/9 | |||||||||
| x1 | -1 | ||||||||||||||
| x2 | 1531/3 | -12/3 | -1/3 | 2/3 | 1/3 | -1/3 | |||||||||
| x3 | 955/9 | 17/18 | 1/9 | -1/18 | 7/18 | -7/18 | |||||||||
| x11 | |||||||||||||||
| L(X7) | 196111/9 | -72/9 | 72/9 | 88/9 | 27/9 | -27/9+M | M | M |
Итерация №7.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты. В качестве разрешающего выберем столбец x4, так как это наибольший коэффициент по модулю.
Вычислим значения Ѳ по строкам как частное от деления: bi / ai4
и из них выберем наименьшее: строка x11 разрешающая.
Разрешающий элемент равен =1.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | Ѳ |
| x10 | 755/9 | 17/18 | 1/9 | -1/18 | 7/18 | -7/18 | -1 | 542/5 | ||||||||
| x9 | 331/3 | -12/3 | -1/3 | 2/3 | 1/3 | -1/3 | -1 | - | ||||||||
| x7 | 11977/9 | 64/9 | 5/9 | -27/9 | 14/9 | -14/9 | 18525/29 | |||||||||
| x1 | -1 | - | ||||||||||||||
| x2 | 1531/3 | -12/3 | -1/3 | 2/3 | 1/3 | -1/3 | - | |||||||||
| x3 | 955/9 | 17/18 | 1/9 | -1/18 | 7/18 | -7/18 | 684/5 | |||||||||
| x11 | ||||||||||||||||
| L(X8) | 196111/9 | -72/9 | 72/9 | 88/9 | 27/9 | -27/9+M | M | M |
Получаем новую симплекс-таблицу: