Использование линейного программирования для решения задач оптимизации

Оптимизация как раздел математики существует достаточно давно и обозначает выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточнённое решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.

Реальные прикладные задачи оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.

Таким образом целью данной курсовой работы является : освоить навыки использования линейного программирования для решения задач оптимизации. Для этого были поставлены следующие задачи :

1)Изучить теоретические сведения, необходимые для решения задач оптимизации методом линейного программирования.

2)Изучить методы решения задач линейного программирования.

3)Решить поставленные задачи, используя рассмотренные методы линейного программирования.

I. Теоретический раздел

1.1 Понятие о линейном программировании. Формулировка задачи линейного программирования

Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования.

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для

решения линейных задач оптимизации.

Формулировка задачи линейного программирования

Нужно максимизировать

$f(x)= \sum_{j=1}^n c_j x_j=c_1x_1+c_2x_2+\dots+c_nx_n$

при условиях

$\sum_{j=1}^n a_{ij}x_j \le b_i$

при i = 1, 2, 3, . . ., m..

Иногда на x_i также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют "основной" или "стандартной" в линейном программировании.

1.2 Виды задач линейного программирования

Поток и паросочетание

Рассмотрим задачу о максимальном паросочетании: есть несколько юношей и девушек; для каждой пары известно, любят ли они друг друга. Нужно поженить максимальное число пар. Введем переменные x_ij — они соответствуют паре из i-того юноши и j-той девушки. Введем ограничения: x_ij≥ 0, x_ij≤ 1, $x_{1i}+x_{2i}+\dots+x_{ni}\le 1$ , $x_{i1}+x_{i2}+\dots+x_{im}\le 1$ , $f=x_{11}+x_{12}+\dots+x_{nm}$ . Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Вторая важная задача — максимальный поток. Пусть имеется граф (с ориентированными ребрами), в котором для каждого ребра указана его пропускная способность. И заданы 2 вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из стока в исток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Возьмем в качестве переменных x_i — количество жидкости, протекающих через i-тое ребро. Тогда $x_i\ge 0$ , $x_i\le c_i$ , где c_i — пропускная способность i-того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции f естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к 2 задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение $f(x)\ge m$ , где m — величина максимального потока, и решить задачу с новой функцией f(x) — стоимостью потока.

Все эти задачи могут быть решены быстрее, чем с помощью общих алгоритмов решения задач линейного программирования, за счет особой структуры уравнений и неравенств.

Транспортная задача

Имеется некий однородный груз, который нужно перевести с n складов на m заводов. Для каждого склада i известно, сколько в нем находится груза a_i, а для каждого завода известна его потребность b_j в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния c_ij от i-го склада до j-го завода известны). Требуется составить наиболее дешевый план перевозки. Решающими переменными в данном случае являются x_ij — количества груза, перевезенного из i-го склада на j-й завод.

Ограничениями будут $x_{i1}+x_{i2}+\dots+x_{im}\le a_i$ и

$x_{1j}+x_{2j}+\dots+x_{nj}\ge b_j$ .

Целевая функция имеет вид: $f(x)=x_{11}c_{11}+x_{12}c_{12}+\dots+x_{nm}c_{nm}$ , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица A размера $n\times m$ . Первый игрок выбирает число от 1 до n, второй — от 1 до m. Затем они сверяют числа и первый игрок получает a_ij очков, а второй ( − a_ij) очков (i — число, выбранное первым игроком, j — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число i нужно выбирать с вероятностью p_i. Тогда оптимальная стратегия является решением следующей задачи линейного программирования: $p_i\ge 0$ , $p_i\le 1$ , $p_1+\dots+p_n=1$ , $a_{1i}p_1+a_{2i}p_2+\dots+a_{ni}p_n\ge c$ ( $i=1,\dots,m$ ), в которой нужно максимизировать функцию $f(p_1,\dots,p_n,c)=c$ . c в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

1.3 Методы решения задач линейного программирования

Симплекс-метод

Сведём задачу линейного программирования к просмотру крайних точек допустимого множества. Именно направленный перебор крайних точек допустимого множества и осуществляется в симплекс-методе, изложенном ниже.

Рассмотрим связь между геометрическим понятием крайней точки и его аналитической интерпретацией. Для ограниченного множества $X$ , описанного с помощью системы неравенств

$\begin{displaymath}a^ix \leq b_i, i = 1,2,\ldots,m \end{displaymath}$

крайними точками являются решения невырожденных подсистем вида:

$\begin{displaymath}a^ix = b_i, i \in S \quad a^ix < b_i, i \notin S, \end{displaymath}$

(1)

где $S$ - некоторое подмножество индексов

$1,2,\ldots,\vert S \vert \geq n$

$\begin{displaymath}\vert S \vert = \mbox{dim}\,x = n \leq m \end{displaymath}$

и матрица, составленная из строк-векторов аⁱ, неособенная.

Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют $x' \in X$ и $x'' \in X$ такие, что для $0 < \lambda < 1$ $\begin{displaymath}x = \lambda x' + (1 - \lambda)x''. \end{displaymath}$ Поскольку для

$\begin{displaymath}a^ix' = a^ix'' = 0 = \lambda a^ix' + (1 - \lambda)a^ix'', \end{displaymath}$

то, очевидно, $a^ix' = a^ix'' = 0$ . В силу единственности решения (3) $x' = x'' = x$ .

С другой стороны, если $x$ -- крайняя точка, то можно обозначить через $S$ множество равенств

$\begin{displaymath}i \in S \Leftrightarrow a^ix = 0.\end{displaymath}$

Обозначим через $A_S$ матрицу, составленную из строк $a^i, i \in S.$ Если предположить, что $\mid S \mid < n$ , то существует нетривиальное нуль-пространство

$\begin{displaymath}\lbrace z:A_Sz = 0 \rbrace.\end{displaymath}$ 2)

