Xreferat.com » Рефераты по экономико-математическому моделированию » Графический метод и симплекс-метод решения задач линейного программирования

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

целевой функции при этих переменных. Ниже записываются коэффициенты уравнений – элементы матрицы условий А, так что под переменной x1 располагается столбец A1, под переменной x2 – столбец A2 и т.д. В правый столбец заносятся правые части ограничений (числа bi > 0).

Затем находим столбцы матрицы условий, образующие единичный базис – в нашем примере это A3 и A4 – и соответствующие им базисные переменные x3, x4 записываем во вторую колонку. Наконец, в первом столбце записываем коэффициенты целевой функции при базисных переменных.


Таблица 1 -  Начальная симплекс-таблица

СБ

 Базисные переменные

с1=1

с2=2

с3=0

с4=0

Значения базисных перем. (xБ=b)

x1

x2

x3

x 4

c3=0

x3

a11=-1

a12=2

a13=1

a14=0

b1=4

c4=0

x4

a21=3

a22=2

a23=0

a24=1

b2=12

Строка оценок j

1= -1

2= -2

3= 0

4= 0

f(x)= 0

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

 

xo = (0, 0, x3, x4) = (0, 0, 4, 12).

 

Шаг 1. Для проверки плана xo на оптимальность подсчитаем симплексные оценки для небазисных переменных x1 и x2 по формуле 

 

j=< cБ, Aj > – cj.

1 = < cБ, A1 > – c1 = 0 ·(–1) + 0 ·3 – 1 = –1.

При табличной реализации для подсчета оценки 1 надо найти сумму произведений элементов первого столбца (cБ) на соответствующие элементы столбца A1 при небазисной переменной x1. Аналогично подсчитывается оценка 2, как скалярное произведение первого столбца (cБ) на столбец при переменной x2.

 

2 = < cБ, A2 > – c2 = 0 ·2 + 0 · 2 – 2 = –2.

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

 

f(x)= < cБ, xБ >,

перемножая скалярно первый и последний столбцы таблицы. 

Так как среди оценок j есть отрицательные, то план xo – не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.

Шаг 2. Поскольку обе оценки 1 и 2 < 0, то в базис можно включить любую из переменных x1, x2. Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x2.

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

В примере ведущим будет столбец при x2.

Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f(x) . В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x2, при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x2 = min{4/2, 12/2}=2.

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

Наименьшее отношение находится в строке с базисной переменной x3. Значит переменная x3 исключается из состава базисных переменных (x3 = 0).

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

В примере ведущей строкой будет первая строка.

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

В нашем случае ведущий элемент a12 = 2.

Табл. 2 - Начальная симплекс-таблица с ведущими строкой и столбцом

cБ

 Базисные перемен.

с1=1

с2=2

с3=0

С4=0

 Значения базисных перем. Уравнения

x1

x2

x3

x 4

c3=0

x3

–1

2

1

0

4

p1

c4=0

x4

3

2

0

1

12

p2

Строка оценок j

1= –1

2= –2

3= 0

4= 0

f(x)= 0

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

Для этого построим новую симплекс-таблицу, во втором столбце которой вместо исключаемой переменной x3 запишем новую базисную переменную x2, а в первом столбце (сБ) вместо с3 запишем коэффициент целевой функции при x2 : c2=2. В новой симплекс таблице столбец при x2 должен стать единичным (ведущий элемент должен равняться единице, а все остальные элементы должны обратиться в ноль). Это достигается следующими преобразованиями строк таблицы.

a.     Все элементы ведущей строки делим на ведущий элемент и записываем в той же строке новой симплекс- таблицы.

Полученную строку p1' назовем разрешающей.

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


p2' = p2 + (- 2) p1' = p2 - p1.

c.      Заполним последнюю строку, вычислив оценки j' = < cБ', Aj' > - - cj, где cБ', Aj' - соответствующие столбцы новой симплекс-таблицы, и значение целевой функции f(x)= < cБ', xБ' >.

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

Таблица 3 - Результат первой итерации

cБ'

 Базисные перемен.

с1=1

с2=2

с3=0

с4=0

 Значения базисных перем. Уравнения

x1

x2

x3

x 4

c2=2

x2

–1/2

1

1/2

0

2

p1' =p1/2

c4=0

x4

4

0

-1

1

8

p2' =p2 - p1

оценки j'

–2

