Построение математической модели для симплекс-задачи
Пример №1. Предприятие для производства двух изделий (А и В) использует сырье трех типов. Известно, что для производства одного изделия А требуется сырье 1- го типа в количестве a1 (ед.), 2 - го типа – a2 (ед.) и 3 – го типа – a3 (ед.), а для производства изделия В –b1, b2 и b3 соответственно. Запасы сырья на предприятии ограничены и составляют величины c1, c2 и c3 соответственно. Известно также, что прибыль от реализации одного изделия А составляет р (руб.), а одного изделия В – q (руб.). Требуется составить такой план производства изделий из имеющегося сырья, чтобы суммарная прибыль от реализации всех изделий была максимальной (для этого построить соответствующую математическую модель и решить полученную задачу линейного программирования графически и симплекс методом). Получить двойственные оценки ресурсов и дать их экономический анализ.Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим максимальное значение целевой функции F(X) = -x1-3x2-2x3-x4 при следующих условиях-ограничений.
x1-x2-x4≤1
-x1+x2+x3-x4≥3
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.
1x1-1x2 + 0x3-1x4 + 1x5 + 0x6 = 1
-1x1 + 1x2 + 1x3-1x4 + 0x5-1x6 = 3
Введем искусственные переменные x: в 2-м равенстве вводим переменную x7;
1x1-1x2 + 0x3-1x4 + 1x5 + 0x6 + 0x7 = 1
-1x1 + 1x2 + 1x3-1x4 + 0x5-1x6 + 1x7 = 3
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = -1x1-3x2-2x3-1x4 - Mx7 => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x7 = 3+x1-x2-x3+x4+x6
которые подставим в целевую функцию:
F(X) = -x1-3x2-2x3-x4 - M(3+x1-x2-x3+x4+x6) => max
или
F(X) = (-1-M)x1+(-3+M)x2+(-2+M)x3+(-1-M)x4+(-M)x6+(-3M) => max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| 1 | -1 | 0 | -1 | 1 | 0 | 0 |
| -1 | 1 | 1 | -1 | 0 | -1 | 1 |
Решим систему уравнений относительно базисных переменных:
x5, x7,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,1,0,3)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x5 | 1 | 1 | -1 | 0 | -1 | 1 | 0 | 0 |
| x7 | 3 | -1 | 1 | 1 | -1 | 0 | -1 | 1 |
| F(X0) | -3M | 1+1M | 3-1M | 2-1M | 1+1M | 0 | 1M | 0 |
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее. Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| x5 | 1 | 1 | -1 | 0 | -1 | 1 | 0 | 0 | 0 |
| x7 | 3 | -1 | 1 | 1 | -1 | 0 | -1 | 1 | 3 |
| F(X1) | -3M | 1+1M | 3-1M | 2-1M | 1+1M | 0 | 1M | 0 | 0 |
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 1 войдет переменная x3
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
|
| 
| 
| 
| 
| 
| 
|
|
| 3 / 1 = 3 | -1 / 1 = -1 | 1 / 1 = 1 | 1 / 1 = 1 | -1 / 1 = -1 | 0 / 1 = 0 | -1 / 1 = -1 | 1 / 1 = 1 |
|
| 
| 
| 
|
| 
| 
| 
|
| Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x5 | 1 | 1 | -1 | 0 | -1 | 1 | 0 | 0 |
| x3 | 3 | -1 | 1 | 1 | -1 | 0 | -1 | 1 |
| F(X1) | -6 | 3 | 1 | 0 | 3 | 0 | 2 | -2+1M |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x5 | 1 | 1 | -1 | 0 | -1 | 1 | 0 | 0 |
| x3 | 3 | -1 | 1 | 1 | -1 | 0 | -1 | 1 |
| F(X2) | -6 | 3 | 1 | 0 | 3 | 0 | 2 | -2+1M |
Составим двойственную задачу к прямой задаче.
Решение двойственной задачи дает оптимальную систему оценок ресурсов.Выясним экономический смысл двойственной задачи. Заметим, что каждое слагаемое в левой части ограничений должно измеряться в тех же единицах, что и правая.
Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов.
Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj.
y1+y2=-1
-y1-y2=-3
-y2=-2
-y1+y2=-1
y1-3y2 => min
y1 ≥ 0
y2 ≥ 0
Переменные yj называются допустимым решением двойственной задачи. Переменные yj называются оптимальными, если они допустимые и на них целевая функция достигает минимальное значения.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 2
Z(Y) = 1*0+-3*2 = -6
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Определение дефицитных и недефицитных (избыточных) ресурсов
Вторая теорема двойственности.Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
1*0 + -1*0 + 0*3 + -1*0 = 0 < 1
1*0 + -1*0 + -1*3 + 1*0 = -3 = -3
1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0.
Неиспользованный экономический резерв ресурса 1 составляет 1 (1-0).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
Обоснование эффективности оптимального плана
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:1*0 + 1*2 = 2 > -1
-1*0 + -1*2 = -2 > -3
0*0 + -1*2 = -2 = -2
-1*0 + 1*2 = 2 > -1
1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x1 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (2 - -1 = 3) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x2 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (-2 - -3 = 1) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x3>0).
4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x4 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (2 - -1 = 3) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
Влияние запасов ресурсов на оптимальное решение прямой задачи.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции F(x) при увеличении дефицитного ресурса на единицу.
Анализ устойчивости оптимального плана.
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
2-ый параметр целевой функции может изменяться в пределах:
0 ≤ Δс2 ≤ 2
Таким образом, 2-параметр может быть уменьшен на 0 или увеличен на 2
Интервал изменения равен:
[-3+0; -3+2] = [-3;-1]
Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится.
Найдем интервалы устойчивости ресурсов.
2-ый запас может изменяться в пределах:
0 ≤ Δb2 ≤ 3
Таким образом, 2-ый запас может быть уменьшен на 0 или увеличен на 3
Интервал изменения равен:
[-3+0; -3+3] = [-3;0]
В оптимальный план не вошла основная переменная x1, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок:
x1 может изменяться в пределах:
-3 ≤ x1 ≤ 1
Пример №2. Решить предложенную задачу управления производством методом линейного программирования.
Решение задачи провести в следующей последовательности:
- по предложенному описанию составить математическую модель;
- выполнить решение симплекс-методом;
- сделать заключение по результатам решения.
Обработка деталей А и В производится на трех станках. Деталь при изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации А составляет 100 руб., детали В – 160 руб. Исходные данные задачи представлены в таблице.
Определить производственную программу, максимизирующую прибыль при условии, что требуется произвести не менее 300 деталей А и не более 200 деталей В.
| Станки | Норма времени на обработку детали, ч | Время работы станка, ч | |
| А | В | ||
| 1-й | 0,2 | 0,2 | 100 |
| 2-й | 0,2 | 0,5 | 180 |
| 3-й | 0,1 | 0,2 | 100 |
Решение. Математическая модель задачи
x1 – количество деталей А,
x2 – количество деталей В,
x1, x2 ≥ 0, x1, x2 – целые числа
Ограничения по ресурсам.
0,2x1 + 0,2x2 ≤ 100
0,2x1 + 0,5x2 ≤ 180
0,1x1 + 0,2x2 ≤ 100
Отграничения по количеству.
x1 ≥ 300
x2 ≤ 200
Целевая функция
100x1 + 160x2 → max
Далее задача решается стандартным калькулятором (ответ: x1 = 300; x2 = 200).
Пример №3. Две культуры – кормовая свекла и кукуруза на силос – могут возделываться без орошения и с поливом. Площадь орошаемой пашни, выделенного под эти культуры, составляет 580 га, площадь богарных земель – 200 га. Ресурсы труда – 12000 чел.-дн., ресурсы воды – 1500 тыс. м3.
Норма затрат ресурсов и урожайность культур.
Показатели Кормовая свекла Кукуруза на силос.
без полива на поливе без полива на поливе.
1. Затраты труда, чел.-дн. 40 50 20 30
2. Норма полива, м3/га - 1 - 2
3. Выход кормов с 1 га, ц.к.ед. 30 50 22 60
Определить оптимальное сочетание посевов указанных культур, обеспечивающее максимальное производство кормов. Дать экономическое описание оптимального решения.
Решение.
x1 - площадь под кормовую свеклу без полива
x2 - площадь под кормовую свеклу с поливом
x3 - площадь под кукурузу без полива
x4 - площадь под кукурузу с поливом
Ограничения по ресурсам:
40x1 + 50x2 + 20x3 + 30x4 ≤ 12000
x2 + 2x4 ≤ 1500
Ограничения по площади:
x1 + x3 ≤ 580
x2 + x4 ≤ 200
Целевая функция:
30x1 + 50x2 + 22x3 + 60x4 → max
Пример №4. Для производства продукций "А" и "В" используется четыре вида взаимозаменяемых ресурсов S1, S2, S3, S4. На изготовление единицы продукции "А" расходуется 3 единицы ресурса S1, 5 единиц ресурса S3, 1 единица ресурса S4, но при этом высвобождается 1 единица ресурса S2. На изготовление единицы продукции "В" расходуется 2 единицы ресурса S1, 1 единица ресурса S2, 2 единицы ресурса S3, но при этом высвобождается 2 единицы ресурса S4. Прибыль от реализации единицы продукции "В" составляет 3 руб., продукции "А" - 5 руб. Найти размеры максимальной и минимальной прибылей при условии, что запасы ресурсов S1 насчитывают 18 единиц, S2 - 3 единицы, S3 - минимум 10 единиц, а ресурса S4 - 4 единицы.
Математическая модель задачи.
x1 - количество изготовленной продукции A, x2 - количество изготовленной продукции B.
x3 – количество ресурсов S1, x4 – количество ресурсов S2, x5 – количество ресурсов S3, x6 – количество ресурсов S4.
Система ограничений:
3x1 + 2x2 ≤ x3 + x4 + x5 + x6
x2 - x4≤ x3 + x4 + x5 + x6
5x1 + 2x2 ≤ x3 + x4 + x5 + x6
x1- 2x6≤ x3 + x4 + x5 + x6
Ограничения по ресурсам:
x3 ≤ 18
x4 ≤ 3
x5 ≥ 10
x6 ≤ 4
Целевая функция:
5x1 + 3x2 → min
5x1 + 3x2 → max
Пример №5. В агентство по торговле недвижимостью обратилось СП “Crocodile”, желающее купить квартиры своим сотрудникам. Филиалы СП находятся в разных районах Москвы (Кутузовский проспект, Коньково, Митино, Текстильщики), поэтому квартиры предполагается покупать в именно этих районах. Агентство предоставило следующую информацию о стоимости квартир в этих районах(в тысячах $)
| Виды квартир | Кутузовский проспект | Коньково | Митино | Текстильщики | Прибыль |
| 1-а комнатная | 60 | 50 | 40 | 35 | 3 |
| 2-х комнатная | 100 | 75 | 60 | 50 | 5 |
| 3-х комнатная | 150 | 90 | 75 | 65 | 7 |
| 4-комнатная | 180 | 110 | 95 | 80 | 10 |
Математическая модель задачи.
x11 - количество однокомнатных квартир на Кутузовском проспекте,
x12 - количество однокомнатных квартир в Коньково,
x13 - количество однокомнатных квартир в Митино,
x14 - количество однокомнатных квартир в Текстильщиках,
x21 - количество двухкомнатных квартир на Кутузовском проспекте,
x22 - количество двухкомнатных квартир в Коньково,
x23 - количество двухкомнатных квартир в Митино,
x24 - количество двухкомнатных квартир в Текстильщиках,
x31 - количество трехкомнатных квартир на Кутузовском проспекте,
x32 - количество трехкомнатных квартир в Коньково,
x33 - количество трехкомнатных квартир в Митино,
x34 - количество трехкомнатных квартир в Текстильщиках,
x41 - количество четырех комнатных квартир на Кутузовском проспекте,
x42 - количество четырех комнатных квартир в Коньково,
x43 - количество четырех комнатных квартир в Митино,
x44 - количество четырех комнатных квартир в Текстильщиках,
Ограничения по затратам:
60*x11 + 100*x21 + 150*x31 + 180*x41 ≤ 700
50*x12 + 75*x22 + 90*x32 + 110*x42 ≤ 550
40*x13 + 60*x23 + 75*x33 + 95*x43 ≤ 400
35*x14 + 50*x24 + 65*x34 + 80*x44 ≤ 250
60*x11 + 100*x21 + 150*x31 + 180*x41 + 50*x12 + 75*x22 + 90*x32 + 110*x42 + 40*x13 + 60*x23 + 75*x33 + 95*x43 + 35*x14 + 50*x24 + 65*x34 + 80*x44 ≤ 2000
Ограничения по количеству:
x21+x22+x23+x24 + x31+x32+x33+x34 ≥ 5
x41+x42+x43+x44 ≤ x11+x12+x13+x14
Ограничения по равенству квартир в районах:
x11 = x12
x12 = x13
x13 = x14
x21 = x22
x22 = x23
x23 = x24
x31 = x32
x32 = x33
x33 = x34
x41 = x42
x42 = x43
x43 = x44
Целевая функция:
3*(x11 + x12 + x13 + x14) + 5*(x21 + x22 + x23 + x24) + 7*(x31 + x32 + x33 + x34) + 10*(x41 + x42 + x43 + x44) = max
Ответ: В каждом районе продать по 2 двухкомнатные и по 3 трехкомнатные квартиры (ответ округлен).
Пример. Предприятие выпускает 3 вида микросхем: M1, M2, M3. Для производства используются одни и те же ресурсы: кремний (S), алюминий (Al), золото (Au), пластик (P), которые берутся в разных количествах. Расход ресурсов на единицу продукции каждого вида приведен в таблице 1. Максимальные суточные запасы ресурсов приведены в таблице 2. Изучение рынка сбыта показало, что разница суточного спроса между отдельно взятыми видами микросхем (Продукт1 – Продукт2) никогда не превышает величин, приведенных в таблице 3. Цены за микросхему каждого вида приведены в таблице 4.
Какое количество микросхем каждого вида должно производить предприятие, чтобы суммарный суточных доход от реализации был максимальным? Чему равен максимальный суточный доход?
Построить неизбыточную математическую модель задачи в соответствии с вариантом и найти ее решение средствами Microsoft Excel.
Таблица №1
| Ресурс \ Продукт | M1 | M2 | M3 |
| S | 12 | 10 | 14 |
| Al | 10 | 12 | 10 |
| Au | 8 | 9 | 7 |
| P | 2 | 3 | 2 |
| Ресурс | Максимальный запас |
| S | 100 |
| Al | 90 |
| Au | 100 |
| P | 120 |
| Продукт1\Продукт2 | M1 | M2 | M3 |
| M1 | 0 | -10 | -7 |
| M2 | 10 | 0 | 3 |
| M3 | 7 | -3 | 0 |
| Продукт | M1 | M2 | M3 |
| Цена | 3,5 | 3,4 | 3,6 |
Решить задачу средствами MS Excel, симплекс-методом и двойственным методом
Решение:
Составляем математическую модель задачи.
x1 – производство продукта М1,
x2 – производство продукта М2,
x3 – производство продукта М3,
Ограничения по ресурсам:
12x1 + 10x2 + 14x3 ≤ 100
10x1 + 12x2 + 10x3 ≤ 90
8x1 + 9x2 + 7x3 ≤ 100
2x1 + 3x2 + 2x3 ≤ 120
Ограничения по суточному спросу:
x1 - x2 ≤ -10
x1 – x3 ≤ -7
x2 – x3 ≤ 3
Целевая функция:
F(x) = 3,5x1 + 3,4x2 + 3,6x3 → max
- Решаем симплексную задачу средствами Excel.
Для этого используем сервис Симплекс-метод в Excel. Заполняем исходные данные и получаем шаблон решения в формате csv. Далее решение проводится с помощью инструмента Поиск решения. - Чтобы решить задачу симплекс-методом воспользуемся сервисом Симплекс-метод.
- Для получения решения симплексной задачи двойственным методом применим сервис двойственным симплекс-метод.