Решение задачи линейного программирования симплекс-методом

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Постановка задач

Задание на курсовую работу

Необходимо составить диету (в соответствии с вариантом), содержащую, по крайней мере, 20 + 16 единиц белков, 30 + 16 единиц углеводов, 10 + 16 единиц жиров и 40 + 16 единиц витаминов, где 16 - номер варианта. Как дешевле всего достичь этого при указанных в таблицах ценах на 1 кг (или на 1 л) пяти имеющихся продуктов?

Таблица 1.1

	Хлеб	Соя	Сушеная рыба	Фрукты	Молоко
Белки Углеводы Жиры витамины	2 12 1 2	12 0 8 2	10 0 3 4	1 4 0 6	2 3 4 2
Цена	12	36	32	18	10

Описание метода симплекс-метод

· Ввести размерность задачи. Ввести коэффициенты в канонической форме, базисные переменные и задать небазисные переменные.

Найти наименьший из коэффициентов .

Пусть это коэффициент . Если , то конец, оптимум найден. Иначе: , и переменная X_s и прейти к 3.

· Если все , то конец.

Решение лежит вне заданных границ. Иначе вычислить для всех и найти минимум .

Пусть этот минимум равен . Тогда X_s - базисная переменная, а X_r - свободная переменная.

· Построить новую каноническую форму, изменить базис и перейти к 2.



Введение

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств. В данном случае нужно составить диету, содержащую, по крайней мере: 36 белков, 46 углеводов, 26 жиров, 56 витаминов - рассмотрено, как дешевле всего достичь при определенных ценах на 1 кг и 1 л в 5 имеющихся продуктах (а именно хлеб, соль, сушеная рыба, фрукты, молоко). Каждая из этих задач является частным случаем линейного программирования.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

· нахождение исходной вершины множества допустимых решений,

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

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

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

1. Теоретическая часть

1) Как определяется направление возрастания целевой функции в графическом методе решения задачи линейного программирования.

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.

Задача ЛП в стандартной форме записи:

Допустим n=2, т.е. необходимо рассмотреть данную задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a_i1 x₁ + a_i2 x₂ = b_i, i=1,2,… m. Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x1=0, x2 =0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Таким образом, геометрически задача линейного программирования (ЗЛП) представляет собой отыскание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений.

Линейное уравнение описывает множество точек, лежащих на одной

прямой. Линейное неравенство описывает некоторую область на плоскости.

Определим, какую часть плоскости описывает неравенство 2х₁+3х₂ 12. Во-первых, необходимо построить прямую 2х₁+3х₂=12. Эта прямая проходит через точки (6, 0) и (0, 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Удобной для использования при подстановке в неравенство является начало координат. Нужно подставить х₁=х₂=0 в неравенство 2х₁+3х₂12. Получится 20+3012. Данное утверждение является верным, следовательно, неравенству 2х₁+3х₂12 соответствует нижняя полуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на рис.

Неравенству 2х₁+3х₂12 соответствует нижняя полуплоскость

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

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям не отрицательности (x_j0, j=1,…, n). Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

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

линейный уравнение симплекс программирование

.

Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая, перпендикулярная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине «a». Меняя значение «a», и получится семейство параллельных прямых, каждая из которых является линией уровня.

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

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

Графический метод решения ЗЛП состоит из следующих этапов.

· Строится многоугольная область допустимых решений ЗЛП - ОДР,

· Строится вектор-градиент ЦФ в какой-нибудь точке Х₀принадлежащей ОДР - .

· Линия уровня C₁x₁+C₂x₂ = а (а-постоянная величина) - прямая, перпендикулярная вектору - градиенту - передвигается в направлении этого вектора в случае максимизации f(x_1,x₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x_1,x₂).

· Для нахождения ее координат достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x_1,x₂), найденное в получаемой точке, является максимальным.

При минимизации f(x_1,x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x_1,x₂) не существует.