0

1

0

f(x')=4

Новый базисный план x' = (0, x2, 0, x4) = (0, 2, 0, 8).

Поскольку оценка 1= -2 < 0, то план x' не оптимален. Для перехода к новому базисному плану (соседней угловой точки) проведем еще одну итерацию симплекс - метода. 

Так как 1 < 0, то в базис вводится переменная x1. Первый столбец, содержащий x1 - ведущий.

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

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

Строим новую (третью) симплекс-таблицу, заменяя в ней базисную переменную x4 на x1, и снова преобразуя строки таблицы таким образом, чтобы ведущий элемент стал равным единице, а остальные элементы ведущего столбца обратились в ноль. Для этого ведущую (вторую) строку делим на 4, а к первой строке прибавляем полученную вторую строку, деленную на 2. Последнюю строку вычисляем по формулам для симплексных оценок j'' = < cБ'', Aj'' > - cj, где cБ'', Aj'' - соответствующие столбцы новой симплекс-таблицы. Значение целевой функции на новом базисном плане находим по формуле f(x'')= < cБ'', xБ'' >.

Таблица 4 - Результат второй итерации

cБ''

 Базисн. перемен.

с1=1

с2=2
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Страницы: 1 2 3 4

Похожие рефераты:

  • Использование математических методов и моделей в управлении микроэкономическими системами

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

  • Парная регрессия

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

  • Методы и модели в экономике

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

  • Параллельное и последовательное моделирование

    Порядок и разновидности соединений звеньев, их характеристика и отличительные черты. Амплитудно-частотные характеристики при различных соединениях, порядок их расчета и анализа. Методика и этапы моделирования последовательного соединения звеньев.

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

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

  • Расчет семейного бюджета на полугодие

    ИНСТИТУТ РЕКЛАМЫ, ТУРИЗМА И ШОУ-БИЗНЕСА ПРАКТИЧЕСКАЯ РАБОТА По курсу: «Информатика». На тему: Расчет семейного бюджета на полугодие. Выполнила: студентка 3-го курса

  • Моделирование макроэкономических процессов и систем

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

  • Классические методы безусловной оптимизации

    Аналитические и численные методы безусловной оптимизации. Метод исключения и метод множителей Лагранжа (ММЛ). Метод Эйлера – классический метод решения задач безусловной оптимизации. Классическая задача условной оптимизации. О практическом смысле ММЛ.

  • Двойственность в линейном программировании

    Прямые и двойственные задачи линейного программирования, особенности и методика их решения. Основные положения теоремы двойственности. Виды математических моделей двойственных задач. Разработка программы планирования работы швейной мастерской в Excel.

  • Мультипликативная модель Хольта-Уинтерса

    Построение адаптивной мультипликативной модели Хольта-Уинтерса с учетом сезонного фактора и согласно параметрам сглаживания. Средняя ошибка аппроксимации. Определение коэффициентов заданного линейного уравнения. Проверка точности построенной модели.

  • Программа имитационного моделирования работы банка

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

  • Имитационное моделирование на основании предварительно установленных зависимостей

    Расчет экономического эффекта работы банка. Алгоритм имитационного моделирования работы кассового зала. Функция распределения экспоненциального закона. Корректировка времени обслуживания клиентов у касс и продвижения очереди. Листинг программы.

  • Метoд аналiзу iєрархiй

    Побудова матриці попарних порівнянь для другого рівня ієрархії. Розрахунок локальних вершин ієрархії та глобальних пріоритетів. Визначення найкращої моделі комп'ютера по параметрам швидкодії, можливості апгрейту, шумовим характеристикам, зручності роботи.

  • Определение оптимальных складских запасов

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

  • Основы решения эконометрических задач

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

  • Оптимизация сетевой модели комплекса производственных работ

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

  • Моделирование физических процессов

    Применение математических методов в моделировании физических процессов, распределение информации и использование языка программирования Pascal. Построение графиков функций, решение уравнений в MathCAD, геометрический смысл методов Эйлера и Рунге-Кутта.

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

    Максимальная ошибка прогноза. Геометрический смысл коэффициента. Истинная прямая регрессии. Ширина доверительного интервала. Матричная запись многофакторной регрессии. Эконометрический анализ нелинейной зависимости показателя от второго фактора.

  • Исследование экономико-математических моделей

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

  • Анализ эмпирического распределения

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