Выбирая $z$ достаточно малым по норме, можно добиться того, что для $x \in X$ вектор $x' = x + z \in X$ или $\begin{displaymath}a^ix' = a^ix = 0 + 0 = 0 \end{displaymath}$

для $i \in S$ и $\begin{displaymath}a^ix' = a^ix + a^ix + a^iz \geq a^ix -\Vert a^i \Vert \Vert z \Vert \geq \delta/2 > 0\end{displaymath}$

для достаточно малых $\Vert z\Vert$ . Аналогично можно показать, что при этом и $x'' = x - z \in X$ . Так как $\begin{displaymath}x = \frac{1}{2}(x + z) + \frac{1}{2}(x - z), \end{displaymath}$ то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x₁, x₂, . . ., x_n на базисные $x^B_i > 0$ и небазисные $x^N_j$ . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (x^B, x^N ).

Система ограничений канонической формы задачи линейного программирования может быть соответственно переписана в виде:

$\begin{displaymath}Ax = A_Bx^B + A_Nx^B = b.\end{displaymath}$ (3)

Предположим, что матрица $A_B$ имеет полный ранг, т.е. $A_B$ - невырожденная. Тогда из равенства (5) следует

$\begin{displaymath}x^B = (A_B)^{-1}b.\end{displaymath}$ 4)

Целевая функция задачи ЛПР также может быть разбита на базисную и не базисную части:

$\begin{displaymath}cx = c_Bx^B + c_Nx^N.\end{displaymath}$

Подстановка (6) дает

$\begin{displaymath}cx = (c_N + c_B(A_B)^{-1}A_N) = d^Nx^N.\end{displaymath}$ 5)

Предположим, что мы находимся в некоторой начальной точке $x^0 = (x^B_0,0)$ со значением целевой функции

$\begin{displaymath}cx^0 = c_B(A_B)^{-1}b.\end{displaymath}$

Каким образом можно уменьшить далее значение целевой функции? Из соотношения (5) следует, что для этого достаточно сделать положительными те компоненты вектора $x^N$ , которым соответствуют отрицательные значения координат вектора модифицированных стоимостей

$\begin{displaymath}d^N =c_N + c_B(A_B)^{-1}A^N, \end{displaymath}$

сохраняя при этом неотрицательность базисных переменных $x^B$ .

Увеличение $x^N$ может быть проделано различным образом, и за время существования симплекс-метода были проделаны многочисленные эксперименты по поиску наиболее эффективных стратегий увеличения $x^N.$

Здесь будет рассмотрена простейшая:

· среди компонент вектора $d^N = (_i, i \in N)$ находится минимальная;

· соответствующая небазисная переменная $x^N_i$ получает максимально возможное приращение, сохраняющее неотрицательность базисных переменных.

Поскольку при увеличении $i$ -й компоненты вектор $x^N$ приобретает вид:

$\begin{displaymath}x^N = \lambda e^i, \end{displaymath}$

где $e^i$ это $i$ -й орт, а $\lambda$ -- степень увеличения этой переменной или шаг алгоритма, то модифицированный базисный вектор выражается следующим образом:

$\begin{displaymath}x^B = (A_B)^{-1}b - \lambda(A_B)_{-1}A^Ne^i \equiv \beta - \lambda \alpha,\end{displaymath}$

где $\alpha$ - $i$ -й столбец матрицы $(A_B){-1}A^N.$ Шаг $\lambda$ определяется при этом из условия:

$\begin{displaymath}\beta - \lambda \alpha \geq 0.\end{displaymath}$

Максимально возможное значение $\lambda$ определится при этом как

$\begin{displaymath}\lambda = \min_{\alpha_i > 0} \frac{\beta_i}{\alpha_i}.\end{displaymath}$ 6)

Пусть $k$ -- номер $i$ , на которой достигается минимум (6). Очевидно, что при этом

$\begin{displaymath}x^B_k = \beta_k - \lambda \alpha_k = 0.\end{displaymath}$

При этом говорят, что переменная $x^B_k$ выводится из базиса (обращается в нуль), а переменная $x^N_i$ вводится в базис. Целевая функция при этом уменьшается на величину

$\begin{displaymath}\delta cx = \lambda d^N_i.\end{displaymath}$

Важную роль в теории симплекс-метода играет условие невырожденности, в котором предполагается полный ранг A_Bи строгая положительность базисного решения β. При этом λ > 0 и δcx < 0, то есть целевая функция уменьшается при переходе к новому базису.

Поскольку в задаче линейного программрования может быть лишь конечное число базисов, а на каждой итерации происходит уменьшение целевой функции, базисы не могут повторяться. Следовательно, после конечного числа итераций вектор модифицированных стоимостей станет неотрицательным, а это означает, что дальнейшее уменьшение целевой функции невозможно, т.е. будет получено одно из оптимальных решений.

В силу выпуклости задачи любое другое оптимальное решение будет иметь также значение целевой функции, т.е. будет в этом смысле эквивалентно.

Геометрический метод

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

c₁x₁+c₂x₂= а (1)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

Предположим надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имеющая наибольшую широту, т. е. точка через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).

Именно так и надо поступать при геометрическом решении задач линейного программирования . на многоугольнике решений следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c₁и c₂и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели ”, расположенные обычно под углом к осям координат.

Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении линии в другую сторону – только убывает.

Пусть имеются три линии уровня :

F=c₁x₁+ c₂x₂= а₁(I)

F=c₁x₁+ c₂x₂ = а₂ (II)

F=c₁x₁+ c₂x₂ = а₃(III)

Причём линия II заключена между линиями I и III. Тогда а₁ < а₂< а_{3 и}а₁ > а₂>а_3.

В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c₁x₁+ c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).

II. Практический раздел

2.1 Решение транспортной задачи

Имеются два склада с сырьём. Ежедневно вывозится с первого склада 60 т сырья, со второго – 80 т. сырьё используется двумя заводами, причём первый завод получает – 50 т, а второй – 90 т. нужно организовать оптимальную (наиболее дешёвую) схему перевозок, если известно, что доставка 1 т сырья с первого склада на первый завод стоит 7 рублей, с первого склада на второй завод – 9 рублей, со второго склада на первый завод – 10 рублей, со второго склада на второй завод – 8 рублей.

Решение:

Обозначим через х₁,х₂ количество сырья, который нужно доставить с первой базы соответственно на первый, второй заводы, а через х₃, хколичество сырья, который нужно доставить со второй базы соответственно на первый, второй заводы. Составим выражения, которые в соответствии с исходными данными должны удовлетворять следующим условиям:

х₁ +х₂= 60;

х₃+ х₄= 80;(1)

х₁+х₃= 50;

х₂+х₄= 90.

Первое и второе уравнения описывают количество сырья, которое необходимо вывезти с первого и второго складов, а третье и четвёртое – сколько нужно завести сырья на первый и второй заводы. К данной системе уравнений нужно добавить систему неравенств:

х_i ≥ 0, где i = 1, . ., 4, (2)

которая означает, что сырьё обратно с заводов на склады не вывозится. Тогда общая стоимость перевозок с учётом приведённых в таблице расценок выразится формулой :

f = 7х₁ + 9х₂+ 10х₃+ 8х_4.(3)

Таким образом, мы пришли к типичной задаче линейного программирования : найти оптимальные значения проектных параметров х_i(i = 1, . ., 4), удовлетворяющим условиям (2), (3) и минимизирующим стоимость перевозок (3).

Из анализа системы уравнений (1) следует, что только первые два уравнения являются независимыми, а последние можно получить из них. Поэтому фактически имеем систему :

х₁ +х₂= 60;

х₃+ х₄= 80;(4)