Если линия уровня параллельна какому-либо функциональному ограничению задачи, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.

2) Дайте характеристику стандартной формы задач линейного программирования.

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

3) Приведите основные правила для преобразования задачи ЛП к стандартному виду.

Задача условной оптимизации называется задачей линейного программирования (ЛП), если целевая функция и все функции ограничений являются линейными функциями:

где . Это есть стандартная форма задачи ЛП. В общем случае ограничения могут иметь знак «» или «=». Однако, умножая неравенство на -1 и заменяя равенство двумя неравенствами «» и «», можно придти к стандартной форме. Кроме того, взяв вместо функцию - , можно получить задачу на минимум. Обозначим через - вектор коэффициентов целевой функции, - вектор свободных членов ограничений, - матрицу коэффициентов ограничений.

4) Каким соотношением задается отрезок в n-мерном пространстве.

Определение: n-мерным вектором х называется упорядоченная совокупность n действительных чисел (x1, x2,…, xn). Числа x1, x2,…, xn называются компонентами вектора х. Определение. n-мерным векторным пространством Rn называют совокупность n-мерных векторов с действительными компонентами, рассматриваемая с определенными в ней операциями сложения векторов и умножения вектора на число.

5) Дайте определение экстремальной точки.

На латинском слово extremum означает «крайнее». Оно в математике имеет два конкретных значения: maximum (сокращенно max) - наибольшее и minimum (сокращенно min) - наименьшее. В таком понимании extremum имеет более узкий смысл, чем optimum, переводимый от латинского как «наилучшее».

Пусть дана функция , где . Говорят, что в точке  достигается максимальное (минимальное) значение функции f, если выполнено неравенство для всех . Этот факт записывается следующим образом:

Точка x*, в которой достигается максимум (минимум) называется максимума (минимума) точкой функции f.

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

Как видим, имеется два вида экстремальных задач - задача на максимум и задача на минимум. Символически они записываются так:

6) Какое множество называется выпуклым?

Множество называется выпуклым, если вместе с любыми двумя своими точками целиком содержит отрезок, их соединяющий.



Выпуклое и не выпуклое множество

7) Докажите, что если ограничения имеют допустимое решение, то они имеют и базисное решение.

Определение начального допустимого базисного решения (ДБР) в общем случае представляет значительные трудности. Поэтому для поиска ДБР разработаны специальные методы.

Метод искусственных переменных. Пусть ограничения задачи ЛП имеют вид AxЈA₀.

Если все b_i і 0, i = 1, 2,…, m, то свободные векторы, образующие единичную подматрицу, составляют базис, а соответствующие им переменные - начальное базисное решение. В общем случае, когда некоторые ограничения имеют знак і, например

a_i1x₁ + a_i2x₂ + … +a_inx_nіb_i, i=1,2,…., m,

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

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n -1x_n+1 + 0x_n+2 + … +0x_n+m = b₁;

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n +0x_n+1-1x_n+2 + … +0x_n+m = b₂;

………………….

a_m1x₁ + a_mІx₂ + … + a_mnx_n + 0x_n+1 + 0x_n+2 +…-1x_n+m = b_m.



Свободные переменные {x_n+1,…, x_n+m} в этом случае уже невозможно использовать в качестве начального базиса, так как x_n+1<0,…, x_n+m<0. Поэтому в уравнения дополнительно вводят искусственные переменные x_n+m+1,…, x_n+m+k. Эти переменные не имеют ничего общего с реальной задачей,

и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>>c_i, (i = 1, 2., m).

В случае решения задач минимизаци искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Знаки искусственных переменных x_n+m+1,…, x_n+m+k должны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

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

8) Докажите, что допустимая область является выпуклым множеством.

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

Доказательство.

В стандартной форме в матричных обозначениях допустимая область G определяется условием



Пусть и принадлежит G, т.е.

Но тогда имеем

т.е. x принадлежит G и, следовательно, выпукло.

