Оптимизация ипользования ресурсов

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

12

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

КУРСОВАЯ РАБОТА

Тема: «ОПТИМИЗАЦИЯ ИСПОЛЬЗОВАНИЯ РЕСУРСОВ»

Задание

Для реализации трех товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b1, b2, b3 единиц. При этом для продажи первой группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a11 единиц, ресурса второго вида - в количестве a21 единиц, ресурса третьего вида - в количестве a31 единиц. Для продажи второй и третьей групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a12, a13 единиц, ресурсов второго вида - в количестве a22, a23 единиц, ресурсов третьего вида - в количестве a32, a33 единиц. Доход от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно с1, с2, с3 (тыс. руб.).

Определите плановый объем и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

Вариант 6.

a11 = 1, a12 = 4, a13 = 0, a21 = 0, a22 = 3, a23=1, a31 = 2, a32=0, a33 = 5,

b1= 36, b2 = 50, b3 = 80,

c1 = 6, с2 = 16, c3 = 25.

1. Этапы выполнения работы

Рассмотрим задачу оптимизации ресурсов при планировании товарооборота торгового предприятия в общем виде.

Коммерческое предприятие реализует п товарных групп, располагая m ограниченными материально-денежными ресурсами . Известны расходы ресурсов каждого вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А = (аij), и прибыль сj, получаемая предприятием от реализации единицы товара j группы. Надо определить объем и структуру товарооборота при которых прибыль коммерческого предприятия была бы максимальной.

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

Работа включает 5 этапов

· формирование математической модели задачи;

· решение задачи симплекс-методом;

· построение двойственной задачи;

2. Формирование математической модели задачи

В целом экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид: найти максимальное (минимальное) значение линейной целевой функции

(3.1)

при условиях-ограничениях:

где aij, bi cj - заданные постоянные величины.

Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (3.1) при выполнении условий (3.2) и (3.4), где k = 0 и l = п.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (3.1) при выполнении условий (3.3) и (3.4).

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

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

В случае когда требуется найти минимум функции можно перейти к нахождению максимума функции так как .

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

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

Запишем в основной задаче линейного программирования ограничение (3.3) в векторной форме

(3.5)

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

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

Так как векторы являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать т.

Опорный план называется невырожденным, если он содержит ровно т положительных компонент. Если в опорном плане число положительных компонент меньше т, то план является вырожденным.

3. Решение задачи симплекс-методом

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

Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.

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

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

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

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

3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из выражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.

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

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

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

Алгоритм симплексного метода включает следующие этапы.

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

где - базисные переменные,

- свободные переменные,

Решим эту систему относительно базисных переменных:

а функцию цели перепишем в виде уравнения

.

Полагая, что основные переменные , получим первый опорный план

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

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

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

Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+; -/-) ведущего столбца. Результаты заносим в отдельный столбец которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению является ведущей. Она определяет переменную которая на следующей итерации выйдет из базиса и станет свободной.

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

4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т.е. вместо в базис войдет переменная , соответствующая ведущему столбцу.

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

где СТЭ - элемент старого плана,

РЭ - разрешающий элемент,

А и В-элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Далее возвращаемся ко второму этапу алгоритма - проверка плана на оптимальность.

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

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

Если в столбце симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. С целью исключения этого для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содержащая три равных значения , имеет вид, показанный в табл. 3.1.

Таблица 3.1

План	Базисные переменные	Значения базисных переменных
II		4	2	3	6	1	0	0	2	4/2=2
		8	4	8	1	0	1	0	4
		10	5	12	-1	1	0	1	5	10/5=2

Допустим, разрешающим столбцом является , который вводится в новый план, тогда разрешающим элементом может быть: 2, 4 или 5. Следуя указанному правилу, получим таблицу 3.2.

Таблица 3.2

Значения базисных переменных
2	1	1.5	3	0.5	0	0	1
2	1	2	0.25	0	0.25	0	1
2	1	2.4	-0.2	0.2	0	0.2	1

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

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

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

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

Определим максимальное значение целевой функции F(X) = 6x₁ + 16x₂ + 25x₃ при следующих условиях-ограничений.

x₁ + 4x₂?36

+ 3x₂ + x₃?50

2x₁ + 5x₃?80

Для построения первого опорного плана систему неравенств, приведем к системе уравнений путем введения дополнительных переменных.

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

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

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

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

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

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

В 1-м неравенстве смысла (?) вводим базисную переменную x₄. В 2-м неравенстве смысла (?) вводим базисную переменную x₅. В 3-м неравенстве смысла (?) вводим базисную переменную x₆.

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

симплекс задача оптимизация ресурс

1x₁ + 4x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 36

0x₁ + 3x₂ + 1x₃ + 0x₄ + 1x₅ + 0x₆ = 50

2x₁ + 0x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 80

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

Определимся с начальным опорным решением.

Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:

Переменная x4 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная.

Переменная x5 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная.

Переменная x6 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x6 - базисная переменная.

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

Введем новую переменную x₀ = 6x₁ + 16x₂ + 25x₃.

Выразим базисные переменные <4, 5, 6> через небазисные.

x₀ = 0+6x₁+16x₂+25x₃

x₄ = 36-x₁-4x₂

x₅ = 50-3x₂-x₃

x₆ = 80-2x₁-5x₃

Переходим к основному алгоритму симплекс-метода.

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

x₀ = 0+6x₁+16x₂+25x₃

x₄ = 36-x₁-4x₂

x₅ = 50-3x₂-x₃

x₆ = 80-2x₁-5x₃

В качестве новой переменной выбираем x₃.

Вычислим значения D₃ по всем уравнениям для этой переменной.

и из них выберем наименьшее:

min (-, 50: 1, 80: 5) = 16

Вместо переменной x₆ в план войдет переменная x₃.

Выразим переменную x₃ через x₆ и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x₀ = 400-4x₁+16x₂-5x₆

x₄ = 36-x₁-4x₂

x₅ = 34+²/₅x₁-3x₂+¹/₅x₆

x₃ = 16^-2/₅x₁^-1/₅x₆

Полагая небазисные переменные x = (4, 5, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (4, -16, 0, 0, 0, 5), x₀ = 400

x₀ = 400-4x₁+16x₂-5x₆

x₄ = 36-x₁-4x₂

x₅ = 34+²/₅x₁-3x₂+¹/₅x₆

x₃ = 16^-2/₅x₁^-1/₅x₆

В качестве новой переменной выбираем x₂.

Вычислим значения D₂ по всем уравнениям для этой переменной.



и из них выберем наименьшее:

min (36: 4, 34: 3, -) = 9

Вместо переменной x₄ в план войдет переменная x₂.

Выразим переменную x₂ через x₄ и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x₀ = 544-8x₁-4x₄-5x₆

x₂ = 9^-1/₄x₁^-1/₄x₄

x₅ = 7+1³/₂₀x₁+³/₄x₄+¹/₅x₆

x₃ = 16^-2/₅x₁^-1/₅x₆

Полагая небазисные переменные x = (2, 5, 3) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (8, 0, 0, 4, 0, 5), x₀ = 544

Выражение для x₀ не содержит положительных элементов. Найден оптимальный план.

Окончательный вариант системы уравнений:

x₀ = 544-8x₁-4x₄-5x₆

x₂ = 9^-1/₄x₁^-1/₄x₄

x₅ = 7+1³/₂₀x₁+³/₄x₄+¹/₅x₆

x₃ = 16^-2/₅x₁^-1/₅x₆

Оптимальный план можно записать так:

x₂ = 9

x₅ = 7

x₃ = 16

F(X) = 16*9 + 25*16 = 544

4. Построение двойственной задачи

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

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

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

Прямая задача линейного программирования в стандартной форме записывается следующим образом:

максимизировать

 (3.6)

при ограничениях:

(3.7)

(3.8)

Чтобы сформулировать условия двойственной задачи, проведем симметричное структурное преобразование условий прямой задачи в соответствии со следующими правилами:

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;

2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;

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

На примере задачи планирования товарооборота двойственная задача формулируется следующим образом:

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

Запишем математическую модель двойственной задачи.

Определить вектор , который удовлетворяет ограничениям

(3.9)

(3.10)

и обеспечивает минимальное значение целевой функции

(3.11)

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

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

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

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

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

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

5. Двойственная задача решается на минимум, если целевая функция прямой задачи задается на максимум, и наоборот.

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

7. Если переменная прямой задачи 0, то j-е условие системы ограничений двойственной задачи является неравенством, если - любое число, то j-е условие двойственной задачи представляет собой уравнение.

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

5. Решение Двойственной задачи

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

Определим максимальное значение целевой функции F(X) = 6x₁+16x₂+25x₃ при следующих условиях-ограничений.

x₁+4x₂?36

3x₂+x₃?50

2x₁+5x₃?80

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

В 1-м неравенстве смысла (?) вводим базисную переменную x₄. В 2-м неравенстве смысла (?) вводим базисную переменную x₅. В 3-м неравенстве смысла (?) вводим базисную переменную x₆.

1x₁ + 4x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 36

0x₁ + 3x₂ + 1x₃ + 0x₄ + 1x₅ + 0x₆ = 50

2x₁ + 0x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 80

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x₄, x₅, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,36,50,80)

Базис	В	x1	x2	x3	x4	x5	x6
x4	36	1	4	0	1	0	0
x5	50	0	3	1	0	1	0
x6	80	2	0	5	0	0	1
F(X0)	0	-6	-16	-25	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:



Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	min
x4	36	1	4	0	1	0	0	0
x5	50	0	3	1	0	1	0	50
x6	80	2	0	5	0	0	1	16
F(X1)	0	-6	-16	-25	0	0	0	0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6
x4	36	1	4	0	1	0	0
x5	34	-0.4	3	0	0	1	-0.2
x3	16	0.4	0	1	0	0	0.2
F(X1)	400	4	-16	0	0	0	5

Итерация №1.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	min
x4	36	1	4	0	1	0	0	9
x5	34	-0.4	3	0	0	1	-0.2	11.33
x3	16	0.4	0	1	0	0	0.2	0
F(X2)	400	4	-16	0	0	0	5	0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6
x2	9	0.25	1	0	0.25	0	0
x5	7	-1.15	0	0	-0.75	1	-0.2
x3	16	0.4	0	1	0	0	0.2
F(X2)	544	8	0	0	4	0	5

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис	В	x1	x2	x3	x4	x5	x6
x2	9	0.25	1	0	0.25	0	0
x5	7	-1.15	0	0	-0.75	1	-0.2
x3	16	0.4	0	1	0	0	0.2
F(X3)	544	8	0	0	4	0	5

Оптимальный план можно записать так:

x₂ = 9

x₅ = 7

x₃ = 16

F(X) = 16*9 + 25*16 = 544

Составим двойственную задачу к прямой задаче.

y₁+2y₃?6

4y₁+3y₂?16

y₂+5y₃?25

36y₁+50y₂+80y₃ => min

y₁ ? 0

y₂ ? 0

y₃ ? 0

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

Из первой теоремы двойственности следует, что Y = C*A^-1.

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

Определив обратную матрицу А^-1 через алгебраические дополнения, получим:

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 4

y₂ = 0

y₃ = 5

Z(Y) = 36*4+50*0+80*5 = 544

Выводы

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

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

В данном курсовом проекте был реализован Симплекс - метод решения экономико-математической модели. Найден наиболее оптимальный вариант решения задачи с несколькими ограничениями по ресурсам.

Список литературы

1. Экономико-математическое моделирование: Учебник для студентов вузов/ Под общ. ред. И.Н. Дрогобыцкого. - М.: Экзамен», 2004.

2. Замков О.О., толстопятенко А.В. Математические методы в экономике. М.: Дело и сервис, 2009.

3. Покровский В.В. Математические методы в бизнесе и менеджменте. М.: Бином, 2008

4. Фомин Г.П. Математические методы и модели. М.: ФиС, 2001

5. Хэмди А. Таха. Введение в исследование операций. М.: Издательский дом Вильямс, 2001

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