х₃= 50 - х₁;

х₄= 90 - х₂.

Поскольку в соответствии с (2) все проектные параметры должны быть неотрицательны, то с учётом (4) получим следующую систему неравенств:

х₁≥ 0, х₂≥ 0, 50 - х₁≥ 0, 90 - х₂≥ 0.

Эти неравенства можно записать в более компактном виде :

0≤ х₁≤ 50, 0≤ х₂≤ 90. (5)

Данная система неравенств описывает все допустимые решения рассматриваемой задачи. Среди всех допустимых значений свободных параметров х₁и х₂нужно найти оптимальные, минимизирующие целевую функцию f. Формула (3) для неё с учётом соотношений (4) принимает вид

f = 7х₁ + 9х₂+ 10(50 - х₁)+ 8(90 - х₂);

f = -3х₁ + х₂+ 1220.

Отсюда следует, что стоимость перевозок уменьшается с увеличением значений х₁; поэтому нужно взять его наибольшее допустимое значение. В соответствии с (5) х₁= 50, тогда получим, что х₂ = 60 - х₁= 10. Тогда оптимальные значения остальных параметров можно найти по формулам (4):

х₃= 50 - х₁=50 – 50 = 0, х₄= 90 - х₂= 90 – 10 = 80.

В этом случае минимальная общая стоимость перевозок равна :

f = 7*50 + 9*10+ 10*0+ 8*80 = 350 + 90 + 0 + 640 = 1080.

То есть, минимальная общая стоимость перевозок f = 1080.

Покажем на рисунке схему доставки сырья на заводы. (Числа указывают количество сырья в тоннах).

2.2 Решение производственной задачи

Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

Вид сырья	Нормы расхода сырья на одно изделие, кг A B	Общее количество сырья, кг
I	2 4	300
II	4 4	120
III	1 2	252
Прибыль от реализации одного изделия, ден. ед.	30 40

Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем изделия А.

Решение.

Обозначим через х₁ и х₂количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х₁ +4х₂) единиц ресурса I, (4х₁ +4х₂) единиц ресурса II, (3х₁ +12х₂) единиц ресурса III. Так кА потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

12х₁ +4х₂≤ 300; 3х₁ + х₂≤ 75;

4х₁ +4х₂≤ 120; или х₁ + х₂≤ 30; (6)

3х₁ +12х₂≤ 252. х₁ +4х₂≤ 84.

По смыслу задачи переменные х₁≥ 0, х₂≥ 0. (7)

Суммарная прибыль А составит 30х₁от реализации продукции А и 40х₂от реализации продукции В, то есть : F = 30х₁ +40х₂(8)

Далее будем решать задачу двумя методами:

1способ – симплексный метод

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком « + », так как все неравенства имеют вид « ≤ ».

Получим систему ограничений в виде :

3₁ +х₂+х₃ ≤ 75;

х₁ +х₂+ х₄ ≤ 30; (9)

х₁ + 4х₂+ х₅ ≤ 84.

Для нахождения первоначального базисного решения разобьём переменные на две группы – основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные переменные: х₃, х₄, х_5.

Не основные переменные: х₁, х_{2. .}

Выразим основные переменные через не основные :

х₃= 75 - 3х₁- х₂;

х₄= 30 х₁- х₂; (10)

х₅= 84 - х₁- 4х_2.

Положив основные переменные равными нулю, то есть х₁= 0, х₂= 0, получим базисное решение Х₁ = (0, 0, 75, 30, 84), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные:

F = 30х₁+ 40х_{2 .}

При решении Х₁значение функции равно F(Х₁). Легко понять, что функцию F можно увеличить за счёт увеличения любой из не основных переменных, входящих в выражение F с положительным коэффициентом. Это можно осуществить, перейдя к новому базисному решению, в котором эта переменная будет не основной, то есть принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдёт в не основные. В данном примере для увеличения F можно переводить в основные любую переменную, так как и х₁ и х₂входят в выражение для F со знаком «+». Для определённости будем выбирать переменную, имеющую больший коэффициент, то есть х₂. Система (10) накладывает ограничения на рост переменной х₂. Поскольку необходимо сохранять допустимость решений, то есть все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁= 0 как не основная переменная):

х₃= 75 - х₂≥ 0; х₂≤ 75;

х₄= 30 - х₂≥ 0; откуда х₂≤ 30;

х₅= 84 - 4х₂≥ 0; х₂≤ 84.