В канонической форме область G определена условиями

Пусть и принадлежат G, т.е.

.

Но тогда имеем

 

т.е. и, следовательно, G выпукло. Теорема доказана.

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

9) Дайте характеристику канонической формы задачи ЛП.

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования (КЗЛП).

В канонической форме:

· все функциональные ограничения записываются в виде равенств с неотрицательной правой частью;

· все переменные неотрицательны;

· целевая функция подлежит максимизации.

Любую ЗЛП можно привести к каноническому виду, используя следующие правила:

а) максимизация целевой функции f x() = c1x1+ … +cnxn равносильна минимизации целевой функции: f x() =-c1x1 -… - cnxn;

б) ограничение в виде неравенства, например, 3Х1 + 2Х2 - Х3 ? 6, может быть приведено к стандартной форме 3Х1 + 2Х2 - Х3 + Х4 = 6, где новая переменная Х4 неотрицательна.

Ограничение Х1 - Х2 + 3Х3 ? 10 может быть приведено к стандартной форме Х1 - Х2 + 3Х3 - Х5 = 10, где новая переменная Х5 неотрицательна;

в) если некоторая переменная Хk может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду Xk

Xk= ? ? ??, где Xk? ? 0 и Xk?? ? 0

10) Выведете основные соотношения для симплекс-метода.

Рассматривая решение задачи ЛП графическим методом отметили, что оптимальному решению всегда соответствует одна из узловых точек области допустимых решений (ОДР).

ОДР представляет собой многогранник в многомерном пространстве. Такая геометрическая фигура называется симплексом, Отсюда название симплекс-метода (СМ). СМ - это упорядоченная процедура перебора угловых точек симплекса, для отыскания точки, доставляющей экстремум целевой функции.

Координаты любой точки внутри симплекса называют планом, угловых точек симплекса - опорными планами,

Процедура СМ может быть сформулирована следующим образом:

· В качестве начального решения выбирается любая угловая точка симплекса, которая называется начальным опорным планом или начальным решением. Пусть это точка А.

· От исходной точки происходит переход с смежной (соседней) точке, значение целевой функции в которой «лучше», чем в начальной. В простейшем случае выбор производится по коэффициентам целевой функции

В задаче о краске целевая функция выглядит: Z = 3x_H+2x_Bmax.

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

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

11) Назовите основные шаги симплекс-метода.

На первом этапе находят одно из решений, удовлетворяющее системе ограничений. Системы, в которых переменных больше, чем ограничений N > m, называются неопределенными. Они приводятся к определенным системам (N = m) путем приравнивания к нулю N-m каких-либо переменных. При этом остается система m уравнений с m неизвестными, которая имеет решение, если определитель системы отличен от нуля. В симплекс-методе вводится понятие базисных переменных, или базиса. Базисом называется любой набор из m таких переменных, что определитель, составленный из коэффициентов при этих переменных в m-ограничениях, отличен от нуля. Остальные N-m переменных называются небазисными, или свободными переменными. Если принять, что все небазисные переменные равны нулю, и решать систему ограничений относительно базисных переменных, то получится базисное решение.

В системе из m уравнений с N неизвестными общее число базисных решений при N > m определяется числом сочетаний

Базисное решение, в котором все x_i0, i = 1, m, называется допустимым базисным решением. Таким образом, первый этап решения, используя симплекс-метод, завершается нахождением допустимого базисного решения, хотя бы и неудачного.

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

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

a) базисные переменные и функция цели выражаются через небазисные переменные;

b) по определенному правилу выбирается та из небазисных переменных, изменение значения которой способно улучшить значение F(x), и она вводится в базис;

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

d) базисные переменные и функция цели выражаются через новые небазисные переменные, и повторяются операции b) и c).

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

12) Приведите основные шаги двойственного симплекс-метода.

Понятие двойственности можно рассмотреть на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах единиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Через  необходимо норму расхода сырья i-го вида на единицу j-й продукции, - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи: - объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.

Математическая модель задачи:

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

Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:

· общую стоимость отходов сырья покупающая организация стремится минимизировать;

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

Эти требования формализуются в виде следующей ЗЛП.

Требование 1 покупающей организации - минимизация покупки:

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

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



По смыслу задачи оценки не должны быть отрицательными:

.

Переменны   называют двойственными оценками или объективно обусловленными оценками.

Задачи (2.23) - (2.25) и (2.26) - (2.28) называют парой взаимно двойственных ЗЛП.

Между прямой и двойственной задачами можно установить следующую взаимосвязь:

· Если прямая задача на максимум, то двойственная к ней - на минимум, и наоборот.

· Коэффициенты целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

· Свободные члены ограничений прямой задачи являются коэффициентами целевой функции двойственной.

· Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.

· Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

· Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной - числу переменных прямой.

· Все переменные в обеих задачах неотрицательны.

13) Основные правила перехода к двойственной задаче.

Важную роль в линейном программировании имеет понятие двойственности. Далее представлены две задачи линейного программирования:

max {F(x) = C^T x| Ax?B, x_i?0, i =1, n} (1)

и

min {F(y) = B^T y| A^T y?C, y_j ?0, j = 1, m} (2)

Задачу (1) называют прямой, а связанную с ней задачу (2) - двойственной. Вместе они образуют симметрическую пару двойственных задач. Число переменных двойственной задачи равно количеству ограничений прямой. Кроме того, при переходе от прямой задачи к двойственной вектора B и C меняют местами, матрица A коэффициентов системы ограничений прямой задачи транспонируется, а знак неравенств в ограничениях меняют на противоположный. Смысл экстремума F(x) противоположен смыслу экстремума F(y). Связь между задачами (1) и (2) взаимна, т.е. если прямой считать задачу (2), то в качестве двойственной ей будет соответствовать задача (1). Возможность перехода от прямой задачи к двойственной (и наоборот) устанавливается теоремой двойственности: если одна из задач (1) или (2) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем оптимальные значения функции цели прямой и двойственной задач совпадают, т.е. max F(x) = min F(y).

Если среди ограничений прямой задачи имеются равенства или на некоторые переменные не наложено условие неотрицательности, то построив двойственную ей задачу, получится пару несимметричных двойственных задач:



При этом выполняются следующие правила:

· Если на переменную x_i прямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.

· Если на переменную xi прямой задачи не наложено условие неотрицательности, то i-е ограничение двойственной задачи записывается в виде строгого равенства.

· Если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не накладывается условие неотрицательности.

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

Далее приведена задача рационального использования ресурсов.

Пусть предприятие располагает ресурсами b₁, b₂,…, b_m, которые могут использоваться для выпуска n видов продукции. Известны нормы потребления j-го ресурса на производство единицы i-й продукции - a_ij, а также прибыль от реализации единицы i-го вида продукции c_i (i = 1, n; j = 1, m). Найти объем производства продукции каждого вида x*_i, максимизирующий суммарную прибыль предприятия F(x) = ?c_ix_i, при этом расход ресурсов не должен превышать их наличия. Математическая модель задачи имеет вид



max {F(x)=?c_ix_i|?a_jix_i?b_j, j=1, m; x_i?0, i=1, n} (3)

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

max {F(x)=?c_ix_i|?a_jix_i=b_j, j=1, m; x_i?0}.

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

а) насколько можно увеличить запас некоторого ресурса, чтобы улучшить оптимальное значение F;

б) насколько можно сократить запас некоторого ресурса, чтобы сохранить при этом оптимальное значение F;

в) увеличение объема, какого из ресурсов наиболее выгодно;

г) какому из ресурсов отдать предпочтение при вложении дополнительных средств;

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

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

