Определение целевой функции симплекс-методом

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

Введение

Курсовое проектирование по дисциплине «Математические методы» является неотъемлемой частью подготовки специалистов в среднем профессиональным образованием.

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

Цель курсовой работы:

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

Задачи курсовой работы:

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

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

проанализировать возможные подходы и методы решения с обоснованием выбранного метода;

развить навыки работы со справочной литературой, материалами ГОСТов;

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

разработка программной и эксплуатационной документации;

проанализировать полученные результаты работы;



1. Оптимизация целевой функции симплекс-методом

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

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л.В. в 1937 году.

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

W(x) = c,

где W(x) - максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку - требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

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

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

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

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

1.2 Алгоритм симплекс-метода

Усиленная постановка задачи

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

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

(1)

Где, x - переменные из исходного линейного функционала,

xs - новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство,

c - коэффициенты исходного линейного функционала,

Z - переменная, которую необходимо максимизировать.

Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно:.

Алгоритм

Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:

(2)

где cB - коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B - столбцы АЕ, соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг

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

Второй шаг

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' - простые, а x ' ' - непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx '+Dx ' '=b. Умножим его на слева:. +=

Таким образом мы выразили простые переменные через непростые, и в выражении, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству равенство , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент - все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение.

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение

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

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

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

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



2. Использование симплексного метода

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

Отправить на склад для хранения (А2 стратегия) или подвергнуть обработке для длит. Хранения (А3 стратегия). Потребитель может приобрести немедленно (В1 стратегия) ,через некоторое время (В2 стратегия) или после длительного периода (В3 стратегия). В случае стратегий А2 и А3 предприятие несет дополнительные затраты на хранение и обработку продукции. Однако, при А2 следует вычесть убытки, если потребитель выберет стратегию В2 или В3 . Определить оптимальные пропорции для применения стратегий А1,А2,А3. Руководствуясь минимаксным критерием, гарантирует средний уровень убытка. Пользуясь минимальным критерием из таблицы.

Таблица 1 - Оптимальные стратегии

Игроки	B1	B2	B3	a =min(Ai)
A1	2	3	2	2
A2	4	2	1	1
A3	1	3	3	1
b = max(Bi)	4	3	3	0

Решение матричной игры

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1. Верхняя цена игры b = min(bj) = 3. Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 2<= y <= 3. Находим решение игры в смешанных стратегиях. 

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



найти минимум функции F(x) при ограничениях:

2x1+4x2+x3 >= 1 3x1+2x2+3x3 >= 1 2x1+x2+3x3 >= 1 F(x) = x1+x2+x3 = min 

найти максимум функции Ф(y) при ограничениях:

2y1+3y2+2y3 <= 1 4y1+2y2+y3 <= 1 y1+3y2+3y3 <= 1 Ф(y) = y1+y2+y3 = max 

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

Определим минимальное значение целевой функции

F(X) = x1 + x2 + x3 при следующих условиях-ограничениях.

2x1 + 4x2 + x3?1 3x1 + 2x2 + 3x3?1 2x1 + x2 + 3x3?1 

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

2x1 + 4x2 + 1x3-1x4 + 0x5 + 0x6 = 1 3x1 + 2x2 + 3x3 + 0x4-1x5 + 0x6 = 1 2x1 + 1x2 + 3x3 + 0x4 + 0x5-1x6 = 1 

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

-2x1-4x2-1x3 + 1x4 + 0x5 + 0x6 = -1 -3x1-2x2-3x3 + 0x4 + 1x5 + 0x6 = -1 -2x1-1x2-3x3 + 0x4 + 0x5 + 1x6 = -1 



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

x4, x5, x6, Полагая, что свободные переменные равны 0, получим первый опорный план:X1 = (0,0,0,-1,-1,-1)

Таблица 2 - Первый опорный план

План	Базис	B	x1	x2	x3	x4	x5	x6
0	x4	-1	-2	-4	-1	1	0	0
	x5	-1	-3	-2	-3	0	1	0
	x6	-1	-2	-1	-3	0	0	1
Индексная строка	F(X0)	0	1	1	1	0	0	0

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

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

Таблица 3 - Расчет двойственного симплекс-метода