Каждое уравнение системы, определяет оценочное отношение – границу роста переменной х_2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной свободного члена к коэффициенту при х₂при условии, что эти числа имеют разные знаки.

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушается ни одна из полученных границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ = min {75, 30, 84/4} = 84/4 = 21. При х₂= 21 переменная х = 0 и переходит в не основные.

Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (то есть, где оценка минимальна), называется разрешающим. В данном случае – это третье уравнение.

II шаг.

Основные переменные: х₂, х₃, х_4.

Не основные переменные: х₁, х_{. .}

Выразим основные переменные через новые не основные, начиная с разрешающего уравнения(его используем для записи выражения для х₂ ) :

х₂= (84 - х₁- х₅)/4;

х₃= 75 - 3х₁- 84/4 + х₁/4 + х₅/4;

х₄= 30 - х₁- 84/4 + х₁/4 + х₅/4;

или

х₂=21 0,25 х₁- 0,25х₅;

х=54 - 2,75х₁+ 0,25х₅;

х=9 - 0,75х₁ + 0,25х₅.

Второе базисное решение Х₂= (0, 21, 54, 9, 0 ) является допустимым.

Выразив линейную функцию через не основные переменные на этом шаге, получаем:

F = 30х₁+ 40 (84 - х₁- х₅)/4 = 840 + 20х₁- 10х₅

Значение линейной функции F₂ = F(X₂) = 840.

Поскольку необходимо сохранять допустимость решений, то должны выполняться следующие неравенства(при этом х₁= 0 как не основная переменная):

х₂=21 - 0,25х₅≥ 0; х₅≤ 84;

х₃=54+ 0,25х₅≥ 0; откуда х₅≤ -216; (11)

х₄=9 + 0,25х₅≥ 0. х₅ ≤ -36 .

Обнаруживаем возможность дальнейшего увеличения линейной функции за счёт переменной х_1, входящей в выражение для F с положительным коэффициентом. Система уравнений (11) определяет наибольшее возможное значение для х₅:

Х₅= min {84, -216,-36} = -36 .

При х₅= -36 х₄= 0 переходит в неосновные переменные.

Разрешающим будет третье уравнение.

III шаг.

Основные переменные : х₁, х₂, х_3.

Неосновные переменные : х₄, х_5.

Выразим основные переменные через неосновные:

х₁= 12– 4/3х₄ + 1/3х₅;

х₂= 18 + 1/3х₄- 1/3х₅;

х₃= 21 + 11/3х₄- 11/3х_5.

Третье базисное решение Х₃= (12, 18, 21, 0, 0) является допустимым.

Выразим линейную функцию через неосновные переменные:

F = 30(12– 4/3х₄ + 1/3х₅)+ 40(18 + 1/3х₄- 1/3х₅) = 1080 – 80/3х₄- 10/3х_5.

Значение линейной функции F₃ = F(X₃) = 1080.

Это выражение не содержит положительных коэффициентов при не основных переменных, поэтому значение F₃ = F(X₃) = 1080 максимальное. Функцию F невозможно ещё увеличить, переходя к другому допустимому базисному решению, то есть решение X₃– оптимальное. Вспоминая экономический смысл всех переменных можно сделать выводы.

Прибыль предприятия принимает максимальное значение 1080 ден. ед. при реализации 12 единиц продукции Р₁(Х₁=12) и Р₂(Х₂=18). Дополнительные переменные х₃, х₄, х_5.

показывают разницу между запасами ресурсов каждого вида и их потреблением, то есть остатки ресурсов. При оптимальном плане производства х₄ = х₅ = 0, остатки ресурсов S₂ и S₃равны нулю, а остатки ресурсов S₁= 21.

Ответ: максимальная прибыль от реализации продукции равна 1080 ден. ед.

2 способ – геометрический метод

Геометрический метод решения задач оптимизации сводится к нахождению оптимального решения задачи в одной из угловых точек многоугольника(рис. 1) для

линейной функции F = 30х₁+ 40х₂→max при следующих ограничениях:

3х₁ + х₂≤ 75, (I)

х₁ + х₂≤ 30, (II) (12)

х₁ +4х₂≤ 84, (III), х₁≥ 0, х₂≥ 0, х₂≥ х₁

по смыслу задачи.

Изобразим многоугольник решений данной задачи.

Подобные работы:

Использование математических методов и моделей в управлении микроэкономическими системами

Использование методов линейного программирования и экономического моделирования в технологических процессах

Использование рабочего времени

Использование эвристических и экономико-математических методов при решении задач управления

Использование электронных таблиц MS EXCEL для решения экономических задач. Финансовый анализ в Excel

Актуально: