Реализация симплекс-метода в случае отрицательных свободных членов
Линейное программирование как наука о методах исследования и отыскания экстремумов линейной функции, на неизвестные которой наложены линейные ограничения. Особенности решения задач симплексным методом. Порядок решения задач с помощью симплексных таблиц.
Рубрика | Экономико-математическое моделирование |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 13.10.2012 |
Размер файла | 152,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Курсовая работа по предмету:
«Математическое моделирование»
Реализация симплекс-метода в случае отрицательных свободных членов
Содержание
- Введение
- Задачи линейного программирования
- Решение задач симплексным методом
- Решение задач с помощью симплексных таблиц
- Выводы и заключения
- Список используемых источников информации
Введение
Линейное программирование сейчас широко используется в экономике, для решения производственных задач, выбора стратегии управления различными экономическими процессами и для другого. Поэтому решение подобных задач весьма актуально на сегодняшний день.
Но целью данной работы является не столько решение задач линейного программирования, сколько реализация этого решения с помощью ЭВМ. Конкретно, в этой работе разбирается реализация симплексного метода решения и поиска первоначального допустимого базисного решения.
Прилагающаяся к работе программа имеет цель научить пользователя на примере решать задачи линейного программирования с помощью симплексных таблиц.
Математическое моделирование как инструмент познания завоевывает все новые и новые позиции в различных областях деятельности человека. Оно становится главенствующим направлением в проектировании и исследовании новых систем, анализе свойств существующих систем, выборе и обосновании оптимальных условий их функционирования и т.п.
Изучение математического моделирования открывает широкие возможности для осознания связи информатики с математикой и другими науками. Абстрактное моделирование с помощью компьютеров - вербальное, информационное, математическое - в наши дни стало одной из информационных технологий в познавательном плане исключительно мощной.
Общее в моделях то, что во всех случаях модель в определённом смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования.
Модель - это материальный или идеальный объект, который строится для изучения исходного объекта (оригинала) и который отражает наиболее важные качества и параметры оригинала.
Задачи линейного программирования
Линейное программирование (ЛП) - наука о методах исследования и отыскания экстремумов линейной функции, на неизвестные которой наложены линейные ограничения.
То есть, задача линейного программирования, это отыскание минимального или максимального значения линейной функции с учётом системы из линейных уравнений-ограничений. Всё вместе это даёт математическую модель, какого-либо экономического процесса.
Экономико-математическая модель - это математическое описание экономического процесса или объекта. Такие модели используются для исследований и анализа экономических процессов. Реализуя их обработку на ЭВМ, мы получаем выигрыш во времени и средствах, так как проведение опытов, как правило, более трудоёмкий и дорогостоящий процесс, кроме того, не всегда возможный. Не буду здесь вдаваться в теорию моделирования, скажу лишь, что именно реализация исследования экономических процессов с помощью ЭВМ для нас и представляет интерес, а проявляется это в машинном решении задач линейного программирования, которые в свою очередь и являются экономико-математическими моделями.
Все задачи линейного программирования можно разделить на следующие группы:
· Задачи об использовании ресурсов, сырья, планирования производства
· Задачи составления рациона
· Задачи об использовании мощностей, загрузке оборудования
· Задачи о раскрое материалов
· Транспортные задачи
Их рассмотрение здесь не приведено, так как не является необходимым для данного проекта.
Но надо представлять общую задачу линейного программирования (ОЗЛП), так как для составления алгоритма необходимо понимать математический смысл решения задачи. Ниже, приведено математическое описание общего вида задачи линейного программирования.
Дана система из m линейных уравнений и неравенств с n переменными:
и линейная функция
Необходимо найти такое решение (план) системы
где
при котором линейная функция F (2.2) принимает оптимальное), есть максимальное или минимальное в зависимости от задачи) значение. При этом система (2.1) - система ограничений, а функция F (2.2) - целевая функция (функция цели).
Геометрически область допустимых решений такой задачи можно представить как многогранник в n мерном пространстве (2.5).
Пример геометрического представления области допустимых решений задачи, где F - линия целевой функции, F=0 начальное положение функции, F=Fmax оптимальное положение функции, A, B, C, D, E - вершины многоугольника.
Причём, как правило, оптимальное решение это одна из его вершин. А поиск оптимума выражается в переходе от одной вершины к другой и выборе оптимальной.
Решение задач симплексным методом
В основе симплексного метода лежит перебор вершин многогранника области допустимых решений с учётом изменений функции цели. То есть при переходе от одной вершине к другой надо, чтобы функция цели принимала лучшее (или не худшее) значение, чем на предыдущем шаге. Тем самым число перебираемых вершин сокращается, и оптимум находится быстрее.
Для решения задач симплексным методом надо освоить три основных элемента:
· способ определения первоначального допустимого базисного решения
· правило перехода к лучшему решению
· критерий проверки оптимальности найденного решения
Кроме того, для решения задачи симплексным методом, она должна быть представлена в канонической форме (все неравенства должны быть заменены уравнениями). Для этого, если в неравенстве стоит знак "" или "", надо ввести дополнительную переменную в левую часть уравнения, со знаком "-" при её коэффициенте, иначе со знаком "+". И так заменяются все неравенства.
Далее, на примере, показано как ищется оптимум в симплексной задаче, в алгебраическом виде.
Дана следующая функция цели:
при ограничениях
Надо найти максимум в этой задачи.
Сначала надо с помощью дополнительных переменных привести задачу к каноническому виду:
Далее надо выбрать m - 4 основных переменных. Они выбираются по следующему правилу: каждая из этих переменных должна входить в какое-либо уравнение один раз, при этом не должно быть такого уравнения, где не было бы ни одной из них (определитель этих переменных не должен быть нулевым). Исходя из этого правила, нам подходят x3, x4, x5, x6. Так как их знаки совпадают со знаком соответствующего свободного члена уравнения, то данное решение системы является допустимым, иначе надо искать первоначальное допустимое решение (смотрите следующий подраздел). Далее выражаем основные переменные через неосновные.
Первое полученное решение выглядит как X1=(0,0,18,16,5,21) - цифры это свободные члены в уравнении, где находится основная переменная (все переменные идут по порядку), если данная переменная неосновная, то пишем ноль. Так как в этом решении нет отрицательных компонент оно допустимо, о чём говорилось ранее. Но, глядя на функцию цели (2.6) мы видим, что в ней есть положительные переменные, а значит, её значение можно увеличить (за счёт любой из них). Выбираем для её увеличения, например, x2.
Сперва, надо определить границу роста этой переменной в каждом уравнении, при этом надо следовать следующим правилам:
· если переменной нет в уравнении, то граница роста равна бесконечности
· если свободный член и коэффициент при этой переменной в уравнении имеют одинаковый знак, то граница так же равна бесконечности
· если свободный член отсутствует, а коэффициент больше или равен нулю, то граница так же равна бесконечности
· иначе (знаки при свободном члене и коэффициенте при переменной разные) граница равна частному от деления свободного члена на коэффициент при переменной
В данном примере получаем: x2=min{18/3; 16/1; 5/1; ?}=5, выбирается самая маленькая граница, она и определяет разрешающее уравнение. В данном случае это третье уравнение. Теперь в разрешающем уравнении переводим x2 в основные переменные (а значит x5 в дополнительные). И выражаем x2 во всех уравнениях через его значение (уравнение).
Второе базисное решение так же допустимо и равно X2=(0; 5; 3; 11; 0; 21) .
Теперь, надо выразить функцию через неосновные переменные.
Как видите, есть ещё положительная переменная x1, а значит, текущее значение функции (F=15) можно увеличить. Повторяем все шаги, в итоге у вас должно получится значение 24. Из вышесказанного можно сделать вывод, что максимум функции цели достигнут тогда, когда в её уравнении нет ни одной положительной переменной, для минимума наоборот (задача на минимум решается так же, но надо убирать не положительные, а отрицательные переменные из уравнения функции).
Вот так выглядит решение задачи симплексным методом. Но есть особые случаи симплексного метода.
Неединственность оптимального решения (альтернативный оптимум). Она появляется, когда после выражения функции через неосновные переменные одна из переменных становится нулевой, а другая удовлетворяет условию оптимальности. То есть оптимум найден, но можно менять нулевую переменную, хотя улучшения функции это не даст. Графически это представляется как совпадение линии функции с линией многогранника области допустимых решений.
Вырожденное базисное решение. Это когда одна из основных переменных равна нулю. После такого решения следующее, может не улучшить функцию, а лишь сменить набор основных переменных. В таких случаях (хотя крайне редко) возможно зацикливание, то есть перебор одних и тех же решений.
Отсутствие конечного оптимума. Это когда на очередном шаге решения все границы роста равны бесконечности или минус бесконечности. Графически это выглядит, как отсутствие какое-то стороны многогранника области допустимых решений и функция может двигаться в эту сторону до бесконечности.
Эти особые случаи тоже надо учитывать при поиске оптимума в симплексной задаче.
Симплекс-метод, решение задачи с начальным базисом
1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ? ").
Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:
Эта система является системой с базисом (базис s1, s2, s3, каждая из них входит только в одно уравнение системы с коэффициентом 1), x1 и x2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами:
-система ограничений должна быть системой уравнений с базисом;
-свободные члены всех уравнений в системе должны быть неотрицательны.
Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z - строке есть отрицательные коэффициенты.
Симплекс-метод итерация 0
БП |
x1 |
x2 |
s1 |
s2 |
s3 |
Решение |
Отношение |
|
z |
-4 |
-6 |
0 |
0 |
0 |
0 |
- |
|
s1 |
2 |
1 |
1 |
0 |
0 |
64 |
64/1=64 |
|
s2 |
1 |
3 |
0 |
1 |
0 |
72 |
72/3=24 |
|
s3 |
0 |
1 |
0 |
0 |
1 |
20 |
20/1=20 |
Для улучшения решения перейдем к следующей итерации симплекс-метода, получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) - в начальной итерации симплекс-метода это столбец x2 (коэффициент -6).
Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») - в начальной итерации это строка s3 (коэффициент 20).
Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x2 заменит в базисе s3. Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.
Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).
1)Вычисление строки х2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s3 таблицы "Итерация 0" будет совпадать со строкой х2 таблицы "Итерация 1". Строку x2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:
2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х2 выделены красным цветом.
3) Вычисление строки s1 таблицы "Итерация 1". На месте 1 в s1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х2 получен необходимый 0.
4) Вычисление строки s2 таблицы "Итерация 1". На месте 3 в s2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х2 получен нужный 0. Столбец х2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.
Строки таблицы «Итерация 1» получаем по следующему правилу:
Новая строка = Старая строка - (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).
Например для z-строки имеем:
Старая z-строка (-4 -6 0 0 0 0)
-(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120)
=Новая z-строка (-4 0 0 0 6 120).
Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.
симплекс-метод итерация 1
БП |
x1 |
x2 |
s1 |
s2 |
s3 |
Решение |
Отношение |
|
z |
-4 |
0 |
0 |
0 |
6 |
120 |
- |
|
s1 |
2 |
0 |
1 |
0 |
-1 |
44 |
44/2=22 |
|
s2 |
1 |
0 |
0 |
1 |
-3 |
12 |
12/1=12 |
|
x2 |
0 |
1 |
0 |
0 |
1 |
20 |
- |
Разрешающий столбец х1, разрешающая строка s2, s2 выходит из базиса, х1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.
симплекс-метод итерация 2
БП |
x1 |
x2 |
s1 |
s2 |
s3 |
Решение |
Отношение |
|
z |
0 |
0 |
0 |
4 |
-6 |
168 |
- |
|
s1 |
0 |
0 |
1 |
-2 |
5 |
20 |
20/5=4 |
|
x1 |
1 |
0 |
0 |
1 |
-3 |
12 |
- |
|
x2 |
0 |
1 |
0 |
0 |
1 |
20 |
20/1=20 |
Разрешающий столбец s3, разрешающая строка s1, s1 выходит из базиса, s3 входит в базис
симплекс-метод итерация 3
БП |
x1 |
x2 |
s1 |
s2 |
s3 |
Решение |
Отношение |
|
z |
0 |
0 |
6/5 |
8/5 |
0 |
192 |
- |
|
s3 |
0 |
0 |
1/5 |
-2/5 |
1 |
4 |
- |
|
x1 |
1 |
0 |
3/5 |
-1/5 |
0 |
24 |
- |
|
x2 |
0 |
1 |
-1/5 |
2/5 |
0 |
16 |
- |
В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение
x1 = 24, x2 = 16, zmax = 192.
Симплекс-метод, решение задачи с искусственным базисом
2) Решим симплекс-методом задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ? " или " = ").
Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х3 ? 0 и х4 ? 0 получим:
Система ограничений предлагает только одну допустимую базисную переменную x4, только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R1 ? 0 и R2 ? 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R1, R2 и x4. Получили, так называемую, М-задачу:
Данная система является системой с базисом, в которой R1, R2 и x4 базисные переменные, а x1, x2 и x3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:
симплекс-метод итерация 0
БП |
x1 |
x2 |
x3 |
R1 |
R2 |
x4 |
Решение |
Отношение |
|
z |
-4 |
-16 |
0 |
0 |
0 |
0 |
0 |
- |
|
R1 |
3 |
4 |
-1 |
1 |
0 |
0 |
6 |
6/4=3/2 |
|
R2 |
1 |
3 |
0 |
0 |
1 |
0 |
3 |
3/3=1 |
|
x4 |
2 |
1 |
0 |
0 |
0 |
1 |
4 |
4/1=4 |
|
Оценка |
-4 |
-7 |
1 |
-1 |
-1 |
0 |
- |
- |
В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х2, он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации симплекс-метода переменная х2 из свободной перейдет в базисную, а переменная R2 из базисной - в свободную. Запишем следующую симплекс-таблицу:
симплекс-метод итерация 1
БП |
x1 |
x2 |
x3 |
R1 |
R2 |
x4 |
Решение |
Отношение |
|
z |
4/3 |
0 |
0 |
0 |
16/30 |
0 |
16 |
- |
|
R1 |
5/3 |
0 |
-1 |
1 |
-4/3 |
0 |
2 |
6/5 |
|
x2 |
1/3 |
1 |
0 |
0 |
1/3 |
0 |
1 |
3 |
|
x4 |
5/3 |
0 |
0 |
0 |
-1/3 |
1 |
3 |
9/5 |
|
Оценка |
-5/3 |
0 |
1 |
-1 |
4/3 |
0 |
- |
- |
Разрешающий столбец х1, разрешающая строка R1, R1 выходит из базиса, x1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:
симплекс-метод итерация 2
БП |
x1 |
x2 |
x3 |
R1 |
R2 |
x4 |
Решение |
Отношение |
|
z |
0 |
0 |
4/5 |
-4/5 |
32/5 |
0 |
72/5 |
- |
|
x1 |
1 |
0 |
-3/5 |
3/5 |
-4/5 |
0 |
6/5 |
- |
|
x2 |
0 |
1 |
1/5 |
-1/5 |
3/5 |
0 |
3/5 |
- |
|
x4 |
0 |
0 |
1 |
-1 |
1 |
1 |
1 |
- |
|
БП |
x1 |
x2 |
x3 |
R1 |
R2 |
x4 |
Решение |
Отношение |
Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R1, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, симплекс-методом получено оптимальное решение x1 = 6/5; x2 = 3/5; zmax = 72/5.
Решение задач с помощью симплексных таблиц
В этом разделе описано использование симплексных таблиц для решения задач. Использование симплексных таблиц весьма удобно для ручного расчёта задач. Для заполнения первой симплексной таблицы надо привести систему к каноническому виду. Затем если надо ищется первоначальное допустимое решение или задачу надо решать M-методом. Кроме того, систему представляют в расширенном виде.
Обратите внимание, что коэффициенты при переменных в функции меняют знак! Все введённые переменные имеют тот же знак, что и свободные члены иначе надо использовать M-метод (или заранее отыскать ПДБР). Далее эти данные заносятся в первую симплексную таблицу, общий вид которой представлен ниже.
Базис |
Свободный член |
Переменные |
Оценочное отношение |
|||||||
x1 |
... |
xj |
... |
xs |
... |
xn+m |
||||
x1 |
b1 |
a11 |
... |
a1j |
... |
a1s |
... |
a1n+m |
g1 |
|
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
xi |
bi |
ai1 |
... |
aij |
... |
ais |
... |
ain+m |
gi |
|
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
xq |
bq |
aq1 |
... |
aqj |
... |
aqs |
... |
aqn+m |
gq |
|
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
xm |
bm |
am1 |
... |
amj |
... |
ams |
... |
amn+m |
gm |
|
F |
c0 |
c1 |
... |
cj |
... |
cs |
... |
cn+m |
MAX/MIN |
Теперь, поясним, что есть что. Каждая строка - это уравнение в расширенной системе (смотрите формулу 2.19). В столбце "Базис" перечисляются все базисные (основные) переменные, их число равно числу уравнений в системе ограничений. Следующий столбец, "Свободные член" заполняется значениями свободных членов уравнения. В самую верхнюю строку (под надписью "переменные") выписываются все переменные. Самая нижняя строка, начиная с c1, заполняется значениями коэффициентов при переменных, которые написаны вверху таблицы, из уравнения функции (с обратным знаком, как в расширенной системе), если в уравнении функции такой переменной нет, то пишем ноль. Ячейки "a" заполняются так. Если вверху столбца написана основная переменная, то на пересечении этого столбца со строкой, в которой написана та же переменная, ставим 1, во все остальные ячейки столбца пишем 0. Если же вверху столбца неосновная переменная, то в ячейки записываются её коэффициенты из соответствующего уравнения, если её нет в этом уравнении, то пишем 0. В ячейку c0, на первом шаге просто пишем ноль.
Далее надо провести проверку на оптимальность решения. Это делается легко, если задача на минимум то решение оптимально, если все c, кроме c0, имеют отрицательные знаки, если же задача на максимум, то когда положительные знаки.
Если решение не оптимально, ищем разрешающий столбец (индекс s), он определяется коэффициентом при переменной в уравнении функции, то есть нижней строкой, начиная c1. Для задачи на минимум это любой столбец, где c максимальный, положительный элемент, а для задачи на максимум, минимальный, отрицательный элемент. Далее проводим расчёт оценочных отношений и заполняем соответствующий столбец. Расчет производится в соответствии со следующим правилом:
если bi и ais имеют разные знаки, то gi равно бесконечности
если bi равно нулю и ais меньше нуля, то gi равно бесконечности
если bi равно нулю и ais больше нуля, то gi равно нулю
если ais равно нулю, то gi равно бесконечности
иначе gi равно частному от деления bi на ais
После того, как столбец с g заполнен. Выбирается разрешающая строка (индекс q). Это строка, в которой самое минимальное оценочное отношение (но не ноль и не бесконечность). На пересечении разрешающих строки и столбца находится разрешающий элемент - aqs.
Теперь составляется новая таблица. В столбце "Базис" вместо старой переменной - xq пишем новую - xs. Опять на пересечении основных переменных ставим 1, а остальные клетки в столбцах основных переменных заполняем нулями (включая нижнюю строку). Далее, новую строку с номером q получаем путём деления старой строки на разрешающий элемент (aqs), при этом считаем только пустые клетки (те которые в столбцах неосновных переменных).
Остальные клетки считаем по следующим формулам:
новая aij ровна старой aij-ais*aqj/aqs
новая bi ровна старой bi-ais*bq/aqs
новая cj ровна старой cj-cs*aqj/aqs
Клетка c0 заполняется как старая c0-cs*gq.
Затем снова проверяем решение на оптимальность, если оно не оптимально ищем разрешающий элемент и так далее, пока не найдём оптимума.
Но возможны и другие ситуации - особые случаи симплексного метода. Например, задача не имеет решения, если все оценочные отношения gi равны нулям и бесконечностям. Кроме того, задача так же может зациклиться. Эти случаи тоже следует учитывать.
Выводы и заключения
линейное программирование симплекс метод
Для решения задачи реализации симплекс-метода в случае всех отрицательных свободных членов мы должны прибегнуть к решению двойственной задачи. Это позволяет получить решение по оптимальному решению двойственной задачи, имеющей допустимое начальное решение.
Задание выполнено, программа работает.
Список используемых источников информации
1. Б.Я Советов, С.А. Яковлев. Моделирование систем. М. Высшая школа,1985
2. Ю.М. Коршунов. Математические основы кибернетики. М.Энергоатомиздат,1987
3. А.А. Горчаков, И.В. Орлова. Компьютерные экономико-математические модели. М.ЮНИТИ,1995
4. А.Н. Колесников. Краткий курс математики для экономистов. М.ИНФА-М,1997
5. В.И. Бережной, Е.В. Бережная Экономико-математические методы и модели в примерах и задачах. Ставрополь,1996
6. Экономико-математические методы и прикладные модели. М.Финстатинформ,1997
7. Б.Я Советов, С.А. Яковлев. Моделирование систем. Практикум. М. Высшая школа,1999
8. С.И. Шелобаев. Математические методы и модели. М. Юнити, 2000
9. В.А. Абчук. Экономико-математические методы. Санкт-Петербург Союз,1999
10. О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. Математические методы в экономике. М.ДИС, 1997.
11. Сайт:http://www.studfiles.ru
Размещено на Allbest.ru
Подобные документы
Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат [583,3 K], добавлен 15.06.2010Основные методы решения задач линейного программирования. Графический метод, симплекс-метод. Двойственная задача, метод потенциалов. Моделирование и особенности решения транспортной задачи методом потенциалов с использованием возможностей Мicrosoft Excel.
контрольная работа [1,1 M], добавлен 14.03.2014Особенности решения задач линейного программирования симплекс-методом. Управляемые параметры, ограничения. Изучение метода потенциалов в процессе решения транспортной задачи. Создание концептуальной модели. Понятие стратификации, детализации, локализации.
лабораторная работа [869,0 K], добавлен 17.02.2012Основы и методы математического программирования. Дифференциальные и разностные уравнения. Классические задачи исследования операций. Алгоритмы симплекса-метода. Допустимые решения при поиске оптимального решения. Линейное и нелинейное программирование.
курсовая работа [183,7 K], добавлен 20.01.2011Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Линейное программирование как инструмент исследования линейных моделей. Основы симплекс-метода. Моделирование экономической ситуации в инструментальном цехе. Применение симплекс-метода для оптимизации плана производства. Применимость линейной модели.
курсовая работа [112,0 K], добавлен 09.12.2014Основы моделирования, прямые и обратные задачи. Линейное программирование и методы решения задач: графический, симплекс-метод. Нахождение решения транспортных и распределительных задач. Теория массового обслуживания. Имитационное моделирование.
курс лекций [1,1 M], добавлен 01.09.2011Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
курсовая работа [54,1 K], добавлен 05.03.2010Характеристика и описание метода линейного программирования, основные области его применения и ограничения использования. Решение экономических задач, особенности формирования оптимизационной модели, расчет и анализ результатов оптимизации прибыли.
курсовая работа [99,0 K], добавлен 23.03.2010