План	Базис	B	x1	x2	x3	x4	x5	x6	min
	x1	1/2	1	2	1/2	-1/2	0	0	0
	x5	1/2	0	4	-11/2	-11/2	1	0	0
	x6	0	0	3	-2	-1	0	1	0
Индексная строка	F(X)	-1/2	0	-1	1/2	1/2	0	0	0

Представим расчет каждого элемента в виде таблицы:



Таблица 4 - Расчет каждого элемента

B	x1	x2	x3	x4	x5	x6
1/2:1	1:1	2:1	1/2:1	-1/2:1	0:1	0:1
1/2-(1/2*0):1	0-(1*0):1	4-(2*0):1	-11/2-(1/2*0):1	-11/2-(-1/2*0):1	1-(0*0):1	0-(0*0):1
0-(1/2*0):1	0-(1*0):1	3-(2*0):1	-2-(1/2*0):1	-1-(-1/2*0):1	0-(0*0):1	1-(0*0):1
-1/2-(1/2*0):1	0-(1*0):1	-1-(2*0):1	1/2-(1/2*0):1	1/2-(-1/2*0):1	0-(0*0):1	0-(0*0):1

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.

Таблица 5 - Конечный опорный план

План	Базис	B	x1	x2	x3	x4	x5	x6	min
1	x1	1/2	1	2	1/2	-1/2	0	0	1/4
	x5	1/2	0	4	-11/2	-11/2	1	0	1/8
	x6	0	0	3	-2	-1	0	1	0
Индексная строка	F(X1)	-1/2	0	-1	1/2	1/2	0	0	0

Итерация №0. 

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

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

Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее: min (1/2:2 , 1/2:4 , -) = 0

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

Формируем следующую часть симплексной таблицы. Вместо переменной (x) в план 1 войдет переменная x2 . Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=3 

На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2 . 

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

НЭ = СЭ - (А*В)/РЭ 

СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

Таблица 6 - Расчет опорного плана

B	x1	x2	x3	x4	x5	x6
1/2-(0*2):3	1-(0*2):3	2-(3*2):3	1/2-(-2*2):3	-1/2-(-1*2):3	0-(0*2):3	0-(1*2):3
1/2-(0*4):3	0-(0*4):3	4-(3*4):3	-11/2-(-2*4):3	-11/2-(-1*4):3	1-(0*4):3	0-(1*4):3
0:3	0:3	3:3	-2:3	-1:3	0:3	1:3
-1/2-(0*-1):3	0-(0*-1):3	-1-(3*-1):3	1/2-(-2*-1):3	1/2-(-1*-1):3	0-(0*-1):3	0-(1*-1):3

Таблица 7 - План 2

План	Базис	B	x1	x2	x3	x4	x5	x6	min
2	x1	1/2	1	0	15/6	1/6	0	-2/3	3 /11
	x5	1/2	0	0	11/6	-1/6	1	-11/3	3/7
	x2	0	0	1	-2/3	-1/3	0	1/3	-
Индексная строка	F(X2)	-1/2	0	0	-1 /6	1/6	0	1/3	0



Итерация №1 

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

Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее: min (1/2:15/6 , 1/2:11/6, - ) = 3/11 

Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (15/6) и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. 

Вместо переменной x в план 2 войдет переменная x3 . Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x1 плана 1 на разрешающий элемент РЭ=15/6 .На месте разрешающего элемента в плане 2 получаем 1. 

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

НЭ = СЭ - (А*В)/РЭ 

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

Представим расчет каждого элемента в виде таблицы:



Таблица 8 - Расчет элементов старого плана

B	x1	x2	x3	x4	x5	x6
1/2:15/6	1:15/6	0:15/6	15/6:15/6	1/6:15/6	0:15/6	-2/3:15/6
1/2-(1/2*11/6):15/6	0-(1*11/6):15/6	0-(0*11/6):15/6	11/6-(15/6*11/6):15/6	-1/6-(1/6*11/6):15/6	1-(0*11/6):15/6	-11/3-(-2/3*11/6):15/6
0-(1/2*-2/3):15/6	0-(1*-2/3):15/6	1-(0*-2/3):15/6	-2/3-(15/6*-2/3):15/6	-1/3-(1/6*-2/3):15/6	0-(0*-2/3):15/6	1/3-(-2/3*-2/3):15/6
-1/2-(1/2*-1/6):15/6	0-(1*-1/6):15/6	0-(0*-1/6):15/6	-1/6-(15/6*-1/6):15/6	1/6-(1/6*-1/6):15/6	0-(0*-1/6):15/6	1/3-(-2/3*-1/6):15/6

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

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

