Цель лекции: Показать возможность графического решения задач с двумя неизвестными.
Математическое программирование занимается исследованием детерминированных и одноцелевых задач. Слово "программирование" в данном случае означает "планирование". К математическому программированию относится:
Математическая модель любой задачи линейного программирования включает в себя:
Решение практической задачи всегда связано с исследованием, с преобразованием некоторого объекта (материального или информационного) или с управлением им (рисунок 1.1).
(рис 1.1) Схема моделирования объекта (процесса)
При решении "стандартной" задачи в линейном программировании нужно определить максимум линейной целевой функции
$$f(x)=\sum_{i=1}^n c_i x_i=c_1 x_1 + c_2 x_2 + \cdots+ c_n x_n$$
при условиях
$$r_j=\sum_{i=1}^n a_{ij} x_i\le R_j$$ $$j=1,2,\ldots, m$$
Здесь целевая функция формируется как скалярное произведение двух векторов. Один из них — вектор искомых переменных $$x_i$$. Компонентами другого вектора являются целевые коэффициенты $$с_i$$. Условия задачи можно сформулировать так: "Расход $$r_j$$ не должен превышать имеющиеся ресурсы $$R_j$$". Вектор расхода $$r_j$$ есть сумма произведений матрицы нормированных коэффициентов $$a_{ij}$$ на вектор искомых переменных $$x_i$$.
Основной аналитический метод решения задач линейного программирования — это симплексный метод . Он сводится к вычислительной процедуре, основанной на принципе последовательного улучшения решений — перехода от одной базисной точки к другой, для которой значение целевой функции больше. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса (n-мерного тетраэдра). Симплекс-метод послужил исходным пунктом для разработки целого семейства алгоритмов решения как линейных, так и нелинейных выпуклых задач оптимизации.
Фирма производит две модели $$А$$ и $$В$$ сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели $$А$$ требуется $$3м^2$$ досок, а для модели $$В$$ — $$4м^2$$. Фирма может получать от своих поставщиков до $$1700м^2$$ досок в неделю. Для каждого изделия модели $$А$$ требуется 12 мин. машинного времени, а для изделия модели $$В$$ — 30 мин. В неделю можно использовать 160 часов машинного времени.
Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие модели $$А$$ приносит 200 руб. прибыли, а каждое изделие модели $$В$$ — 400 руб. прибыли?
В данном случае объектом является фирма, а ее деятельность представляется в виде математической модели, т.е. учитываются только некоторые количественные стороны этой деятельности. Менеджер (субъект) ставит себе задачу: составить недельный производственный план фирмы. При этом он руководствуется целью моделирования — максимальной эффективностью производства, получением максимальной прибыли.
Построение математической модели
Пусть $$x_1$$ - количество выпущенных за неделю полок модели $$А$$, а $$x_2$$ — количество выпущенных за неделю полок модели $$В$$. Тогда составим следующие соотношения:
$$3x_1$$ - количество досок, требуемых на неделю для изготовления полок модели $$А$$.
$$4x_2$$- количество досок, требуемых на неделю для изготовления полок модели $$В$$.
$$3x_1 + 4x_2$$- количество досок требуемых на неделю для изготовления книжных полок двух моделей. По условию задачи это число не должно превышать $$1700м^2$$, следовательно, получаем первое ограничение:
$$3x_1 + 4x_2 <=1700$$
Найдем ограничение на использование машинного времени.
12 мин. составляют 0,2 часа, а 30 мин. — 0,5 часа, таким образом:
$$0{,}2x_1$$ - количество времени, требуемое на неделю для обработки полок модели $$А$$;
$$0{,}5x_2$$ - количество времени, требуемое на неделю для обработки полок модели $$В$$;
$$0{,}2x_1 + 0{,}5x_2$$ - количество времени, требуемое на неделю для обработки двух моделей. По условию задачи это число не должно превышать 160 часов, следовательно, получаем второе ограничение:
$$0{,}2x_1 + 0{,}5x_2 <=160$$ или $$2x_1 + 5x_2 <=1600$$
Кроме того, поскольку $$x_1$$ и $$x_2$$ выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательными, то есть
$$x_1 >=0, x_2 >=0,$$Наша задача состоит в том, чтобы найти такие значения $$x_1$$ и $$x_2$$, при которых еженедельная прибыль будет максимальной. Составим выражение для еженедельной прибыли:
$$200x_1$$ - еженедельная прибыль, получаемая от продажи полок модели $$А$$.
$$400x_2$$ - еженедельная прибыль, получаемая от продажи полок модели $$В$$.
$$F=200x_1+400x_2$$ - еженедельная прибыль, которая должна быть максимальной.
Таким образом, имеем следующую математическую модель для данной задачи:
$$3x_1+4x_2 <=1700$$;
$$2x_1+5x_2 <=1600$$;
$$F(х_1, х_2)=200x_1+400x_2 \Rightarrow max;$$
$$x_1 >= 0,$$ $$x_2 >= 0,$$ $$x_1=\mbox{целое},$$ $$x_2=\mbox{целое}.$$
Необходимо найти значения переменных $$x_1$$ и $$x_2$$, при которых данная функция $$F$$ принимает максимальное значение, при соблюдении ограничений, накладываемых на эти переменные.
Решения, удовлетворяющие системе ограничений и требованию неотрицательности, являются допустимыми, а решения, удовлетворяющие одновременно и требованию максимизации (минимизации) целевой функции являются оптимальными.
Область допустимых решений целевой функции $$F()$$ можно найти графическим методом.
Построим прямоугольную систему координат, где по оси $$ОX$$ отложим значения $$x_1$$, а по оси $$OY$$ отложим значения $$x_2$$. Так как, согласно условию (3), $$x_1$$ и $$x_2$$ неотрицательны, то можно ограничиться рассмотрением первого квадранта (рисунок 1.2).
Рассмотрим первое ограничение:
$$3x_1+4x_2 <=1700$$
Заменим в данном ограничении знак неравенства знаком равенства и построим прямую
$$3x_1+4x_2=1700$$
Для этого найдем две точки, принадлежащие данной прямой. Пусть, например, $$x_1=0$$, $$4x_2=1700$$ или $$x_2=425$$. $$(0, 425)$$ — координаты первой точки, принадлежащей прямой.
Пусть $$x_2=0$$, то $$3x_1=1700$$, следовательно, $$x_1=567$$. $$(567, 0)$$ — координаты второй точки, принадлежащей прямой. Отметим эти точки на числовых осях.
Аналогично, для второго ограничения:
$$2x_1+5x_2 <=1600$$
$$2x_1+5x_2=1600$$
При $$x_1=0$$, $$x_2=320$$ $$(0; 320)$$
При $$x_2=0$$, $$x_1=800$$ $$(800; 0)$$
Построим данные прямые (на рисунке они соответственно обозначены (1) и (2))
Теперь найдем на чертеже такие полуплоскости, которые соответствуют неравенствам (1) и (2). Прямая (1) делит координатную плоскость на две полуплоскости. Одна полуплоскость расположена выше прямой, вторая ниже. Чтобы найти ту полуплоскость, которая соответствует неравенству (1), необходимо взять любую точку, принадлежащую одной из полуплоскостей и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой.
(рис 1.2) Графическое решение задачи о максимальной прибыли
Например, возьмем точку с координатами $$(0; 0)$$ и подставим ее координаты в неравенство (1) $$3x_1+4x_2 <=1700$$. Получается $$0 <= 1700$$ - данное неравенство является верным, следовательно, неравенству (1) удовлетворяет полуплоскость, лежащая ниже прямой (1).
Аналогично, поступим для неравенства (2) $$2x_1+5x_2 <= 1600$$. Возьмем точку с координатами $$(0; 0)$$. Получается $$0 <= 1600$$ - данное неравенство верно. Неравенству (2) удовлетворяет полуплоскость, расположенная ниже прямой (2). Стрелки на каждой границе показывают, с какой стороны прямой выполнены ограничения. Учитывая неравенства (3), получаем, что выделенный четырехугольник $$ОАВС$$ является областью, содержащей точки, для которых выполнены условия (1-3). Точки, лежащие внутри и на границе этой области, являются допустимыми решениями. Среди всех допустимых решений нужно найти оптимальное решение, при котором функция $$F$$ будет принимать максимальное значение.
Для поиска оптимального решения построим по функции $$F()$$ прямую уровня.
Возьмем произвольную точку, принадлежащую области допустимых решений — четырехугольнику $$ОАВС$$, например, точку $$M$$ с координатами $$(100; 100)$$. Подставим координаты точки $$M$$ в функцию $$F$$.
$$F(100; 100)=200*100+400*100=60000$$
Прямая уровня будет иметь следующий вид: $$2x_1+4x_2=600$$
Построим полученную прямую. Для этого необходимо найти координаты двух произвольных точек этой прямой. Одна точка у нас уже есть — это точка $$M(100; 100)$$. Найдем еще одну точку. Пусть $$x_2=0$$, тогда $$x_1=300$$. Следовательно, координаты дополнительной точки $$(300; 0)$$. Отметим полученные точки и построим прямую уровня (на рисунок 1.2 она обозначена (3)).
Значения функции $$F$$ будут возрастать по мере того, как прямая уровня удаляется от начала координат в положительном квадранте. Направление возрастания функции $$F$$ будет совпадать с вектором, координаты которого являются коэффициентами при переменных $$x_1$$ и $$x_2$$ функции $$F$$. На рисунке — это вектор $$a\{2, 4\}$$, отложенный от точки $$М$$. Обратите внимание, что вектор $$a$$, определяющий направление возрастания функции $$F$$, всегда будет перпендикулярен прямой уровня.
Максимизация целевой функции $$F$$
Для нахождения точки, в которой функция $$F$$ достигнет своего максимального значения, необходимо перемещать прямую уровня по направлению вектора $$a$$ до пересечения этой прямой с граничной точкой области допустимых решений. На нашем рисунке — это точка В.
Найдем координаты точки $$B$$. Данная точка расположена на пересечении двух прямых (1) и (2), поэтому, чтобы найти ее координаты необходимо решить следующую систему уравнений:
$$3x_1+4x_2=1700$$;
$$2x_1+5x_2=1600$$.
Легко убедиться, что оптимальное решение этой задачи задается в вершине выпуклого четырехугольника координатами
$$x_1=300$$; $$x_2=200$$.
Значит, чтобы получить максимальную прибыль $$F=200x_1+400x_2=60000+80000=140000$$ руб., фирме необходимо выпускать в неделю триста полок модели $$А$$ и двести полок модели $$В$$.
Для птицефабрики требуется составить самый дешевый рацион питания цыплят в виде смеси из корма $$А$$ и корма $$Б$$. Цыплята должны получить необходимую дозу витамина В1 — тиамина и витамина С — аскорбина при достаточной калорийности питания. Сколько надо взять граммов корма $$А$$ и корма $$Б$$ для каждой порции оптимальной смеси, чтобы удовлетворить потребность цыплят в витаминах и питательности корма?
Исходные данные для поиска решения приведены в таблице:
| Тиамин, мг | Аскорбин, мг | Калории, кал | Цена, руб. | |
|---|---|---|---|---|
| Корм А, г | 0,1 | 1 | 110 | 3,80р. |
| Корм Б, г | 0,25 | 0,25 | 120 | 4,20р. |
| Потребность | 1 | 5 | 400 |
Для наглядного представления представим условия задачи в виде ментальной карты.
$$F(X1, X2)=3{,}80*Х1+4{,}20*Х2\Rightarrow MIN$$
Оптимальному решению отвечает минимум
$$0{,}10 X1+0{,}25 X2 >=1$$ потребление тиамина не менее нормы;
$$1{,}00 X1+0{,}25 X2 >=5$$ потребление аскорбина не менее нормы;
$$110 X1+120 X2 >=400$$ калорийность питания не должна быть ниже нормы;
$$X1 >=0, X2 >=0$$ переменные $$Х1$$ и $$Х2$$ не могут быть отрицательными.
Так как в данной задаче только две переменные, то вначале определим решение графически. В декартовой системе координат $$Х1$$, $$Х2$$ построим прямые, соответствующие условиям (1), (2), (3).
$$0{,}10 X1+0{,}25 X2=1$$;
$$1{,}00 X1+0{,}25 X2=5$$;
$$110 X1+120 X2=400$$.
В соответствии с ограничением (4) мы должны рассматривать только область первого квадранта. Подставляя в условия (1) – (3)
значения начала координат $$(0,0)$$, находим, что
Результаты графического решения:
При застройке нового микрорайона требуется определить месторасположение нового торгового центра. Для обеспечения удобства всех жителей микрорайона необходимо так расположить торговый центр, чтобы суммарное расстояние переходов от него до жилых массивов было бы минимальным, а расстояние от каждого жилого массива до торгового центра не превышало бы 5. Координаты жилых массивов приведены в таблице 1.
| Координаты жилых массивов | ||
|---|---|---|
| X | Y | |
| Жилой массив 1 | 2 | 8 |
| Жилой массив 2 | 10 | 9 |
| Жилой массив 3 | 5 | 2 |
| Жилой массив 4 | 11 | 9 |
На рисунок 1.4 представлена наглядная схема расположения жилых массивов (1), (2), (3), (4). Между ними должен быть размещен торговый центр ТЦ с координатами $$Х_0$$, $$Y_0$$.
(рис 1.4) — Схема расположения жилых массивов
На рисунке показано, как вычисляют расстояния $$L_3$$ между жилым массивом (3) и торговым центром: $$L_3$$ является гипотенузой треугольника с катетами $$(X_0-X_3)$$ и $$(Y_0-Y_3)$$. Аналогичным образом определяются и другие расстояния.
| Формула | Назначение | Примечание |
|---|---|---|
| $$\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}$$ | Расстояние между жилым массивом $$i$$ и торговым центром | $$X_0$$, $$Y_0$$ — координаты торгового центра, $$x_i$$, $$y_i$$ — координаты жилых массивов $$(i=1,2,3,4)$$ |
| $$\sum_{i=1}^n\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}$$ | Суммарное расстояние между жилыми массивами и торговым центром | $$n$$ — количество жилых массивов $$(n=4)$$ |
| $$\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}\Rightarrow min$$ | Суммарное расстояние между жилыми массивами и торговым центром должно быть минимальным |
Построим прямоугольную систему координат, где по оси $$ОX$$ отложим значения $$X_0$$, а по оси $$OY$$ отложим значения $$Y_0$$. Значения $$x_1$$ и $$x_2$$ неотрицательны, поэтому можно ограничиться рассмотрением первого квадранта. Из условий задачи и рисунка 1.4 следует, что $$X_0$$ находится в интервале 2 – 11, а $$Y_0$$ не выходит из интервала 2 – 9.
Из формулы расстояния между жилым массивом $$i$$ и торговым центром выразим явным образом зависимость $$Y_0$$ от $$X_0$$:
$$\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}\le 5$$
$$(Y_0-y_i)^2\le 25-(X_0-x_i)^2$$
$$Y_0\le y_i\pm \sqrt{25-(X_0-x_i)^2} $$
Знак + перед корнем берется для $$i=3$$, в остальных случаях выбираем знак (-).
По последней формуле построим графики зависимости координат торгового центра от координат жилых массивов (1), (2), (3), (4). Они показаны на рисунок 1.5.
(рис 1.5) Нахождение решения нелинейной задачи
Каждая из кривых делит координатную плоскость на две части. Одна часть расположена выше прямой, вторая ниже. Чтобы найти ту полуплоскость, которая соответствует неравенствам, необходимо взять любую точку, принадлежащую одной из полуплоскостей (например, точку 7,4) и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой. Эти полуплоскости выделены штриховкой у каждой кривой.
Областью допустимых решений является замкнутый криволинейный треугольник $$АВС$$. Координаты торгового центра, выбранные в этом треугольнике,
удовлетворяют заданным неравенствам.
| Уравнения | $$X_0$$ | $$Y_0$$ | |
|---|---|---|---|
| $$А (3,4)$$ | $$Y_0=2+\sqrt{25-(X_0-5)^2}$$ $$Y_0=9-\sqrt{25-(X_0-11)^2}$$ | 6,53 | 6,76 |
| $$В (1,3)$$ | $$Y_0=8-\sqrt{25-(X_0-2)^2}$$ $$Y_0=2+\sqrt{25-(X_0-5)^2}$$ | 6,82 | 6,66 |
| $$С (1,4)$$ | $$Y_0=8-\sqrt{25(X_0-2)^2}$$ $$Y_0=9-\sqrt{25-(X_0-11)^2}$$ | 6,73 | 6,39 |
Вычисляя теперь расстояния от жилых массивов до торгового центра, легко проверить, что
Из приведенных примеров видно, что областью допустимых решений линейных задач оптимизации является выпуклый многоугольник,
в одной из вершин которого находится
Эффективные средства
В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel "Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:
Параметры задач ограничиваются такими предельными показателями:
Алгоритм поиска оптимальных решений включает в себя несколько этапов:
Последовательность необходимых подготовительных работ, выполняемых при решении задач экономико-математического моделирования с помощью MS Excel, приведена на блок-схеме рисунка 1.6.
(рис 1.6) Схема подготовительных работ
Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы требуют творчества — и разными людьми они могут быть выполнены по-разному. Кратко поясним сущность формулировок пунктов плана.
область переменных $$x_i$$;
область исходных нормированных коэффициентов $$a_{ij}$$;
область целевых коэффициентов $$c_i$$;
область задания
область
При постановке задачи известны целевые коэффициенты $$c_i$$ и нормированные коэффициенты $$a_ij$$ $$(i=1,2,\ldots, n; j=1,2,\ldots, m)$$. В предыдущем примере коэффициентами, формирующими целевую функцию, служили значения нормированной прибыли на одну полку типа $$А$$ ($$с_1=200\mbox{руб.}$$) и одну полку типа $$В$$ ($$с_2=400\mbox{руб.}$$). Нормированными коэффициентами $$a_{ij}$$ служили нормы расхода материала и машинного времени на одну полку каждого типа. Матрица $$a_{ij}$$ имела следующий вид:
$$a_{ij} = \left( \begin{array}{cc} 3м^2 4м^2 \\ 12 мин. 30 мин. \end{array} \right) $$
Кроме того, всегда известны значения
Таким образом, в диалоговом окне оптимизационной программы "Поиск решения" мы должны задать следующий целевой алгоритм:
$$F=\sum c_i x_i\Rightarrow max$$ - целевая функция равна произведению вектора искомых значений переменных $$x_i$$ на вектор целевых коэффициентов $$c_i$$
$$r_j=\sum a_{ij} x_i <=R_j$$ - нормированных коэффициентов
$$a_{ij}$$ на вектор искомых значений переменных $$x_i$$ не должен превышать значения заданного вектора
$$d_i=< x_i <=D_i$$ - значения переменной $$x_i$$ должны находиться в заданных пределах $$d_i\div D_i$$ число исходных элементов системы
$$i=1,2,\ldots,n$$ - число исходных элементов системы
$$j=1,2,\ldots,m$$ - число заданных видов
Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):
(рис 1.7) Схема отладки и анализа решения
При отладке рекомендуется возвращаться к заданию новых начальных условий:
Программа выдает
Анализ
Экономический анализ ставит перед собой следующие цели [2]:
Возможные методы анализа представлены в схеме на рисунке 1.8.
(рис 1.8) Виды анализа решения
После получения оптимального решения проводится его анализ по полученным отчетам. Анализ устойчивости — изучение влияния изменений отдельно взятых параметров модели на показатели оптимального решения. Анализ пределов — анализ допустимых изменений в оптимальном плане, при котором план остается оптимальным.
Учитывая ответственность принятия экономического управленческого решения, руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:
Анализ с целью ответа на первый вопрос называется вариантным анализом; анализ с целью ответа на второй вопрос называется решениями по заказу.
Вариантный анализ бывает следующих видов:
После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Математическая модель — приближенное описание объекта, выраженное с помощью математической символики, отражающее количественные соотношения между его элементами.
Симплекс-метод — вычислительная процедура, основанная на принципе последовательного улучшения решений.
Целевая функция — функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.
Матрица нормированных коэффициентов — постоянные параметры объекта моделирования.
Ресурс— количественная мера возможности выполнения какой-либо деятельности; условия, позволяющие с помощью определённых преобразований получить желаемый результат.
Область допустимых решений — все решения, которые удовлетворяют заданным ограничениям задачи.
Оптимальное решение — допустимое решение, для которого значение целевой функции максимально.
Анализ решения — заключительный этап математического моделирования экономических процессов.
Графическое решение задач оптимизации удобно применять в случае двух искомых переменных. Тогда за декартовые координаты $$X$$ и $$Y$$ принимают значения этих переменных. Если по физическому смыслу переменные могут быть только положительными, то решение ищется только в первом квадранте. Линейные ограничения на заданные ресурсы выражаются в виде прямых линий. Эти линии вместе с осями координат ограничивают область допустимых решений в виде выпуклого многоугольника. Оптимальное решение с экстремумом целевой функции находится в одной из вершин многоугольника. Координаты этой вершины являются искомыми значениями переменных.
В качестве упражнения предлагается решить графически следующую задачу по планированию работы зверофермы:
На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество кормов каждого вида, которое должны получать животные, приведено в таблице. В ней также указаны общее количество корма каждого вида, которое может быть использовано зверофермой ежедневно, и прибыль от реализации одной шкурки лисицы и песца. Определить, сколько лисиц и песцов можно вырастить при имеющихся запасах корма.
| Вид корма | Количество единиц корма, которое ежедневно должны получать | Запас корма | |
|---|---|---|---|
| лисица | песец | ||
| $$А$$ | 2 | 2 | 180 |
| $$Б$$ | 4 | 1 | 240 |
| $$В$$ | 6 | 7 | 426 |
| Прибыль от реализации одной шкурки, руб. | 1600 | 1200 | |
Попробуйте найти решение самостоятельно, а затем сравните его с приведенным ниже.
Пусть $$x_1$$ — количество лисиц, а $$x_2$$ — количество песцов, которые еще можно содержать при имеющихся материальных
Построим прямоугольную систему координат, где по оси $$ОX$$ отложим значения $$x_1$$, а по оси $$OY$$ отложим значения $$x_2$$. Значения $$x_1$$ и $$x_2$$ неотрицательны, поэтому можно ограничиться рассмотрением первого квадранта (рисунок 1.9).
Рассмотрим последовательно все ограничения по
$$2x_1+2x_2 <=180$$ — расход корма $$А$$ не может превышать его запасы.
Заменим в данном ограничении знак неравенства знаком равенства:
$$2x_1+2x_2=180$$ или
$$x_1+x_2=90$$
Построим прямую (1) на графике рисунке 1.9.
Аналогично, для второго и третьего ограничений:
$$4x_1+x_2 <=240$$ — расход корма $$Б$$ не может превышать его запасы.
$$6x_1+7x_2 <=426$$ — расход корма $$В$$ не может превышать его запасы.
Построим ограничительные прямые (2) и (3) по уравнениям:
$$4x_1+x_2=240$$;
$$6x_1+7x_2=426$$.
(рис 1.9) Нахождение оптимального решения
Каждая из прямых (1), (2), (3) делит координатную плоскость на две полуплоскости. Одна полуплоскость расположена выше прямой, вторая ниже.
Чтобы найти ту полуплоскость, которая соответствует неравенствам, необходимо взять любую точку, принадлежащую одной из полуплоскостей
(например, точку 0,0) и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой.
При подкормке посевов необходимо внести на 0,01 га почвы не менее 8 единиц азота, не менее 24 единиц фосфора и не менее 16 единиц калия. Фермер закупает комбинированные удобрения двух видов "Азофоска" и "Комплекс". В таблице указаны содержание количества единиц химического вещества в 1 кг каждого вида удобрений и цена 1 кг удобрений. Определить графически потребность фермера в удобрениях того и другого вида на 0,01 га посевной площади при минимальных затратах на потребление.
| Химические вещества | Содержание химических веществ в 1 кг удобрения | |
|---|---|---|
| Азофоска | Комплекс | |
| Азот | 1 | 2 |
| Фосфор | 12 | 3 |
| Калий | 4 | 4 |
| Цена 1 кг удобрения, руб. | 50 | 20 |
Ответ: для подкормки требуется на каждые 0,01 га закупить 1,14 кг "Азофоски" и 3,43 кг удобрения "Комплекс" на сумму 125, 71 руб. Внесение удобрений будет соответствовать такому графику:
Полной даме необходимо похудеть, а за помощью она обратилась к подруге. Подруга посоветовала перейти на рациональное питание, состоящее из двух продуктов P и Q.
Суточное питание этими продуктами должно давать менее 14 единиц жира (чтобы похудеть), но не менее 300 килокалорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 килокалорий, а на упаковке с продуктом Q — 4 единицы жира и 200 килокалорий соответственно. При этом цена продукта Р равна 250 руб./кг, а цена продукта Q равна 210 руб./кг.
Так как дама была стеснена в средствах, то ее интересовал вопрос: в какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?
Составьте ментальную карту по условиям задачи.
Решите задачу графически. Определите
Ответ: даме необходимо потреблять за сутки 0,00 кг продукта Р и 1,50 кг продукта Q, всего на сумму 315,00 руб.
Цель лекции: Показать возможность графического решения задач с двумя неизвестными.
Математическое программирование занимается исследованием детерминированных и одноцелевых задач. Слово "программирование" в данном случае означает "планирование". К математическому программированию относится:
Математическая модель любой задачи линейного программирования включает в себя:
Решение практической задачи всегда связано с исследованием, с преобразованием некоторого объекта (материального или информационного) или с управлением им (рисунок 1.1).
(рис 1.1) Схема моделирования объекта (процесса)
При решении "стандартной" задачи в линейном программировании нужно определить максимум линейной целевой функции
$$f(x)=\sum_{i=1}^n c_i x_i=c_1 x_1 + c_2 x_2 + \cdots+ c_n x_n$$
при условиях
$$r_j=\sum_{i=1}^n a_{ij} x_i\le R_j$$ $$j=1,2,\ldots, m$$
Здесь целевая функция формируется как скалярное произведение двух векторов. Один из них — вектор искомых переменных $$x_i$$. Компонентами другого вектора являются целевые коэффициенты $$с_i$$. Условия задачи можно сформулировать так: "Расход $$r_j$$ не должен превышать имеющиеся ресурсы $$R_j$$". Вектор расхода $$r_j$$ есть сумма произведений матрицы нормированных коэффициентов $$a_{ij}$$ на вектор искомых переменных $$x_i$$.
Основной аналитический метод решения задач линейного программирования — это симплексный метод . Он сводится к вычислительной процедуре, основанной на принципе последовательного улучшения решений — перехода от одной базисной точки к другой, для которой значение целевой функции больше. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса (n-мерного тетраэдра). Симплекс-метод послужил исходным пунктом для разработки целого семейства алгоритмов решения как линейных, так и нелинейных выпуклых задач оптимизации.
Фирма производит две модели $$А$$ и $$В$$ сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели $$А$$ требуется $$3м^2$$ досок, а для модели $$В$$ — $$4м^2$$. Фирма может получать от своих поставщиков до $$1700м^2$$ досок в неделю. Для каждого изделия модели $$А$$ требуется 12 мин. машинного времени, а для изделия модели $$В$$ — 30 мин. В неделю можно использовать 160 часов машинного времени.
Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие модели $$А$$ приносит 200 руб. прибыли, а каждое изделие модели $$В$$ — 400 руб. прибыли?
В данном случае объектом является фирма, а ее деятельность представляется в виде математической модели, т.е. учитываются только некоторые количественные стороны этой деятельности. Менеджер (субъект) ставит себе задачу: составить недельный производственный план фирмы. При этом он руководствуется целью моделирования — максимальной эффективностью производства, получением максимальной прибыли.
Построение математической модели
Пусть $$x_1$$ - количество выпущенных за неделю полок модели $$А$$, а $$x_2$$ — количество выпущенных за неделю полок модели $$В$$. Тогда составим следующие соотношения:
$$3x_1$$ - количество досок, требуемых на неделю для изготовления полок модели $$А$$.
$$4x_2$$- количество досок, требуемых на неделю для изготовления полок модели $$В$$.
$$3x_1 + 4x_2$$- количество досок требуемых на неделю для изготовления книжных полок двух моделей. По условию задачи это число не должно превышать $$1700м^2$$, следовательно, получаем первое ограничение:
$$3x_1 + 4x_2 <=1700$$
Найдем ограничение на использование машинного времени.
12 мин. составляют 0,2 часа, а 30 мин. — 0,5 часа, таким образом:
$$0{,}2x_1$$ - количество времени, требуемое на неделю для обработки полок модели $$А$$;
$$0{,}5x_2$$ - количество времени, требуемое на неделю для обработки полок модели $$В$$;
$$0{,}2x_1 + 0{,}5x_2$$ - количество времени, требуемое на неделю для обработки двух моделей. По условию задачи это число не должно превышать 160 часов, следовательно, получаем второе ограничение:
$$0{,}2x_1 + 0{,}5x_2 <=160$$ или $$2x_1 + 5x_2 <=1600$$
Кроме того, поскольку $$x_1$$ и $$x_2$$ выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательными, то есть
$$x_1 >=0, x_2 >=0,$$Наша задача состоит в том, чтобы найти такие значения $$x_1$$ и $$x_2$$, при которых еженедельная прибыль будет максимальной. Составим выражение для еженедельной прибыли:
$$200x_1$$ - еженедельная прибыль, получаемая от продажи полок модели $$А$$.
$$400x_2$$ - еженедельная прибыль, получаемая от продажи полок модели $$В$$.
$$F=200x_1+400x_2$$ - еженедельная прибыль, которая должна быть максимальной.
Таким образом, имеем следующую математическую модель для данной задачи:
$$3x_1+4x_2 <=1700$$;
$$2x_1+5x_2 <=1600$$;
$$F(х_1, х_2)=200x_1+400x_2 \Rightarrow max;$$
$$x_1 >= 0,$$ $$x_2 >= 0,$$ $$x_1=\mbox{целое},$$ $$x_2=\mbox{целое}.$$
Необходимо найти значения переменных $$x_1$$ и $$x_2$$, при которых данная функция $$F$$ принимает максимальное значение, при соблюдении ограничений, накладываемых на эти переменные.
Решения, удовлетворяющие системе ограничений и требованию неотрицательности, являются допустимыми, а решения, удовлетворяющие одновременно и требованию максимизации (минимизации) целевой функции являются оптимальными.
Область допустимых решений целевой функции $$F()$$ можно найти графическим методом.
Построим прямоугольную систему координат, где по оси $$ОX$$ отложим значения $$x_1$$, а по оси $$OY$$ отложим значения $$x_2$$. Так как, согласно условию (3), $$x_1$$ и $$x_2$$ неотрицательны, то можно ограничиться рассмотрением первого квадранта (рисунок 1.2).
Рассмотрим первое ограничение:
$$3x_1+4x_2 <=1700$$
Заменим в данном ограничении знак неравенства знаком равенства и построим прямую
$$3x_1+4x_2=1700$$
Для этого найдем две точки, принадлежащие данной прямой. Пусть, например, $$x_1=0$$, $$4x_2=1700$$ или $$x_2=425$$. $$(0, 425)$$ — координаты первой точки, принадлежащей прямой.
Пусть $$x_2=0$$, то $$3x_1=1700$$, следовательно, $$x_1=567$$. $$(567, 0)$$ — координаты второй точки, принадлежащей прямой. Отметим эти точки на числовых осях.
Аналогично, для второго ограничения:
$$2x_1+5x_2 <=1600$$
$$2x_1+5x_2=1600$$
При $$x_1=0$$, $$x_2=320$$ $$(0; 320)$$
При $$x_2=0$$, $$x_1=800$$ $$(800; 0)$$
Построим данные прямые (на рисунке они соответственно обозначены (1) и (2))
Теперь найдем на чертеже такие полуплоскости, которые соответствуют неравенствам (1) и (2). Прямая (1) делит координатную плоскость на две полуплоскости. Одна полуплоскость расположена выше прямой, вторая ниже. Чтобы найти ту полуплоскость, которая соответствует неравенству (1), необходимо взять любую точку, принадлежащую одной из полуплоскостей и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой.
(рис 1.2) Графическое решение задачи о максимальной прибыли
Например, возьмем точку с координатами $$(0; 0)$$ и подставим ее координаты в неравенство (1) $$3x_1+4x_2 <=1700$$. Получается $$0 <= 1700$$ - данное неравенство является верным, следовательно, неравенству (1) удовлетворяет полуплоскость, лежащая ниже прямой (1).
Аналогично, поступим для неравенства (2) $$2x_1+5x_2 <= 1600$$. Возьмем точку с координатами $$(0; 0)$$. Получается $$0 <= 1600$$ - данное неравенство верно. Неравенству (2) удовлетворяет полуплоскость, расположенная ниже прямой (2). Стрелки на каждой границе показывают, с какой стороны прямой выполнены ограничения. Учитывая неравенства (3), получаем, что выделенный четырехугольник $$ОАВС$$ является областью, содержащей точки, для которых выполнены условия (1-3). Точки, лежащие внутри и на границе этой области, являются допустимыми решениями. Среди всех допустимых решений нужно найти оптимальное решение, при котором функция $$F$$ будет принимать максимальное значение.
Для поиска оптимального решения построим по функции $$F()$$ прямую уровня.
Возьмем произвольную точку, принадлежащую области допустимых решений — четырехугольнику $$ОАВС$$, например, точку $$M$$ с координатами $$(100; 100)$$. Подставим координаты точки $$M$$ в функцию $$F$$.
$$F(100; 100)=200*100+400*100=60000$$
Прямая уровня будет иметь следующий вид: $$2x_1+4x_2=600$$
Построим полученную прямую. Для этого необходимо найти координаты двух произвольных точек этой прямой. Одна точка у нас уже есть — это точка $$M(100; 100)$$. Найдем еще одну точку. Пусть $$x_2=0$$, тогда $$x_1=300$$. Следовательно, координаты дополнительной точки $$(300; 0)$$. Отметим полученные точки и построим прямую уровня (на рисунок 1.2 она обозначена (3)).
Значения функции $$F$$ будут возрастать по мере того, как прямая уровня удаляется от начала координат в положительном квадранте. Направление возрастания функции $$F$$ будет совпадать с вектором, координаты которого являются коэффициентами при переменных $$x_1$$ и $$x_2$$ функции $$F$$. На рисунке — это вектор $$a\{2, 4\}$$, отложенный от точки $$М$$. Обратите внимание, что вектор $$a$$, определяющий направление возрастания функции $$F$$, всегда будет перпендикулярен прямой уровня.
Максимизация целевой функции $$F$$
Для нахождения точки, в которой функция $$F$$ достигнет своего максимального значения, необходимо перемещать прямую уровня по направлению вектора $$a$$ до пересечения этой прямой с граничной точкой области допустимых решений. На нашем рисунке — это точка В.
Найдем координаты точки $$B$$. Данная точка расположена на пересечении двух прямых (1) и (2), поэтому, чтобы найти ее координаты необходимо решить следующую систему уравнений:
$$3x_1+4x_2=1700$$;
$$2x_1+5x_2=1600$$.
Легко убедиться, что оптимальное решение этой задачи задается в вершине выпуклого четырехугольника координатами
$$x_1=300$$; $$x_2=200$$.
Значит, чтобы получить максимальную прибыль $$F=200x_1+400x_2=60000+80000=140000$$ руб., фирме необходимо выпускать в неделю триста полок модели $$А$$ и двести полок модели $$В$$.
Для птицефабрики требуется составить самый дешевый рацион питания цыплят в виде смеси из корма $$А$$ и корма $$Б$$. Цыплята должны получить необходимую дозу витамина В1 — тиамина и витамина С — аскорбина при достаточной калорийности питания. Сколько надо взять граммов корма $$А$$ и корма $$Б$$ для каждой порции оптимальной смеси, чтобы удовлетворить потребность цыплят в витаминах и питательности корма?
Исходные данные для поиска решения приведены в таблице:
| Тиамин, мг | Аскорбин, мг | Калории, кал | Цена, руб. | |
|---|---|---|---|---|
| Корм А, г | 0,1 | 1 | 110 | 3,80р. |
| Корм Б, г | 0,25 | 0,25 | 120 | 4,20р. |
| Потребность | 1 | 5 | 400 |
Для наглядного представления представим условия задачи в виде ментальной карты.
$$F(X1, X2)=3{,}80*Х1+4{,}20*Х2\Rightarrow MIN$$
Оптимальному решению отвечает минимум
$$0{,}10 X1+0{,}25 X2 >=1$$ потребление тиамина не менее нормы;
$$1{,}00 X1+0{,}25 X2 >=5$$ потребление аскорбина не менее нормы;
$$110 X1+120 X2 >=400$$ калорийность питания не должна быть ниже нормы;
$$X1 >=0, X2 >=0$$ переменные $$Х1$$ и $$Х2$$ не могут быть отрицательными.
Так как в данной задаче только две переменные, то вначале определим решение графически. В декартовой системе координат $$Х1$$, $$Х2$$ построим прямые, соответствующие условиям (1), (2), (3).
$$0{,}10 X1+0{,}25 X2=1$$;
$$1{,}00 X1+0{,}25 X2=5$$;
$$110 X1+120 X2=400$$.
В соответствии с ограничением (4) мы должны рассматривать только область первого квадранта. Подставляя в условия (1) – (3)
значения начала координат $$(0,0)$$, находим, что
Результаты графического решения:
При застройке нового микрорайона требуется определить месторасположение нового торгового центра. Для обеспечения удобства всех жителей микрорайона необходимо так расположить торговый центр, чтобы суммарное расстояние переходов от него до жилых массивов было бы минимальным, а расстояние от каждого жилого массива до торгового центра не превышало бы 5. Координаты жилых массивов приведены в таблице 1.
| Координаты жилых массивов | ||
|---|---|---|
| X | Y | |
| Жилой массив 1 | 2 | 8 |
| Жилой массив 2 | 10 | 9 |
| Жилой массив 3 | 5 | 2 |
| Жилой массив 4 | 11 | 9 |
На рисунок 1.4 представлена наглядная схема расположения жилых массивов (1), (2), (3), (4). Между ними должен быть размещен торговый центр ТЦ с координатами $$Х_0$$, $$Y_0$$.
(рис 1.4) — Схема расположения жилых массивов
На рисунке показано, как вычисляют расстояния $$L_3$$ между жилым массивом (3) и торговым центром: $$L_3$$ является гипотенузой треугольника с катетами $$(X_0-X_3)$$ и $$(Y_0-Y_3)$$. Аналогичным образом определяются и другие расстояния.
| Формула | Назначение | Примечание |
|---|---|---|
| $$\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}$$ | Расстояние между жилым массивом $$i$$ и торговым центром | $$X_0$$, $$Y_0$$ — координаты торгового центра, $$x_i$$, $$y_i$$ — координаты жилых массивов $$(i=1,2,3,4)$$ |
| $$\sum_{i=1}^n\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}$$ | Суммарное расстояние между жилыми массивами и торговым центром | $$n$$ — количество жилых массивов $$(n=4)$$ |
| $$\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}\Rightarrow min$$ | Суммарное расстояние между жилыми массивами и торговым центром должно быть минимальным |
Построим прямоугольную систему координат, где по оси $$ОX$$ отложим значения $$X_0$$, а по оси $$OY$$ отложим значения $$Y_0$$. Значения $$x_1$$ и $$x_2$$ неотрицательны, поэтому можно ограничиться рассмотрением первого квадранта. Из условий задачи и рисунка 1.4 следует, что $$X_0$$ находится в интервале 2 – 11, а $$Y_0$$ не выходит из интервала 2 – 9.
Из формулы расстояния между жилым массивом $$i$$ и торговым центром выразим явным образом зависимость $$Y_0$$ от $$X_0$$:
$$\sqrt{(X_0-x_i)^2+(Y_0-y_i)^2}\le 5$$
$$(Y_0-y_i)^2\le 25-(X_0-x_i)^2$$
$$Y_0\le y_i\pm \sqrt{25-(X_0-x_i)^2} $$
Знак + перед корнем берется для $$i=3$$, в остальных случаях выбираем знак (-).
По последней формуле построим графики зависимости координат торгового центра от координат жилых массивов (1), (2), (3), (4). Они показаны на рисунок 1.5.
(рис 1.5) Нахождение решения нелинейной задачи
Каждая из кривых делит координатную плоскость на две части. Одна часть расположена выше прямой, вторая ниже. Чтобы найти ту полуплоскость, которая соответствует неравенствам, необходимо взять любую точку, принадлежащую одной из полуплоскостей (например, точку 7,4) и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой. Эти полуплоскости выделены штриховкой у каждой кривой.
Областью допустимых решений является замкнутый криволинейный треугольник $$АВС$$. Координаты торгового центра, выбранные в этом треугольнике,
удовлетворяют заданным неравенствам.
| Уравнения | $$X_0$$ | $$Y_0$$ | |
|---|---|---|---|
| $$А (3,4)$$ | $$Y_0=2+\sqrt{25-(X_0-5)^2}$$ $$Y_0=9-\sqrt{25-(X_0-11)^2}$$ | 6,53 | 6,76 |
| $$В (1,3)$$ | $$Y_0=8-\sqrt{25-(X_0-2)^2}$$ $$Y_0=2+\sqrt{25-(X_0-5)^2}$$ | 6,82 | 6,66 |
| $$С (1,4)$$ | $$Y_0=8-\sqrt{25(X_0-2)^2}$$ $$Y_0=9-\sqrt{25-(X_0-11)^2}$$ | 6,73 | 6,39 |
Вычисляя теперь расстояния от жилых массивов до торгового центра, легко проверить, что
Из приведенных примеров видно, что областью допустимых решений линейных задач оптимизации является выпуклый многоугольник,
в одной из вершин которого находится
Эффективные средства
В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel "Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:
Параметры задач ограничиваются такими предельными показателями:
Алгоритм поиска оптимальных решений включает в себя несколько этапов:
Последовательность необходимых подготовительных работ, выполняемых при решении задач экономико-математического моделирования с помощью MS Excel, приведена на блок-схеме рисунка 1.6.
(рис 1.6) Схема подготовительных работ
Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы требуют творчества — и разными людьми они могут быть выполнены по-разному. Кратко поясним сущность формулировок пунктов плана.
область переменных $$x_i$$;
область исходных нормированных коэффициентов $$a_{ij}$$;
область целевых коэффициентов $$c_i$$;
область задания
область
При постановке задачи известны целевые коэффициенты $$c_i$$ и нормированные коэффициенты $$a_ij$$ $$(i=1,2,\ldots, n; j=1,2,\ldots, m)$$. В предыдущем примере коэффициентами, формирующими целевую функцию, служили значения нормированной прибыли на одну полку типа $$А$$ ($$с_1=200\mbox{руб.}$$) и одну полку типа $$В$$ ($$с_2=400\mbox{руб.}$$). Нормированными коэффициентами $$a_{ij}$$ служили нормы расхода материала и машинного времени на одну полку каждого типа. Матрица $$a_{ij}$$ имела следующий вид:
$$a_{ij} = \left( \begin{array}{cc} 3м^2 4м^2 \\ 12 мин. 30 мин. \end{array} \right) $$
Кроме того, всегда известны значения
Таким образом, в диалоговом окне оптимизационной программы "Поиск решения" мы должны задать следующий целевой алгоритм:
$$F=\sum c_i x_i\Rightarrow max$$ - целевая функция равна произведению вектора искомых значений переменных $$x_i$$ на вектор целевых коэффициентов $$c_i$$
$$r_j=\sum a_{ij} x_i <=R_j$$ - нормированных коэффициентов
$$a_{ij}$$ на вектор искомых значений переменных $$x_i$$ не должен превышать значения заданного вектора
$$d_i=< x_i <=D_i$$ - значения переменной $$x_i$$ должны находиться в заданных пределах $$d_i\div D_i$$ число исходных элементов системы
$$i=1,2,\ldots,n$$ - число исходных элементов системы
$$j=1,2,\ldots,m$$ - число заданных видов
Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):
(рис 1.7) Схема отладки и анализа решения
При отладке рекомендуется возвращаться к заданию новых начальных условий:
Программа выдает
Анализ
Экономический анализ ставит перед собой следующие цели [2]:
Возможные методы анализа представлены в схеме на рисунке 1.8.
(рис 1.8) Виды анализа решения
После получения оптимального решения проводится его анализ по полученным отчетам. Анализ устойчивости — изучение влияния изменений отдельно взятых параметров модели на показатели оптимального решения. Анализ пределов — анализ допустимых изменений в оптимальном плане, при котором план остается оптимальным.
Учитывая ответственность принятия экономического управленческого решения, руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:
Анализ с целью ответа на первый вопрос называется вариантным анализом; анализ с целью ответа на второй вопрос называется решениями по заказу.
Вариантный анализ бывает следующих видов:
После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Математическая модель — приближенное описание объекта, выраженное с помощью математической символики, отражающее количественные соотношения между его элементами.
Симплекс-метод — вычислительная процедура, основанная на принципе последовательного улучшения решений.
Целевая функция — функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.
Матрица нормированных коэффициентов — постоянные параметры объекта моделирования.
Ресурс— количественная мера возможности выполнения какой-либо деятельности; условия, позволяющие с помощью определённых преобразований получить желаемый результат.
Область допустимых решений — все решения, которые удовлетворяют заданным ограничениям задачи.
Оптимальное решение — допустимое решение, для которого значение целевой функции максимально.
Анализ решения — заключительный этап математического моделирования экономических процессов.
Графическое решение задач оптимизации удобно применять в случае двух искомых переменных. Тогда за декартовые координаты $$X$$ и $$Y$$ принимают значения этих переменных. Если по физическому смыслу переменные могут быть только положительными, то решение ищется только в первом квадранте. Линейные ограничения на заданные ресурсы выражаются в виде прямых линий. Эти линии вместе с осями координат ограничивают область допустимых решений в виде выпуклого многоугольника. Оптимальное решение с экстремумом целевой функции находится в одной из вершин многоугольника. Координаты этой вершины являются искомыми значениями переменных.
В качестве упражнения предлагается решить графически следующую задачу по планированию работы зверофермы:
На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество кормов каждого вида, которое должны получать животные, приведено в таблице. В ней также указаны общее количество корма каждого вида, которое может быть использовано зверофермой ежедневно, и прибыль от реализации одной шкурки лисицы и песца. Определить, сколько лисиц и песцов можно вырастить при имеющихся запасах корма.
| Вид корма | Количество единиц корма, которое ежедневно должны получать | Запас корма | |
|---|---|---|---|
| лисица | песец | ||
| $$А$$ | 2 | 2 | 180 |
| $$Б$$ | 4 | 1 | 240 |
| $$В$$ | 6 | 7 | 426 |
| Прибыль от реализации одной шкурки, руб. | 1600 | 1200 | |
Попробуйте найти решение самостоятельно, а затем сравните его с приведенным ниже.
Пусть $$x_1$$ — количество лисиц, а $$x_2$$ — количество песцов, которые еще можно содержать при имеющихся материальных
Построим прямоугольную систему координат, где по оси $$ОX$$ отложим значения $$x_1$$, а по оси $$OY$$ отложим значения $$x_2$$. Значения $$x_1$$ и $$x_2$$ неотрицательны, поэтому можно ограничиться рассмотрением первого квадранта (рисунок 1.9).
Рассмотрим последовательно все ограничения по
$$2x_1+2x_2 <=180$$ — расход корма $$А$$ не может превышать его запасы.
Заменим в данном ограничении знак неравенства знаком равенства:
$$2x_1+2x_2=180$$ или
$$x_1+x_2=90$$
Построим прямую (1) на графике рисунке 1.9.
Аналогично, для второго и третьего ограничений:
$$4x_1+x_2 <=240$$ — расход корма $$Б$$ не может превышать его запасы.
$$6x_1+7x_2 <=426$$ — расход корма $$В$$ не может превышать его запасы.
Построим ограничительные прямые (2) и (3) по уравнениям:
$$4x_1+x_2=240$$;
$$6x_1+7x_2=426$$.
(рис 1.9) Нахождение оптимального решения
Каждая из прямых (1), (2), (3) делит координатную плоскость на две полуплоскости. Одна полуплоскость расположена выше прямой, вторая ниже.
Чтобы найти ту полуплоскость, которая соответствует неравенствам, необходимо взять любую точку, принадлежащую одной из полуплоскостей
(например, точку 0,0) и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой.
При подкормке посевов необходимо внести на 0,01 га почвы не менее 8 единиц азота, не менее 24 единиц фосфора и не менее 16 единиц калия. Фермер закупает комбинированные удобрения двух видов "Азофоска" и "Комплекс". В таблице указаны содержание количества единиц химического вещества в 1 кг каждого вида удобрений и цена 1 кг удобрений. Определить графически потребность фермера в удобрениях того и другого вида на 0,01 га посевной площади при минимальных затратах на потребление.
| Химические вещества | Содержание химических веществ в 1 кг удобрения | |
|---|---|---|
| Азофоска | Комплекс | |
| Азот | 1 | 2 |
| Фосфор | 12 | 3 |
| Калий | 4 | 4 |
| Цена 1 кг удобрения, руб. | 50 | 20 |
Ответ: для подкормки требуется на каждые 0,01 га закупить 1,14 кг "Азофоски" и 3,43 кг удобрения "Комплекс" на сумму 125, 71 руб. Внесение удобрений будет соответствовать такому графику:
Полной даме необходимо похудеть, а за помощью она обратилась к подруге. Подруга посоветовала перейти на рациональное питание, состоящее из двух продуктов P и Q.
Суточное питание этими продуктами должно давать менее 14 единиц жира (чтобы похудеть), но не менее 300 килокалорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 килокалорий, а на упаковке с продуктом Q — 4 единицы жира и 200 килокалорий соответственно. При этом цена продукта Р равна 250 руб./кг, а цена продукта Q равна 210 руб./кг.
Так как дама была стеснена в средствах, то ее интересовал вопрос: в какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?
Составьте ментальную карту по условиям задачи.
Решите задачу графически. Определите
Ответ: даме необходимо потреблять за сутки 0,00 кг продукта Р и 1,50 кг продукта Q, всего на сумму 315,00 руб.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.