Формулировка основных типов задач ЛП, построение их математических моделей
Задачи, решаемые методами ЛП, очень разнообразны по содержанию. Но их математические модели схожи и условно объединяются в три большие группы задач:- транспортные задачи;
- задачи о составлении плана;
- задачи о смеси (о диете).
Транспортная задача
На двух торговых базах А и В имеется 30 гарнитуров мебели, по 15 на каждой. Всю мебель требуется доставить в два мебельных магазина, С и Д причем в С надо доставить 10 гарнитуров, а в Д - 20. Известно, что доставка одного гарнитура с базы А в магазин С обходится в одну денежную единицу, в магазин Д - в три денежных единицы. Соответственно с базы В в магазины С и Д: две и пять денежных единиц. Составить план перевозок так, чтобы стоимость всех перевозок была наименьшей.Данные задачи для удобства разметим в таблице. На пересечении строк и столбцов стоят числа, характеризующие стоимость соответствующих перевозок (табл. 3.1).
Таблица 3.1
| магазины / базы | С | Д | отправлено гарнитуров |
| А | 1 | 3 | 15 |
| В | 2 | 5 | 15 |
| получено гарнитуров | 10 | 20 | 30 = 30 |
Составим математическую модель задачи.
Необходимо ввести переменные. В формулировке вопроса говорится, что необходимо составить план перевозок. Обозначим через х1, х2 количество гарнитуров, перевозимых с базы А в магазины С и Д соответственно, а через у1, у2 - количество гарнитуров, перевозимых с базы В в магазины С и Д соответственно. Тогда количество мебели, вывозимое со склада А, равно (х1 + х2), а со склада В - (у1 + у2). Потребность магазина С равна 10 гарнитурам, и в него привезли (х1 + у1) штук, т. е. х1 + у1 = 10. Аналогично, для магазина Д имеем х2 + у2 = 20. Заметим, что потребности магазинов в точности равны количеству гарнитуров, имеющихся на складах, поэтому х1 + у2 = 15 и у1 + у2 = 15. Если бы со складов вы увезли меньше, чем по 15 комплектов, то магазинам не хватило бы мебели для удовлетворения их потребностей.
Итак, переменные х1, х2, у1, у2 по смыслу задачи неотрицательны и удовлетворяют системе ограничений:
(3.1)
Обозначив через F транспортные расходы, посчитаем их. на перевозку одного комплекта мебели из А в С тратится одна ден. ед., на перевозку x1 комплектов - x1 ден. ед. Аналогично, на перевозку x2 комплектов из А в Д затратится 3x2 ден. ед.; из В в С - 2y1 ден. ед., из В в Д - 5y2 ден. ед.
Итак,
F = 1x1 + 3x2 + 2y1 + 5y2 → min (3.2)
(мы хотим, чтобы общая стоимость перевозок была минимальной).
Сформулируем задачу математически.
На множестве решений системы ограничений (3.1) найти такое решение, которое обращает в минимум целевую функцию F (3.2), или найти оптимальный план (x1, x2, y1, y2), определяемый системой ограничений (3.1) и целевой функцией (3.2).
Задача, которую мы рассмотрели может быть представлена в более общем виде, с любым числом поставщиков и потребителей.
В рассмотренной нами задаче наличие груза у поставщиков (15 + 15) равно общей потребности потребителей (10 + 20). Такая модель называется закрытой, а соответствующая задача - сбалансированной транспортной задачей.
В экономических расчетах немалую роль играют и так называемые открытые модели, в которых указанное равенство не соблюдается. Либо запас у поставщиков больше потребности у потребителей, либо спрос превышает наличие товара. заметим, что тогда в систему ограничений несбалансированной транспортной задачи наряду с уравнениями будут входить и неравенства.
Перейти к онлайн решению своей задачи
Рассмотрим пример несбалансированной транспортной задачи.
В пунктах А и В расположены кирпичные заводы, а в С и Д - карьеры, снабжающие их песком. потребность заводов в песке меньше, чем производительность карьеров. Известно, сколько песка нужно каждому из заводов и сколько добывается в каждом карьере. Также известна стоимость перевозки 1 т песка из каждого карьера к заводам (числа на стрелочках). Нужно так спланировать снабжение заводов песком, чтобы затраты на перевозку были наименьшими. Данные задачи на схеме.
Постоим математическую модель задачи.
Введем переменные:
x11 - количество тонн песка, перевозимого с карьера С на завод А;
x12 - с карьера С на завод А;
x21 - количество тонн песка в А с карьера Д;
x22 - количество тонн песка с карьера Д на завод В.
На завод А должно быть доставлено 40 т с обоих карьеров, значит x11 + x21 = 40, на завод В должно быть доставлено 50 т, значит x12 + x22 = 50. Из карьера С вывезено не более 70 т, т. е. x11 + x12 ≤ 70, аналогично x21 + x22 ≤ 30. Имеем систему ограничений:
(3.3)
И целевая функция F, выражающая стоимость перевозок, имеет вид
F= 2x11 + 6x12 + 5x21 + 3x22→min. (3.4)
Задача о составлении плана
Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. - за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов (табл. 3.2).Таблица 3.2
Изделия |
Виды машин | |||
| 1 | 2 | 3 | 4 | |
| I | 1 | 0,5 | 1 | 0 |
| II | 1 | 1 | 0 | 1 |
| Возможное время работы машин | 18 | 12 | 12 | 9 |
Построим математическую модель.
В задаче необходимо определить план выпуска изделий, обозначим за x количество изделий I вида, за y - количество изделий II вида. Тогда посчитаем, сколько времени затратит первая машина на обработку всех производственных изделий. Она тратит одну единицу времени на одного изделие I вида, значит на x штук изделий потратит 1x ед. времени, на обработку y изделий II вида затратится 1y ед. времени. Всего резерв времени работы первой машины - 18 единиц времени. Значит, x + y ≤ 18. Аналогичные рассуждения со второй машиной, третьей и четвертой дадут систему ограничений:
(3.5)
Общая прибыль будет выражена в целевой функции:
F = 4x + 6y → max. (3.6)
Задача состоит в нахождении на множестве решений системы (3.5) такого решения, при котором значение целевой функции (3.6) было бы максимальным.
Задача составления смеси
Еще одна распространенная задача ЛП - задача о составлении смеси. Примером таких задач может быть задача о составлении таких смесей нефтепродуктов, которые бы удовлетворяли определенным техническим требованиям и были наиболее дешевыми по стоимости. Либо задачи о рационе, когда известна потребность в определенных веществах и содержание этих веществ в различных продуктах. Необходимо составить рацион так, чтобы удовлетворить потребности в необходимых веществах и при этом продуктовая корзина имела бы минимальную стоимость при заданных ценах на продукты.Практически подобные задачи ставятся, к примеру, в любом животноводческом хозяйстве и имеют очень большой спектр применения.
Рассмотрим пример. Для откорма цыплят на птицефабрике в их рацион необходимо включать не менее 33 единиц вещества А, 23 единиц питательного вещества В, 12 единиц С. Для откорма используются три вида корма. Данные о содержании питательных веществ в каждом виде корма заданы таблицей. Также известна стоимость кормов. Необходимо составить наиболее дешевый рацион (табл. 3.3).
Таблица 3.3
| Корма-продукты | Вещества | Стоимость 1 ед. корма | ||
| А | В | С | ||
| I | 4 | 3 | 1 | 20 |
| II | 3 | 2 | 1 | 20 |
| III | 2 | 1 | 2 | 10 |
Для понимания задачи можете представить себе, что вещества А, В, С - это жиры, белки, углеводы, а продукты I, II, III - то, чем кормят цыплят, например пшено, комбикорм, витаминные добавки. Тогда первая строка таблицы показывает содержание в одной единице пшена: 4 ед. белка, 3 ед. жиров, одной ед. углеводов. Вторая строка - содержание белков, жиров, углеводов в 1 ед. II продукта и т. д.
Если постановка задачи ясна, приступим к построению математической модели.
В качестве ответа на поставленную задачу мы должны предложить рацион, т. е. указать сколько и каких кормов взять, чтобы необходимое количество питательных веществ было соблюдено и при этом он стоил как можно дешевле.
Поэтому, обозначим за x1 количество кормов типа I в рационе, за x2 - количество кормов типа II и, соответственно, x3 - количество корма III в рационе. Тогда, вещества А при употреблении такого рациона цыплята получат 4x1 - при потреблении продуктов типа I, 3x2 - при потреблении II продукта, 2x3 - при потреблении III. Всего вещества А необходимо употребить по условию задачи не менее 33 единиц, следовательно 4x1 + 3x2 + 2x3 ≥ 33.
Аналогично рассуждая с веществами В и С, имеем:
3x1 + 2x2 + 1x3 ≥ 23 и x1 + x2 + 2x3 ≥ 12.
Таким образом, получим систему ограничений:
(3.7)
Переменные неотрицательны по смыслу задачи. При этом стоимость рациона выражается функцией:
F = 20x1 + 20x2 + 10x3 → min, (3.8)
т. к. 20, 20, 10 - стоимость одной ед. продуктов I, II, III типов соответственно, а в рационе их содержится x1, x2, x3 единиц.
Система ограничений (3.7) вместе с целевой функцией (3.8) и составляют математическую модель исходной задачи. Решить ее - значит найти x1, x2, x3, удовлетворяющие системе ограничений и обращающие значение функции F в минимальное.
Расстановка типов судов по линиям
Построить такой план расстановки двух типов судов по трем линиям, который обеспечил бы максимум суммарной провозной способности флота, но не меньше заданного на линиях объема перевозок.| Тип судна | Производительность судов, млн. тонно-миль в сутки | Эксплуатационный период, сутки | ||
| 1-я линия | 2-я линия | 3-я линия | ||
| 1 | p11 | p12 | p13 | s1 |
| 2 | p21 | p22 | p23 | s2 |
| Заданный объем перевозки, млн. тонно-миль | V1 | V2 | V3 | |
Экономико-математическая модель задачи.
Ограничения по эксплуатационному периоду:
x1/p11+ x2/p12+ x3/p13 ≤ s1
x4/p21+ x5/p22+ x6/p23 ≤ s2
Ограничения по поставкам:
s1x1+ s2x4 ≥ V1
s1x2+ s2x5 ≥ V2
s1x3+ s2x6 ≥ V3
Целевая функция
p11x1+p12x2+p13x3+p21x4+p22x5 +p23x6 → max
Построение математической модели для симплекс-задачи
Пример №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. Далее решение проводится с помощью инструмента Поиск решения. - Чтобы решить задачу симплекс-методом воспользуемся сервисом Симплекс-метод.
- Для получения решения симплексной задачи двойственным методом применим сервис двойственным симплекс-метод.
Вопросы для самоконтроля
1. Постановка транспортной задачи. опишите построение математической модели.
2. Что такое сбалансированная и несбалансированная транспортная задача?
3. Что подсчитывается в целевой функции транспортной задачи?
4. Что отражает каждое неравенство системы ограничений задачи о плане?
5. Что отражает каждое неравенство системы ограничений задачи о смеси?
6. Что обозначают переменные в задаче о плане и задаче о смеси?