План	Базис	B	x1	x2	x3	x4	x5	x6
3	x3	3/11	6/11	0	1	1/11	0	-4/11
	x5	2/11	-7/11	0	0	-3/11	1	-10/11
	x2	2/11	4/11	1	0	-3/11	0	1/11
Индексная строка	F(X3)	-5/11	1/11	0	0	2/11	0	3/11

Оптимальный план можно записать так:x3 = 3/11 x5 = 2/11 x2 = 2/11 F(X) = 1*3/11 + 1*2/11 = 5/11 

Составим двойственную задачу к прямой задаче. 2y1 + 3y2 + 2y3?1 4y1 + 2y2 + y3?1 y1 + 3y2 + 3y3?1 y1 + y2 + y3 => max y1 ? 0; y2 ? 0; y3?0

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

Из теоремы двойственности следует, что Y = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис.



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

Как видно из последнего плана симплексной таблицы, обратная матрица A1 расположена в столбцах дополнительных переменных.

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

Оптимальный план двойственной задачи равен:y1 = 2/11 y2 = 0 y3 = 3/11 Z(Y) = 1*2/11+1*0+1*3/11 = 5/11

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

pi = g*xi; qi = g*yi. Цена игры:g = 1:5/11 = 21/5 p1 = 21/5*0 = 0 p2 = 21/5*2/11 = 2/5 p3 = 21/5*3/11 = 3/5 q1 = 21/5*2/11 = 2/5 q2 = 21/5*0 = 0 q3 = 21/5*3/11 = 3/5

Оптимальная стратегия игрока А:P( 0; 2/5; 3/5) 

Оптимальная стратегия игрока B:Q(2/5;0;3/5)



3. Задача

При откорме животных каждое из них должно ежедневно получать витамины A, D и E не менее 32. 44 и 44 ед. Указанные питательные вещества содержатся в четырех видах кормов, цены которых составляют 15, 25, 42 и 18 рублей за 1 кг. Содержание питательных веществ в 1 кг каждого из видов кормов составляет: первый вид корма - 26, 30 и 28. Второй вид корма - 18, 20 и 19. Третий вид корма - 30, 28 и 32. Четвертый вид корма - 10, 19 и 17. Составить рацион кормления, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

симплекс метод математический программирование

F(X) = 15x1 + 25x2 + 42x3 + 18x4->min 26x1 + 18x2 + 30x3 + 10x4>=32 30x1 + 20x2 + 28x3 + 19x4>=44 28x1 + 19x2 + 32x3 + 17x4>=48

Решение задачи

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

F(X) = 15x1 + 25x2 + 42x3 + 18x4

при следующих условиях-ограничений.

26x1 + 18x2 + 30x3 + 10x4>=32 30x1 + 20x2 + 28x3 + 19x4>=44 28x1 + 19x2 + 32x3 + 17x4>=48

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

26x1 + 18x2 + 30x3 + 10x4-1x5 + 0x6 + 0x7 = 32 30x1 + 20x2 + 28x3 + 19x4 + 0x5-1x6 + 0x7 = 44 28x1 + 19x2 + 32x3 + 17x4 + 0x5 + 0x6-1x7 = 48

Умножим все строки на (-1) и будем искать первоначальный опорный план.

-26x1-18x2-30x3-10x4 + 1x5 + 0x6 + 0x7 = -32 -30x1-20x2-28x3-19x4 + 0x5 + 1x6 + 0x7 = -44 -28x1-19x2-32x3-17x4 + 0x5 + 0x6 + 1x7 = -48

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

Таблица 10 - Матрица коэффициентов

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	-32	-26	-18	-30	-10	1	0	0
x6	-44	-30	-20	-28	-19	0	1	0
x7	-48	-28	-19	-32	-17	0	0	1
F(X0)	0	15	25	42	18	0	0	0

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