Сформулируем задачу, двойственную к рассматриваемой задаче рационального использования ресурсов. Пусть некоторая организация может закупить все ресурсы b_j, которыми располагает предприятие. Необходимо определить оптимальные цены y*_j (j = 1, m) на единицу этих ресурсов при условии, что покупатель стремиться минимизировать общую оценку ресурсов. При этом общая ценность ресурсов должна быть не меньше прибыли, которую может получить предприятие при организации собственного производства. Математическая модель задачи имеет вид

min {F(y)=?b_jy_j|?a_ijy_j?c_i, i=1, n; y_j0, j=1, m} (4)

Пока прибыль предприятия (задача 3) меньше общей ценности ресурсов (задача 4), решение обеих задач будет неоптимальным. Оптимум достигается в случае, когда прибыль становится равной общей ценности ресурсов, т.е. max F(x) = min F(y).



2. Алгоритм решения задачи

	Хлеб	Соя	Сушеная рыба	Фрукты	Молоко
Белки Углеводы Жиры Витамины	2 12 1 2	12 0 8 2	10 0 3 4	1 4 0 6	2 3 4 2
Цена	12	36	32	18	10

Необходимо ввести переменные и обозначить функцию:

x₁ - хлеб (а так же содержащиеся в нём белки, углеводы, жиры, витамины).

x₂ - соя (а так же содержащиеся в ней белки, углеводы, жиры, витамины).

x₃ - сушёная рыба (а так же содержащиеся в ней белки, углеводы, жиры, витамины).

x₄ - фрукты (а так же содержащиеся в них белки, углеводы, жиры, витамины).

x₅ - молоко (а так же содержащиеся в нём белки, углеводы, жиры, витамины).

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

Найдем наименьшее значение линейной функции

Z = 12*х₁ + 36*х₂ + 32*х₃ + 18*х₄ + 10*х₅

Ограничивающие условия («?» в соответствии с вариантом):

2*х₁ + 12*х₂ + 10*х₃ + 1*х₄ + 2*х₅ >= 36

12*х₁ + 0*х₂ + 0*х₃ + 4*х₄ + 3 *х₅ >= 46

1*х₁ + 8*х₂ + 3*х₃ + 0 *х₄ + 4 *х₅ >= 26

2*х₁ + 2*х₂ + 4*х₃ + 6*х₄ + 2*х₅ >=56

Умножим коэффициенты исходной функции на -1.

Z = -12*х₁ - 36*х₂ - 32*х₃ - 18*х₄ - 10*х₅

Будем искать наибольшее значение получившейся функции. Максимальное значение рассматриваемой функции равно наименьшему значению исходной функции по модулю, но значения противоположны по знаку. Другими словами, получившийся ответ нужно умножить на -1.

Необходимо найти начальное опорное (абсолютно произвольное) решение для функции Z, которое бы удовлетворяло системе наложенных ограничений. Далее, применяя симплекс таблицы, получаются решения, при которых значение функции будет, как минимум, не убывать. И так до тех пор, пока оптимальное значение не будет достигнуто, а функция достигает своего максимума. Если, конечно, рассматриваемая линейная функция обладает максимальным значением при заданной системе ограничений. Перед применением симплекс таблиц, необходимо преобразовать систему линейных ограничений и рассматриваемую функцию Z к вполне определенному виду:

· Свободные члены системы ограничений должны быть неотрицательными.

Свободные члены системы ограничений неотрицательные.

· Система ограничений должна быть приведена к каноническому виду.

От левой части неравенства 1 системы ограничений отнимаем неотрицательную переменную x₆ - преобразуем неравенство 1 в равенство.

От левой части неравенства 2 системы ограничений отнимаем неотрицательную переменную x₇ - преобразуем неравенство 2 в равенство.

От левой части неравенства 3 системы ограничений отнимаем неотрицательную переменную x₈ - преобразуем неравенство 3 в равенство.

От левой части неравенства 4 системы ограничений отнимаем неотрицательную переменную x₉ - преобразуем неравенство 4 в равенство.

Размещено на Allbest.ru