Решение задачи линейного программирования
Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 31.10.2014 |
| Размер файла | 100,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Содержание
Введение
1. Постановка задачи
2. Построение математической модели
3. Выбор, обоснование и описание метода решений рассматриваемой задачи
3.1 Общая задача линейного программирования
3.2 Выбор метода реализации модели
3.3 Алгоритм симплекс-метода
4. Решение задачи симплекс-методом
4.1 Решение прямой задачи линейного программирования симплексным методом
4.2 Составление и решение двойственной задачи
5. Анализ модели на чувствительность
Заключение
Список библиографических источников
Введение
Экономические проблемы, возникающие перед специалистами, в большинстве своем сложные. Они зависят от множества различных, иногда противоречащих друг другу факторов, изменяются с течением времени и влияют на другие проблемы и процессы.
Вследствие этого исследование экономической проблемы целесообразно проводить на адекватной математической модели. Математическая модель отражает проблему в абстрактной форме и позволяет учесть большое число разнообразных характеристик, от которых эта проблема зависит. Анализ и расчет математической модели позволяют выбрать оптимальные решения поставленной задачи и обосновать этот выбор.
Целью данной работы является решение конкретной задачи линейного программирования. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства.
Для решения задач линейного программирования созданы специальные методы. Изучению одного из них, а именно симплекс-методу, посвящена эта работа. В соответствии с целью в работе поставлены и решены следующие задачи:
- произвести построение математической модели задачи;
- выбрать и описать метод реализации модели;
- решить прямую и двойственную задачи выбранным методом;
- произвести анализ модели на чувствительность.
Объектом исследования является сельскохозяйственное производство на Нарвских островах для внешнего рынка.
Предметом исследования являются данные о землях и культурах, которые выращиваются в этом климате.
1. Постановка задачи
Была предложена следующая простая модель сельскохозяйственного производства на Нарвских островах для внешнего рынка. Имеются три основные культуры, растущие в этом климате, и выращиваться они могут на одном из двух типов пахотных земель. В настоящее время для обработки пригодны 1400000 акров земли типа I и 1200000 акров земли типа II. Разные типы культур по-разному растут на разных землях, и подсчитано, что чистый урожай культуры i с земли типа j составляет Rij.
Таблица 1
|
I |
Rij |
||
|
J=I |
J=II |
||
|
1 |
6 |
6 |
|
|
2 |
8 |
5 |
|
|
3 |
4 |
5 |
Все культуры требуют дополнительного орошения (ирригационного). Имеющаяся ирригационная система обеспечивает 5600000 м3 воды в год. Для одного акра культуры i, выращенной на земле типа j, требуется Wij м3 воды в год.
Таблица 2
|
I |
Wij |
||
|
J=I |
J=II |
||
|
1 |
2 |
3 |
|
|
2 |
3 |
3 |
|
|
3 |
3 |
2 |
Население, занятое в сельском хозяйстве, составляет 700000 человек. Чтобы получить урожаи 1,2,3 с каждых 10 акров земли, для выполнения различных работ по выращиванию культур в течение 1 года требуется, соответственно, 2, 1 и 3 человека.
Определите, какие культуры, в каком количестве и на каких землях необходимо выращивать, чтобы получить максимальный урожай? Каков размер максимального урожая?
Решение должно содержать:
- построение математической модели;
- выбор, обоснование и описание метода решений рассматриваемой задачи;
- решение сформулированной задачи;
- анализ модели на чувствительность.
2. Построение математической модели
Процесс построения математической модели для решения поставленной задачи можно начать с ответов на три следующие вопроса:
1. Для определения каких величин должна быть построена модель?
2. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, для моделируемой системы?
3. В чем состоит цель, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи? [16, с. 102]
Отвечая на поставленные вопросы сформулируем суть проблемы - необходимо определить, какие культуры, в каком количестве и на каких землях необходимо выращивать, чтобы получить максимальный урожай. Также необходимо определить размер максимального урожая.
Введем обозначение переменных:
х1 - количество планируемого выращивания 1-й культуры на землях типа I;
х2 - количество планируемого выращивания 1-й культуры на землях типа IІ;
х3 - количество планируемого выращивания 2-й культуры на землях типа I;
х4 - количество планируемого выращивания 2-й культуры на землях типа IІ;
х5 - количество планируемого выращивания 3-й культуры на землях типа I;
х6 - количество планируемого выращивания 3-й культуры на землях типа IІ.
Учитывая, что чистый урожай культуры i с земли типа j составляет Rij, то можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х1, х2, х3, х4, х5, х6, которые обеспечат максимальный урожай:
Величины х1, х2, х3, х4, х5 и х6 нельзя выбирать произвольно, так как необходимо учесть ограничения на количество акров пригодных в настоящее время земель типа I и типа II. Ограничения на количество акров пригодных в настоящее время земель типа I и типа II можно записать следующим образом:
При решении рассматриваемой задачи должны быть учтены ограничения на дополнительное орошение. Ограничение на количество поставляемой ирригационной системой воды можно записать следующим образом:
Также должны быть учтены ограничения на население, занятое в сельском хозяйстве. Это ограничение можно записать следующим образом:
Так как отрицательные х1, х2, х3, х4, х5, х6 не имею смысла, то должно удовлетворяться ограничение:
x1 0, x20, x30, x40, x50, x60.
Итак, математическую модель можно записать следующим образом.
Математическая модель задачи: Определите, какие культуры, в каком количестве и на каких землях необходимо выращивать, чтобы получить максимальный урожай (X1, Х2, Х3, Х4, Х5, Х6):
при ограничениях:
где по смыслу задачи:
x1 0, x20, x30, x40, x50, x60.
Получили задачу на условный экстремум.
3. Выбор, обоснование и описание метода решений рассматриваемой задачи
3.1 Общая задача линейного программирования
Общей задачей линейного программирования (ОЗЛП) называют задачу: Максимизировать (минимизировать) функцию
(3.1)
при ограничениях: (3.2)
где cj, aij, bi -заданные действительные числа, (3.1) - целевая функция, (3.2) - ограничения, - план задачи.
Экономическая интерпретация модели ЛП состоит в следующем. Моделируемая система характеризуется наличием нескольких видов «производственной деятельности» , для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы Расход i-го ресурса на единицу продукта j-го вида производственной деятельности равен aij. В свою очередь при таком потреблении результат j-го вида производственной деятельности для единицы соответствующего продукта (удельная стоимость или прибыль) характеризуется величиной cj.
Цель построения модели состоит в определении уровней (объемов производства) каждого вида производственной деятельности xj, при которых оптимизируется (максимизируется или минимизируется) общий результат производственной деятельности системы в целом без нарушения ограничений, накладываемых на использование ресурсов.
Оптимальным решением (или оптимальным планом) задачи ЛП называется решение системы ограничений (2.2), при котором линейная функция (2.1) принимает оптимальное значение.
Термины «решение» и «план» - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй - о содержательной стороне (экономической интерпретации).
Симметричной формой записи ЗЛП называют задачу:
или задачу (3.3)
Рассмотрим задачу о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, фирма и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров) Пj, Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Все эти виды ограничивающих факторов называют ингредиентами Ri, Они ограничены, и их количества равны соответственно b1,b2,...,bm условных единиц.
Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д. Примем в качестве такой меры, например, цену реализации cj, j=. Известны также технологические коэффициенты aij, , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Обозначим через план производства, показывающий, какие виды товаров П1, П2,..., Пn нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.
Математическая модель задачи имеет следующий вид:
(3.4)
математический программирование симплекс таблица
Так как переменные xj входят в целевую функцию Z() и систему ограничений только в первой степени, а показатели aij, bi, cj являются постоянными в планируемый период, то (3.4) - задача линейного программирования.
3.2 Выбор метода реализации модели
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Линейный характер построенной модели определяет с формальных позиций то, что все входящие в нее функции (ограничения и целевая функция) линейны. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности.
1. Пропорциональность означает, что вклад каждой переменной х1, х2, х3, х4 в целевую функцию прямо пропорционален этим переменным.
2. Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных [10, с. 74].
Для привидения системы ограничений неравенств к каноническому виду, необходимо в системе ограничений выделить единичный базис.
Ограничения вида «?»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi.
Ограничения вида «?» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0» [7, с. 59].
3.3 Алгоритм симплекс-метода
Пусть система приведена к каноническому виду.
В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.
Fmin= C1X1+ C2X2+ C3X3+....+ CnXn (3.6)
Все hi должны быть больше либо равны нулю, где i=1,2...m.
На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.
Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица 3.1).
Таблица 3.1. Первая симплекс таблица
|
C |
Б |
H |
C1 |
C2 |
… |
Cm |
Cm+1 |
… |
Cm+k |
|
|
X1 |
X2 |
… |
Xm |
Xm+1 |
… |
Xm+k |
||||
C1C2 C3 Cm |
X1X2 X3 Xm |
h1h2 h3 |
1 0 0 |
0 1 0 |
: : : : |
0 0 0 0 |
q1,m+1 q2,m+1 q3,m+1 qm,m+1 |
: : : |
q1,m+k q2,m+k q3,m+k:qm,m+k |
|
|
F= |
F0 |
?1 |
?2 |
… |
?m |
?m+1 |
… |
?m+k |
Первый столбец - коэффициенты в целевой функции при базисных переменных. Второй столбец - базисные переменные. Третий столбец - свободные члены (hi?0). Самая верхняя строка - коэффициенты при целевой функции. Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет» [3, с. 81].
Для первой итерации:
(3.7)
- оценки они рассчитываются по формуле:
(3.8)
Индексная строка позволяет нам судить об оптимальности плана:
При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.
Для перехода ко второй итерации отыскиваем ключевой (главный) столбец и ключевую (главную) строку.
Ключевым столбцом является тот, в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.
Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца [1, с. 42].
На пересечении строки и столбца находится разрешающий элемент.
На этом этапе осуществляется к переходу к последующим итерациям.
Переход к итерациям:
- Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
- Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
- Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
- Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
- Остальные элементы переносятся по формуле:
(3.9)
4. Решение задачи симплекс-методом
4.1 Решение прямой задачи линейного программирования симплексным методом
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции:
F(X) = 6x1+6x2+8x3+5x4+4x5+5x6
при следующих условиях-ограничениях:
x1+x3+x5?1400000
x2+x4+x6?1200000
2x1+3x2+3x3+3x4+3x5+2x6?5600000
0.2x1+0.2x2+0.1x3+0.1x4+0.3x5+0.3x6?700000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x7. В 2-м неравенстве смысла (?) вводим базисную переменную x8. В 3-м неравенстве смысла (?) вводим базисную переменную x9. В 4-м неравенстве смысла (?) вводим базисную переменную x10.
1x1 + 0x2 + 1x3 + 0x4 + 1x5 + 0x6 + 1x7 + 0x8 + 0x9 + 0x10 = 1400000
0x1 + 1x2 + 0x3 + 1x4 + 0x5 + 1x6 + 0x7 + 1x8 + 0x9 + 0x10 = 1200000
2x1 + 3x2 + 3x3 + 3x4 + 3x5 + 2x6 + 0x7 + 0x8 + 1x9 + 0x10 = 5600000
0.2x1 + 0.2x2 + 0.1x3 + 0.1x4 + 0.3x5 + 0.3x6 + 0x7 + 0x8 + 0x9 + 1x10 = 700000
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
2 |
3 |
3 |
3 |
3 |
2 |
0 |
0 |
1 |
0 |
|
|
0.2 |
0.2 |
0.1 |
0.1 |
0.3 |
0.3 |
0 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x7, x8, x9, x10.
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0,1400000,1200000,5600000,700000)
Базисное решение называется допустимым, если оно неотрицательно.
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
|
|
x7 |
1400000 |
1 |
0 |
1 |
0 |
|
|
x8 |
1200000 |
0 |
1 |
0 |
1 |
|
|
x9 |
5600000 |
2 |
3 |
3 |
3 |
|
|
x10 |
700000 |
0.2 |
0.2 |
0.1 |
0.1 |
|
|
F(X0) |
0 |
-6 |
-6 |
-8 |
-5 |
|
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
|
|
3 |
2 |
0 |
0 |
1 |
0 |
|
|
0.3 |
0.3 |
0 |
0 |
0 |
1 |
|
|
-4 |
-5 |
0 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
|
|
x7 |
1400000 |
1 |
0 |
1 |
0 |
|
|
x8 |
1200000 |
0 |
1 |
0 |
1 |
|
|
x9 |
5600000 |
2 |
3 |
3 |
3 |
|
|
x10 |
700000 |
0.2 |
0.2 |
0.1 |
0.1 |
|
|
F(X1) |
0 |
-6 |
-6 |
-8 |
-5 |
|
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
min |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
1400000 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
- |
|
|
3 |
2 |
0 |
0 |
1 |
0 |
1866666.67 |
|
|
0.3 |
0.3 |
0 |
0 |
0 |
1 |
7000000 |
|
|
-4 |
-5 |
0 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x7 в план 1 войдет переменная x3. Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1.
На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
|
B |
x1 |
x2 |
x3 |
|
|
1400000 / 1 = 1400000 |
1 / 1 = 1 |
0 / 1 = 0 |
1 / 1 = 1 |
|
|
x4 |
x5 |
x6 |
x7 |
|
|
0 / 1 = 0 |
1 / 1 = 1 |
0 / 1 = 0 |
1 / 1 = 1 |
|
|
x8 |
x9 |
x10 |
|
|
0 / 1 = 0 |
0 / 1 = 0 |
0 / 1 = 0 |
|
После преобразований получаем новую таблицу:
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
|
|
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
x8 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
x9 |
1400000 |
-1 |
3 |
0 |
3 |
0 |
2 |
-3 |
0 |
1 |
0 |
|
|
x10 |
560000 |
0.1 |
0.2 |
0 |
0.1 |
0.2 |
0.3 |
-0.1 |
0 |
0 |
1 |
|
|
F(X1) |
11200000 |
2 |
-6 |
0 |
-5 |
4 |
-5 |
8 |
0 |
0 |
0 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
min |
|
|
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
- |
|
|
x8 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1200000 |
|
|
x9 |
1400000 |
-1 |
3 |
0 |
3 |
0 |
2 |
-3 |
0 |
1 |
0 |
466666.67 |
|
|
x10 |
560000 |
0.1 |
0.2 |
0 |
0.1 |
0.2 |
0.3 |
-0.1 |
0 |
0 |
1 |
2800000 |
|
|
F(X2) |
11200000 |
2 |
-6 |
0 |
-5 |
4 |
-5 |
8 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 2 войдет переменная x2. Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x9 плана 1 на разрешающий элемент РЭ=3.
На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
|
B |
x1 |
x2 |
x3 |
|
|
1400000 / 3 = 466666.67 |
-1 / 3 = -0.33 |
3 / 3 = 1 |
0 / 3 = 0 |
|
|
x4 |
x5 |
x6 |
x7 |
|
|
3 / 3 = 1 |
0 / 3 = 0 |
2 / 3 = 0.67 |
-3 / 3 = -1 |
|
|
x8 |
x9 |
x10 |
|
|
0 / 3 = 0 |
1 / 3 = 0.33 |
0 / 3 = 0 |
|
После преобразований получаем новую таблицу:
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
|
|
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
x8 |
733333.33 |
0.33 |
0 |
0 |
0 |
0 |
0.33 |
1 |
1 |
-0.33 |
0 |
|
|
x2 |
466666.67 |
-0.33 |
1 |
0 |
1 |
0 |
0.67 |
-1 |
0 |
0.33 |
0 |
|
|
x10 |
466666.67 |
0.17 |
0 |
0 |
-0.1 |
0.2 |
0.17 |
0.1 |
0 |
-0.0667 |
1 |
|
|
F(X2) |
14000000 |
0 |
0 |
0 |
1 |
4 |
-1 |
2 |
0 |
2 |
0 |
Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai6 и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (0.67) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
|
|
x8 |
733333.33 |
0.33 |
0 |
0 |
0 |
0 |
|
|
x2 |
466666.67 |
-0.33 |
1 |
0 |
1 |
0 |
|
|
x10 |
466666.67 |
0.17 |
0 |
0 |
-0.1 |
0.2 |
|
|
F(X3) |
14000000 |
0 |
0 |
0 |
1 |
4 |
|
x6 |
x7 |
x8 |
x9 |
x10 |
min |
|
|
0 |
1 |
0 |
0 |
0 |
- |
|
|
0.33 |
1 |
1 |
-0.33 |
0 |
2200000 |
|
|
0.67 |
-1 |
0 |
0.33 |
0 |
700000 |
|
|
0.17 |
0.1 |
0 |
-0.0667 |
1 |
2800000 |
|
|
-1 |
2 |
0 |
2 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x2 в план 3 войдет переменная x6. Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x2 плана 2 на разрешающий элемент РЭ=0.67.
На месте разрешающего элемента в плане 3 получаем 1. В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
|
B |
x1 |
x2 |
|
|
466666.67 / 0.67 = 700000 |
-0.33 / 0.67 = -0.5 |
1 / 0.67 = 1.5 |
|
|
x3 |
x4 |
x5 |
x6 |
|
|
0 / 0.67 = 0 |
1 / 0.67 = 1.5 |
0 / 0.67 = 0 |
0.67 / 0.67 = 1 |
|
|
x7 |
x8 |
x9 |
x10 |
|
|
-1 / 0.67 = -1.5 |
0 / 0.67 = 0 |
0.33 / 0.67 = 0.5 |
0 / 0.67 = 0 |
|
После преобразований получаем новую таблицу:
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
|
|
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
x8 |
500000 |
0.5 |
-0.5 |
0 |
-0.5 |
0 |
0 |
1.5 |
1 |
-0.5 |
0 |
|
|
x6 |
700000 |
-0.5 |
1.5 |
0 |
1.5 |
0 |
1 |
-1.5 |
0 |
0.5 |
0 |
|
|
x10 |
350000 |
0.25 |
-0.25 |
0 |
-0.35 |
0.2 |
0 |
0.35 |
0 |
-0.15 |
1 |
|
|
F(X3) |
14700000 |
-0.5 |
1.5 |
0 |
2.5 |
4 |
0 |
0.5 |
0 |
2.5 |
0 |
Итерация №3.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (0.5) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
min |
|
|
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1400000 |
|
|
x8 |
500000 |
0.5 |
-0.5 |
0 |
-0.5 |
0 |
0 |
1.5 |
1 |
-0.5 |
0 |
1000000 |
|
|
x6 |
700000 |
-0.5 |
1.5 |
0 |
1.5 |
0 |
1 |
-1.5 |
0 |
0.5 |
0 |
- |
|
|
x10 |
350000 |
0.25 |
-0.25 |
0 |
-0.35 |
0.2 |
0 |
0.35 |
0 |
-0.15 |
1 |
1400000 |
|
|
F(X4) |
14700000 |
-0.5 |
1.5 |
0 |
2.5 |
4 |
0 |
0.5 |
0 |
2.5 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x8 в план 4 войдет переменная x1. Строка, соответствующая переменной x1 в плане 4, получена в результате деления всех элементов строки x8 плана 3 на разрешающий элемент РЭ=0.5. На месте разрешающего элемента в плане 4 получаем 1. В остальных клетках столбца x1 плана 4 записываем нули. Таким образом, в новом плане 4 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
|
B |
x1 |
x2 |
|
|
500000 / 0.5 = 1000000 |
0.5 / 0.5 = 1 |
-0.5 / 0.5 = -1 |
|
|
x3 |
x4 |
x5 |
x6 |
|
|
0 / 0.5 = 0 |
-0.5 / 0.5 = -1 |
0 / 0.5 = 0 |
0 / 0.5 = 0 |
|
|
x7 |
x8 |
x9 |
x10 |
|
|
1.5 / 0.5 = 3 |
1 / 0.5 = 2 |
-0.5 / 0.5 = -1 |
0 / 0.5 = 0 |
После преобразований получаем новую таблицу:
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
|
|
x3 |
400000 |
0 |
1 |
1 |
1 |
1 |
0 |
-2 |
-2 |
1 |
0 |
|
|
x1 |
1000000 |
1 |
-1 |
0 |
-1 |
0 |
0 |
3 |
2 |
-1 |
0 |
|
|
x6 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
x10 |
100000 |
0 |
0 |
0 |
-0.1 |
0.2 |
0 |
-0.4 |
-0.5 |
0.1 |
1 |
|
|
F(X4) |
15200000 |
0 |
1 |
0 |
2 |
4 |
0 |
2 |
1 |
2 |
0 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
|
|
x3 |
400000 |
0 |
1 |
1 |
1 |
1 |
0 |
-2 |
-2 |
1 |
0 |
|
|
x1 |
1000000 |
1 |
-1 |
0 |
-1 |
0 |
0 |
3 |
2 |
-1 |
0 |
|
|
x6 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
x10 |
100000 |
0 |
0 |
0 |
-0.1 |
0.2 |
0 |
-0.4 |
-0.5 |
0.1 |
1 |
|
|
F(X5) |
15200000 |
0 |
1 |
0 |
2 |
4 |
0 |
2 |
1 |
2 |
0 |
Оптимальный план можно записать так:
x3 = 400000 акров земли;
x1 = 1000000 акров земли;
x6 = 1200000 акров земли.
F(X) = 8 * 400000 + 6 * 1000000 + 5 * 1200000 = 15200000
Таким образом, максимальный урожай составит 15200000.
Проведем анализ оптимального плана. В оптимальный план вошла дополнительная переменная x10. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 4-го вида в количестве 100000.
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 1> 0 в столбце x2 означает, что использование x2 - не выгодно.
Значение 0 в столбце x3 означает, что использование x3 - выгодно.
Значение 2> 0 в столбце x4 означает, что использование x4 - не выгодно.
Значение 4> 0 в столбце x5 означает, что использование x5 - не выгодно.
Значение 0 в столбце x6 означает, что использование x6 - выгодно.
Значение 2 в столбце x7 означает, что теневая цена (двойственная оценка) равна 2.
Значение 1 в столбце x8 означает, что теневая цена (двойственная оценка) равна 1.
Значение 2 в столбце x9 означает, что теневая цена (двойственная оценка) равна 2.
4.2 Составление и решение двойственной задачи
Построим двойственную задачу по следующим правилам.
1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Расширенная матрица A:
|
1 |
0 |
1 |
0 |
1 |
0 |
1400000 |
|
|
0 |
1 |
0 |
1 |
0 |
1 |
1200000 |
|
|
2 |
3 |
3 |
3 |
3 |
2 |
5600000 |
|
|
0.2 |
0.2 |
0.1 |
0.1 |
0.3 |
0.3 |
700000 |
|
|
6 |
6 |
8 |
5 |
4 |
5 |
0 |
Транспонированная матрица AT:
|
1 |
0 |
2 |
0.2 |
6 |
|
|
0 |
1 |
3 |
0.2 |
6 |
|
|
1 |
0 |
3 |
0.1 |
8 |
|
|
0 |
1 |
3 |
0.1 |
5 |
|
|
1 |
0 |
3 |
0.3 |
4 |
|
|
0 |
1 |
2 |
0.3 |
5 |
|
|
1400000 |
1200000 |
5600000 |
700000 |
0 |
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Неравенства, соединенные стрелочками (-), называются сопряженными.
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Выясним экономический смысл двойственной задачи. Заметим, что каждое слагаемое в левой части ограничений должно измеряться в тех же единицах, что и правая.
Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов.
Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj:
y1+2y3+0.2y4?6
y2+3y3+0.2y4?6
y1+3y3+0.1y4?8
y2+3y3+0.1y4?5
y1+3y3+0.3y4?4
y2+2y3+0.3y4?5
1400000y1+1200000y2+5600000y3+700000y4 > min
y1 ? 0, y2 ? 0, y3 ? 0, y4 ? 0
|
Исходная задача I |
Двойственная задача II |
||
|
x1 ? 0 |
- |
y1+2y3+0.2y4?6 |
|
|
x2 ? 0 |
- |
y2+3y3+0.2y4?6 |
|
|
x3 ? 0 |
- |
y1+3y3+0.1y4?8 |
|
|
x4 ? 0 |
- |
y2+3y3+0.1y4?5 |
|
|
x5 ? 0 |
- |
y1+3y3+0.3y4?4 |
|
|
x6 ? 0 |
- |
y2+2y3+0.3y4?5 |
|
|
6x1+6x2+8x3+5x4+4x5+5x6 > max |
- |
1400000y1+1200000y2+5600000y3+700000y4 > min |
|
|
x1+x3+x5?1400000 |
- |
y1 ? 0 |
|
|
x2+x4+x6?1200000 |
- |
y2 ? 0 |
|
|
2x1+3x2+3x3+3x4+3x5+2x6?5600000 |
- |
y3 ? 0 |
|
|
0.2x1+0.2x2+0.1x3+0.1x4+0.3x5+0.3x6?700000 |
- |
y4 ? 0 |
Переменные yj называются допустимым решением двойственной задачи. Переменные yj называются оптимальными, если они допустимые и на них целевая функция достигает минимальное значения.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1
Оптимальный план двойственной задачи равен:
y1 = 2; y2 = 1; y3 = 2; y4 = 0.
Z(Y) = 1400000*2+1200000*1+5600000*2+700000*0 = 15200000
Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
5. Анализ модели на чувствительность
Проведем определение дефицитных и недефицитных (избыточных) ресурсов. Для этого используем вторую теорему двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
1*1000000 + 0*0 + 1*400000 + 0*0 + 1*0 + 0*1200000 =
= 1400000 = 1400000;
0*1000000 + 1*0 + 0*400000 + 1*0 + 0*0 + 1*1200000 =
= 1200000 = 1200000;
2*1000000 + 3*0 + 3*400000 + 3*0 + 3*0 + 2*1200000 =
= 5600000 = 5600000;
0.2*1000000 + 0.2*0 + 0.1*400000 + 0.1*0 + 0.3*0 + 0.3*1200000 =
= 600000 < 700000.
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3>0).
4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y4 = 0.
Неиспользованный экономический резерв ресурса 4 составляет 100000 (700000-600000).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
1*2 + 0*1 + 2*2 + 0.2*0 = 6 = 6
0*2 + 1*1 + 3*2 + 0.2*0 = 7 > 6
1*2 + 0*1 + 3*2 + 0.1*0 = 8 = 8
0*2 + 1*1 + 3*2 + 0.1*0 = 7 > 5
1*2 + 0*1 + 3*2 + 0.3*0 = 8 > 4
0*2 + 1*1 + 2*2 + 0.3*0 = 5 = 5
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x2 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (7 - 6 = 1) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x3>0).
4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x4 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (7 - 5 = 2) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
5-ое ограничение выполняется как строгое неравенство, т.е. ресурс 5-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x5 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (8 - 4 = 4) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
6-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 6-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x6>0).
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Определим чувствительность решения к изменению коэффициентов целевой функции.
Так как любые изменения коэффициентов целевой функции оказывают влияние на оптимальность полученного ранее решения, то наша цель - найти такие диапазоны изменения коэффициентов в целевой функции (рассматривая каждый из коэффициентов отдельно), при которых оптимальные значения переменных остаются неизменными.
Пусть каждое значение параметра целевой функции изменится на ? сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:
3-ый параметр целевой функции может изменяться в пределах:
?c3- = min [yk/d3k] для d3k>0.
?c3+ = |max [yk/d3k]| для d3k<0.
где в знаменателе коэффициенты столбцов свободных переменных в оптимальном плане (коэффициенты структурных сдвигов, элементы обратной матрицы к базису оптимального плана).
Таким образом, 3-параметр может быть уменьшен на 2 или увеличен на 0.5. Интервал изменения равен:
(c3 - ?c3-; c3 + ?c3+)
[8-2; 8+0.5] = [6;8.5]
Если значение c3 будет лежать в данном интервале, то оптимальный план не изменится.
1-ый параметр целевой функции может изменяться в пределах:
?c1- = min [yk/d1k] для d1k>0.
?c1+ = |max [yk/d1k]| для d1k<0.
Таким образом, 1-параметр может быть уменьшен на 0.5 или увеличен на 2.
Интервал изменения равен:
(c1 - ?c1-; c1 + ?c1+)
[6-0.5; 6+2] = [5.5;8]
Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится.
6-ый параметр целевой функции может изменяться в пределах:
?c6- = min [yk/d6k] для d6k>0.
?c6+ = |max [yk/d6k]| для d6k<0.
Таким образом, 6-параметр может быть уменьшен на 1 или увеличен на 0. Интервал изменения равен:
(c6 - ?c6-; c6 + ?c6+)
[5-1; 5+0] = [4;5]
Если значение c6 будет лежать в данном интервале, то оптимальный план не изменится.
Определим чувствительность решения к изменению запасов сырья.
Из теоремы об оценках известно, что колебание величины bi приводит к увеличению или уменьшению f(X).
Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных уi в оптимальном плане соответствующей двойственной задачи остаются неизменными.
Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, в которых оптимальный план двойственной задачи не менялся бы.
Найдем интервалы устойчивости ресурсов.
1-ый запас может изменяться в пределах:
?b1- = min [xk/dk1] для dk1>0.
?b1+ = |max [xk/dk1]| для dk1<0.
Таким образом, 1-ый запас может быть уменьшен на 333333.33 или увеличен на 200000. Интервал изменения равен:
(b1 - ?b1-; b1 + ?b1+)
[1400000-333333.33; 1400000+200000] = [1066666.67;1600000]
2-ый запас может изменяться в пределах:
?b2- = min [xk/dk2] для dk2>0.
?b2+ = |max [xk/dk2]| для dk2<0.
Таким образом, 2-ый запас может быть уменьшен на 500000 или увеличен на 200000.
Интервал изменения равен:
(b2 - ?b2-; b2 + ?b2+)
[1200000-500000; 1200000+200000] = [700000;1400000]
3-ый запас может изменяться в пределах:
?b3- = min [xk/dk3] для dk3>0.
?b3+ = |max [xk/dk3]| для dk3<0.
Таким образом, 3-ый запас может быть уменьшен на 400000 или увеличен на 1000000. Интервал изменения равен:
(b3 - ?b3-; b3 + ?b3+)
[5600000-400000; 5600000+1000000] = [5200000;6600000]
Нижняя граница для: ?b-4
?b-4 = min[xk/dk4] для dk4>0.
Таким образом, 4-ый запас может быть уменьшен на 100000.
4-ый вид ресурса в оптимальном плане недоиспользован, является недефицитным. Увеличение данного ресурса приведет лишь к росту его остатка. При этом структурных изменений в оптимальном плане не будет, так как двойственная оценка y4 = 0. Другими словами, верхняя граница b+4 = +?. Интервал изменения равен:
(b4 - ?b4-; ?)
[700000-100000; +?] = [600000;+?]
В оптимальный план не вошла основная переменная x4, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок:
x4 может изменяться в пределах:
-1000000 ? ?b4 ? 400000
[700000-400000; 700000] = [300000;700000].
Заключение
В ходе выполнения работы было произведено построение математической модели задачи.
В теоретической части курсовой работы раскрыты теоретические положения использования симплекс-метода для решения задачи линейного программирования. Из теории хотелось бы выделить, что линейность предполагает наличие двух свойств - пропорциональности и аддитивности. Также был описан общий алгоритм симплекс-метода.
В расчетной части работы проведено решение поставленной задачи и определен необходимый план выращивания культур, который дает максимальный урожай.
Также была сформулирована и решена двойственная задача. Проведено определение дефицитных и недефицитных (избыточных) ресурсов. При этом использовалась вторая теорема двойственности.
Была определена чувствительность решения к изменению коэффициентов целевой функции.
Так как любые изменения коэффициентов целевой функции оказывают влияние на оптимальность полученного ранее решения, то цель - найти такие диапазоны изменения коэффициентов в целевой функции (рассматривая каждый из коэффициентов отдельно), при которых оптимальные значения переменных остаются неизменными.
Таким образом, можно утверждать, что все поставленные задачи выполнены.
Список библиографических источников
1. Айвазян С.А., Иванова С.С. Эконометрика. Краткий курс: учеб. пособие / С.А. Айвазян, С.С. Иванова. - М.: Маркет ДС, 2007. - 104 с.
2. Анфилатов B.C., Емельянов А.А., Кукушкин А.А. и др. Системный анализ в управлении: учеб.пособие /под ред. А.А. Емельянова. М.: Финансы и статистика, 2002. - 368 с.
3. Афоничкин А.И., Михаленко Д.Г. Управленческие решения в экономических системах: Учебник для вузов. - СПб.: Питер, 2009.
4. Баранов В.В. Процессы принятия управляющих решений, мотивированных интересами. М.: ФИЗМАТЛИТ, 2005. - 296 с.
5. Бородич С.А. Вводный курс эконометрики: Учебное пособие. - Мн.: БГУ, 2000. - 354 с.
6. Бывшев В.А. Эконометрика: учеб. пособие / В.А. Бывшев. - М.: Финансы и статистика, 2008. - 480 с.
7. Вертакова Ю.В. и др. Управленческие решения: разработка и выбор: учеб.пособие. М.: КНОРУС, 2005. - 352 с.
8. Гапоненко Т.В. Управленческие решения: учеб. пособие / Т.В. Гапоненко. Ростов н/Д: Феникс, 2008. - 284 с.
9. Голубков Е.П. Технология принятия управленческих решений - М.: Издат. «Дело и Сервис», 2005.
10. Заичкин Н.И. Экономико-математические модели и методы принятия решений в управлении производством. /Учебное пособие. - М.: ГУУ, 2000.
11. Зайцев М.Г. Методы оптимизации управления для менеджеров: компьютерно-ориентированный подход: учеб. пособие / М. Г. Зайцев [3-е изд., испр.] - М: Дело, 2007.
12. Карданская, Н.Л. Принятия управленческого решения / Н.Л. Карданская. - М.: ЮНИТИ, 1999.
13. Кодин, В.Н. Как работать над управленческим решением. Системный подход / В.II. Кодин, С.В. Литягина. - М.: КиоРус, 2010.
14. Колпаков В.М. Теория и практика принятия управленческих решений: учеб. пособие. К.: МАУП, 2004. - 504 с.
15. Литвак Б. Г. Разработка управленческого решения: учебник. М.: Дело, 2008. - 392 с.
16. Логинов, В. Н. Управленческие решения: модели и методы / B. Н. Логинов. - М.: Альфа-Пресс, 2011.
17. Мадера А.Г. Моделирование и принятие решений в менеджменте: Руководство для будущих топ-менеджеров. - М.: Издательство ЛКИ, 2010.
18. Орлов А.И. Теория принятия решений: учеб.пособие. М.: Экзамен, 2005. - 656 с.
19. Первозванский А.А. Математические модели в управлении производством. - М.: Изд-во «Наука», 1975.
20. Подиновский В.В., Ногин В.Д. Парето - оптимальные решения многокритериальных задач. - М.: Наука, 1982.
21. Просветов, Г.И. Управленческие решения: задачи и решения / Г.И. Просветов. - М.: Альфа-Пресс, 2009.
22. Смирнов Э.А. Управленческие решения. М.: ИНФРА-М, 2001. - 264 с.
23. Тебекин, А.В. Менеджмент организации / А.В. Тебекин, Б.С. Касаев. - М.: КноРус, 2011.
24. Управление организацией: учебник / под ред. А.Г. Поршнева, 3.П. Румянцевой, Н.А. Саломатина. - 2-е изд., перераб. и доп. - М.: ИНФРА-М, 1998.
25. Управленческие решения: технология, методы и инструменты / С.В. Петухова, П.В. Шеметов, В.В. Радионов. Л.Ы. Никифорова. - М.: Омега-Л, 2011.
Размещено на Allbest.ru
Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016