Полагая, что свободные переменные равны 0, получим первый опорный план:X1 = (0,0,0,0,-32,-44,-48)

Таблица 11 - Матрица коэффициентов

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	-32	-26	-18	-30	-10	1	0	0
x6	-44	-30	-20	-28	-19	0	1	0
x7	-48	-28	-19	-32	-17	0	0	1
F(X0)	0	15	25	42	18	0	0	0



План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-17).

Таблица 12 - Нахождение ведущей строки и столбца

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	-32	-26	-18	-30	-10	1	0	0
x6	-44	-30	-20	-28	-19	0	1	0
x7	-48	-28	-19	-32	-17	0	0	1
F(X0)	0	15:(-28) = -15/28	25:(-19) = -16/19	42:(-32) = -15/16	18:(-17) = -11/17	-	-	-

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-10/17).

Таблица 13 - Нахождение решающего элемента

Базис	В	X1	X2	X3	X4	X5	X6	X7
X5					0	1	0
X6					0	0	1
X4					1	0	0
F(X0)					0	0	0
0	0		(		-	-	-

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.



Итерация №0

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

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

Вычислим значения Di по строкам как частное от деления:bi / ai1 и из них выберем наименьшее:

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

Таблица 14 - Выбор наименьшего значения

Базис	B	x1	x2	x3	x4	x5	x6	min
X7			19	0		0	1
x6				29	0		1
X4				3	1	0	0
F(X0)			-12	0		0	0	0

Получаем новую симплекс-таблицу.

Итерация №1

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

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

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

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



Таблица 15 - Нахождение разрешающего элемента

Базис	B	X1	X2	X3	X4	X5	X6	X7	min
X1		1			0		0		-
X6		0			0		1
X4		0			1	0
F(X2)		0			0	0		0

Получаем новую симплекс-таблицу.

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

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

Базис	B	X1	X2	X3	X4	X5	X6	X7
X1		1				0	0
X6		0				0	1
X5		0				1	0
F(x3)		0				0	0

Оптимальный план можно записать так:x1 = 15/7 F(X) = 15*15/7 = 255/7



Заключение

В данной курсовой работе мне было предложено изучить "Определение целевой функции симплекс-методом", а также симплекс-метод в целом. Поскольку симплекс-метод был разработан еще в 1937 году его применение все еще остается актуальным. Симплекс-метод помогает максимизировать или минимизировать оптимальный план на определенном функциональном пространстве какой-либо задачи линейного программирования. В ходе изучения этого метода я узнал основные правила и алгоритм решения поставленной задачи, а также, что решение зависит от условий ограничения функции. Если задача поставлена в нахождении минимума целевой функции, то все вспомогательные переменные будут увеличивать значение этой функции, а если задача поставлена в нахождении максимума, то все вспомогательные переменные будут уменьшать значение данной целевой функции. Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «?», то далеко не всегда нулевой вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат. Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация. Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются: дополнительные переменные сообщают, насколько соответствующее им ограничение «недоиспользовано». Значение дополнительной переменной, равное нулю, соответствует равенству значений правых и левых частей ограничения. Вспомогательные переменные сообщают, насколько данное условие далеко от допустимого (относительно конкретного ограничения).



Список используемой литературы

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2001.

2. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

3. Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций. - М.:2006.

4. Агальцов В.П., Волдайская И.В. Математические методы в программировании. - М.:"Форум" - ИНФРА-М, 2006.

5. Партыка Т.Л., Попов И.И. Математические методы. - М.:"Форум" - ИНФРА-М, 2005.

6. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research:An Introduction. - 7-е изд. - М.:"Вильямс", 2007. - С. 95-141. - ISBN 0-13-032374-8.

7. Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9.

8. Емельянов А.А. Имитационное моделирование экономических процессов [Текст]: Учеб. пособие для вузов / А.А. Емельянов, Е.А. Власова, Р.В. Дума. - М.: Финансы и статистика, 2002. - 368 с.

9. Бусленко, Н.П. Моделирование сложных систем [Текст] / Н.П. Бусленко.- М.: Наука, 1978. - 399 с.

10. Советов Б.Я. Моделирование систем [Текст]: Учеб. для вузов / Б.Я. Советов, С.А. Яковлев. - М.: Высш. школа, 1985. - 271 с.

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