Математическое программирование - Программирование, компьютеры и кибернетика курс лекций

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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

Математическое программирование. Понятие об оптимизационных задачах. Задача линейного программирования (ЗЛП) . Графический метод решения ЗЛП
1. Предмет - математическое программирование, краткая классификация методов.
2. Основные понятия теории оптимизации.
3. Постановка ЗЛП, различные формы записи. Примеры экономических задач.
4. Графический метод решения ЗЛП. Основные свойства ЗЛП.
Предмет - математическое программирование
Среди многочисленных проблем, возникновение которых связано с бурно развивающейся научно-технической революцией, пожалуй, наиболее важной является проблема совершенствования управления во всех звеньях хозяйства.
Современные промышленные предприятия, предприятия бытового обслуживания, транспортные агентства, научно-технические организации представляют собой сложные системы «человек-машина». Эффективность работы таких систем зависит от качества организационного управления. Чтобы добиться качества современному руководителю не всегда бывает достаточно личного опыта, интуиции и организаторских способностей в их традиционном понимании. При формировании стратегических и тактических решений руководитель должен учитывать множество подчас противоречивых соображений, опираться на сложные критерии эффективности путей достижения конечных целей. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием - математическое программирование.
Математическое программирование - область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функций многих переменных с ограничениями на область изменения этих переменных.
Для того, чтобы успешно руководить крупным предприятием в условиях конкуренции руководителю, возможно, и не надо быть самому классным специалистом в области математического программирования, но чтобы понимать суть и смысл решаемой задачи, получаемых результатов и не «упустить руль», он должен понимать способ решения, быстро реагировать на возникающие изменения, чтобы эффективно использовать возможности математического программирования. Математическое программирование в настоящее время используется практически во всех областях жизни и производства:
в экономике - для решения больших макроэкономических моделей (типа модели Леонтьева и др.), микроэкономических моделей или моделей предпринимательства, для оптимизации технико-экономических систем (планирование, эконометрика), транспортные задачи, в теории принятия решений, теории игр и т.п.;
в технике - управление размерами и оптимизация структур, оптимальное планирование сложных технических систем, как информационные системы, сети компьютеров, транспортные и телекоммуникационные сети и др.;
в автоматике - распознавание систем и объектов, оптимальное управление системами, фильтрация, роботы, автоматизированные линии и т.п.;
в медицине, политике, социологии и т.п., и т.д.
Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности.
Экономические возможности формализуются в виде системы ограничений.
Все это составляет математическую модель. Математическая модель - это отражение оригинала в виде функций, уравнений, неравенств, цифр и т.д. Модель задачи математического программирования включает:
совокупность неизвестных величин х = (х 1 , х 2 , …, х n ), действуя на которые систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, стратегией, поведением и т.п.);
целевую функцию, которая позволяет выбрать наилучший вариант из множества возможных. Целевая функция обозначается F(x). Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности и т.д.;
условия (система ограничений), налагаемые на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений.
Т.о., модель задачи математического программирования примет вид:
Найти план х = (х 1 , х 2 , …, х n ), доставляющий экстремальное значение целевой функции F ( x ) > max ( min ), при ограничениях g i ( x ) ? (=, ?) b i , i = .
Из экономических или физических соображений на план задачи или некоторые его компоненты, как правило, налагаются условия неотрицательности, х j ? 0, иногда - целочисленности.
План х, удовлетворяющий системе ограничений задачи, называют допустимым. Допустимый план, доставляющий целевой функции экстремальное значение, называют оптимальным. Оптимальный план обозначают х*, экстремальное значение функции F(x*) = F*.
В зависимости от особенностей целевой функции F(x) и функций ограничений g i (x), задачи математического программирования делятся на ряд типов.
Задача линейного программирования (ЗЛП) - задача оптимизации линейной функции при линейных ограничениях.
Задача нелинейного программирования (ЗНП) - задача оптимизации нелинейной функции при ограничениях или без них (когда или F(x) и/или g i (x) нелинейны).
Задача дискретного (в частности целочисленного) программирования - Задача оптимизации, в которой на переменные наложено дополнительное требование принимать лишь дискретные (в частности целочисленные) значения.
Задача динамического программирования - задача оптимизации динамических систем (т.е. развивающихся с течением времени).
Задача вероятностного или стохастического программирования - задача оптимизации, содержащая случайные величины.
Основные понятия теории оптимизации
Говорят, что функция F(x) имеет в т. х*(х 1 ,х 2 , … , х n ) локальный максимум (минимум), если существует такая окрестность т. х*, в которой для любого х выполняется неравенство F(x) ? F(x*) (F(x) ? F(x*)).
Необходимое условие экстремума: чтобы F(x) имела в т. х* экстремум необходимо, чтобы ?F(x*)/?x j = 0, .
Достаточное условие экстремума: если F(x) в т. х* имеет ?F(x*)/?x j = 0, , то чтобы в этой точке F(x) имела экстремум достаточно, чтобы квадратичная форма
была положительно (минимум) или отрицательно (максимум) определена.
Очевидно, что точки локального экстремума могут не давать наибольшего или наименьшего значений функции в некоторой области, кроме того, их может быть несколько. Большое значение в этой связи приобретает понятие выпуклости множества допустимых значений и выпуклости (вогнутости) функции.
Множество S называется выпуклым, если для любых двух точек этого множества оно содержит и отрезок, соединяющий эти точки:
Функция F ( x ), определенная на выпуклом множестве S , выпукла, если ее график целиком лежит ниже (не выше) отрезка, соединяющего любые две точки графика:
Функция F ( x ), определенная на выпуклом множестве S , вогнута, если ее график целиком лежит выше (не ниже) отрезка, соединяющего любые две точки графика:
Теорема 1: пересечение выпуклых множеств является выпуклым множеством.
Теорема 2: сумма выпуклых функций является выпуклой функцией, сумма вогнутых функций - вогнутой функцией.
Теорема 3 (основное свойство выпуклых задач):
Всякий локальный оптимум является глобальным.
Непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает максимума (минимума) по крайней мере в одной точке этого множества.
Из сказанного можно определить общий принцип решения задач оптимизации: максимум (минимум) F(x) при х, принадлежащих замкнутому допустимому множеству, если оно существует, является либо точкой экстремума, либо граничной точкой допустимого множества, либо и тем и другим одновременно.
При численных расчетах часто необходимо использовать еще два важных понятия.
Вектор, указывающий направление наискорейшего возрастания функции, называется градиентом функции grad F ( x ) = (? F /? x 1 , … ,? F /? x n ). Противоположный ему вектор называют антиградиентом, он указывает направление наискорейшего убывания функции.
Линией уровня (или линией равного значения) функции F ( x ) называют геометрическое место точек, координаты которых удовлетворяют уравнению F ( x ) = Const . Линия уровня и вектор градиент в каждой точке взаимно перпендикулярны.
Постановка ЗЛП, различные формы запи си. Примеры экономических задач
Линейное программирование - раздел математического программирования, рассматривающий задачи оптимизации линейных функций многих переменных при линейных ограничениях на область изменения переменных.
Особенностью ЗЛП является то, что линейная целевая функция не имеет экстремума и достигает наибольшего или наименьшего значения на границе допустимой области.
Рассмотрим постановку ЗЛП на примере задачи и наилучшем использовании ресурсов. Имеется m видов ресурсов в ограниченном количестве b = (b 1 , b 2 , … , b m ). Ресурсы используются предприятием для выпуска n видов продукции. Известна экономическая выгода производства каждого вида продукции, исчисляемая, например, ценой реализации С = (С 1 , С 2 , … , С n ). Известны технологические коэффициенты а ij , соответствующие количеству i-го вида ресурса, необходимого для производства единицы j -го вида продукции - А = ( а ij ). Необходимо составить план производства х = (х 1 ,х 2 , … , х n ), приносящий предприятию максимальную прибыль.
В общем виде математическую модель задачи (ЗЛП) можно записать следующим образом:
F(x) = C 1 x 1 + C 2 x 2 + … + C n x n > max
a 11 x 1 + a 12 x 2 + … + a 1n x n ? b 1 , x j ? 0, j=
a 21 x 1 + a 22 x 2 + … + a 2n x n ? b 2 ,
a m1 x 1 + a m2 x 2 + … + a mn x n ? b m .
Рассмотрим задачу о диете. Необходимо составить диету (рацион), содержащую определенные питательные вещества. Имеем n видов продуктов, каждый из которых сожержит необходимые m видов питательных веществ. Единица j-го продукта содержит а ij единиц i-го питательного вещества. Для нормальной жизнедеятельности необходимо не менее b i единиц i-го вещества. Известна стоимость единицы каждого вида продукта С = (С 1 , С 2 , … , С n ). Необходимо составить диету минимальной стоимости.
Математическая модель задачи примет вид:
F(x) = C 1 x 1 + C 2 x 2 + … + C n x n > min
a 11 x 1 + a 12 x 2 + … + a 1n x n ? b 1 , x j ? 0, j=
a 21 x 1 + a 22 x 2 + … + a 2n x n ? b 2 ,
a m1 x 1 + a m2 x 2 + … + a mn x n ? b m .
Здесь х j - количество j - го продукта в рационе.
В матричной форме общая ЗЛП выглядит так:
Кроме того, для записи ЗЛП можно использовать знак суммы:
Рассмотрим задачу о размещении заказа. Имеется m однородных групп оборудования, на котором нужно выполнить заказ на выпуск n видов продукции в объемах х* j , . Мощность оборудования ограничена, например, временем Т i . Производительность оборудования задана коэффициентами а ij . Известны коэффициенты затрат С ij - затраты i - го оборудования на производство j - го продукта. Построить план х ij размещения заказа (загрузки оборудования). Составим математическую модель задачи.
- по видам продукции, план по которой может быть перевыполнен
- по видам продукции, план по которой должен соответствовать заказу
- по видам продукции, заказ на которую принимается для более полной загрузки
4. Графический метод реш ения ЗЛП. Основные свойства ЗЛП
Графический метод решения ЗЛП используется, если число неизвестных задачи не больше 2 или если разность между числом неизвестных и ограничений задачи, записанных в виде уравнений не более двух.
Определяем точку максимума (минимума):
Точка максимума - точка допустимой области, наиболее удаленная от линии уровня в направлении градиента, точка минимума - точка допустимой области, наиболее удаленная от линии уровня в направлении антиградиента.
При решении ЗЛП возможны следующие случаи:
ЗЛП является выпуклой задачей, поэтому решение всегда единственно.
Оптимальное решение достигается по крайней мере в одной из вершин допустимой области: а) только в одной вершине; б) в двух вершинах и имеет бесконечное множество планов.
Если допустимая область не ограничена, то ЗЛП может быть разрешима или не разрешима, что зависит от целевой функции: в) задача на max не разрешима, а на min - разрешима; г) ЗЛП не разрешима.
Если допустимая область состоит из единственной точки, то в ней достигается и максимум и минимум - д).
Если допустимая область пуста, то ЗЛП не разрешима - е).
Если допустимая область ограничена и не пуста, то ЗЛП всегда имеет решение.
1. Стандартная форма ЗЛП, правила построения.
2. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР), метод искусственного базиса.
1. Стандартна я форма ЗЛП, правила построения
Графический метод решения ЗЛП можно использовать, если число неизвестных равно 2 или разность между числом неизвестных и числом ограничений, записанных в виде уравнений, равна 2. В общем случае эти требования не всегда выполняются. Чтобы использовать для решения некий универсальный метод решения, ЗЛП необходимо записать в определенной, стандартной форме.
Стандартная форма ЗЛП представляет собой такой вид задачи, в котором:
2) все ограничения заданы в виде уравнений;
3) целевая функция сформулирована на минимум.
Требования эти оправданы. Во-первых, поиск максимума линейной функции сводится к поиску минимума функции с противоположными по знаку коэффициентами: оптимальные точки совпадают, а значения целевых функций равны по абсолютному значению. Во-вторых, линейная функция не имеет экстремумов и достигает своего наибольшего или наименьшего значения на границе допустимой области, поэтому и решать необходимо не неравенства, а уравнения. Запишем правила приведения любой ЗЛП к стандартному виду.
Правила построения стандартной формы ЗЛП:
1) Если F(x) = C 1 x 1 + C 2 x 2 + … + C n x n max, то можно искать
F(x) = - C 1 x 1 - C 2 x 2 - … - C n x n min.
2) Ограничения в виде неравенств ( ) могут быть сведены к уравнениям введением дополнительных, уравновешивающих неотрицательных уравнений.
Например: 2х 1 + 3х 2 4 2х 1 + 3х 2 + х 3 = 4, х 3 - уравновешивающая переменная.
4x 1 + 2x 2 5 4x 1 + 2x 2 - x 4 = 5, x 4 - уравновешивающая переменная.
3) Если некоторая переменная х может быть не ограничена знаком, то в стандартном виде такую переменную можно представить в виде разности двух неотрицательных переменных: x = x' - x'', x' , x'' .
При этом дополнительные переменные не входят в целевую функцию. Стандартная форма ЗЛП в матричном виде выглядит так: Ax = b, x , F(x) = C T x min.
2. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР), метод искусственного базиса
Чтобы ЗЛП имела решение необходимо, чтобы система ограничений была совместна. Это возможно, если ранг m системы (число линейно независимых уравнений) был не больше числа неизвестных n. Случай m > n невозможен. При m = n система имеет единственное решение, которое определяется методами обычной алгебры. Если m < n, то система имеет m линейно независимых векторов - базис, через которые любой вектор системы может быть выражен как линейная комбинация. Таких базисов может быть несколько, но не больше, чем С n m . Переменные ЗЛП, соответствующие m векторам базиса, являются базисными, остальные переменные - свободные.
Базисом называют любой набор m переменных такой, что определитель, составленный из коэффициентов при этих переменных, отличен от нуля. Соответствующее решение называю базисным решением.
Переменные, входящие в базис, называют базисными (б.п.), остальные n - m переменных называют свободными.
Чтобы получить простейшее частное решение системы необходимо свободные переменные приравнять нулю, учитывая при этом неотрицательность всех переменных.
Допустимым базисным решением (ДБР) является такое, при котором все переменные неотрицательны. В противном случае базисное решение недопустимо.
Частное допустимое базисное решение, с которого начинают решение, называют начальным допустимым базисным решением (НДБР).
Чтобы найти НДБР, удобно ЗЛП записать в каноническом виде.
Канонический вид ЗЛП - это такой стандартный вид, в котором в каждом i-ом уравнении найдется такая переменная х I , что коэффициент перед ней в данном уравнении равен +1, а в других уравнениях и в выражении целевой функции эти коэффициенты равны нулю. Если при этом все b , то говорят о допустимом каноническом виде, в противном случае - о недопустимом.
1 Случай. Исходная задача ЗЛП содержит все ограничения со знаком .
Стандартная форма ЗЛП является одновременно и каноническим допустимым видом.
, - дополнительные, уравновешивающие переменные
При этом х j = 0, - свободные переменные, х n + I = b i , - - базисные переменные - НДБР.
2 Случай. Ограничения исходной ЗЛП содержат неравенства разных знаков и уравнения.
Стандартная форма ЗЛП не совпадает с каноническим видом.
, - дополнительные, уравновешивающие переменные.
Чтобы построить канонический вид и получить НДБР используют метод искусственного базиса. В каждое уравнение, не содержащее переменную, создающую канонический вид, вводят искусственную неотрицательную переменную.
Новые искусственные переменные создают канонический вид. Однако, вводя в ограничения-равенства искусственную переменную, изменяют исходные условия.
Чтобы преобразованная задача соответствовала исходной, необходимо, чтобы в окончательном решении искусственные переменные равнялись нулю. Этого можно достичь, если вспомогательная целевая функция, равная сумме искусственных переменных, будет равна нулю, то естьb
Оптимальное решение вспомогательной задачи соответствует НДБР исходной задачи.
При решении ЗЛП симплекс-методом удобно представить задачу в табличном виде.
ПРИЗНАК ОПТИМАЛЬНОСТИ. План х* = (х 1 , х 2 , ..., х n ) считается оптимальным, если все коэффициенты целевой функции неотрицательны, С j 0,. Тогда значение F max равно значению, стоящему в правом нижнем углу таблицы.
Если имеется хотя бы один отрицательный коэффициент целевой функции, следует перейти к новому базисному решению, значение целевой функции при котором будет меньше. Для этого используют следующие правила:
Среди отрицательных коэффициентов целевой функции выбирают максимальный по модулю. Столбец, в котором стоит этот коэффициент, называют разрешающим и помечают *.
Находят отношения , т.е. отношения свободных членов ограничений к элементам матрицы коэффициентов ограничений, стоящим в разрешающем столбце и имеющим положительные значения. Среди этих отношений выбирают минимальное. Строка, в которой стоит это минимальное отношение, называется разрешающий и помечается *. Если среди элементов разрешающего столбца не будет ни одного положительного, то задача оптимизации не имеет решения.
Элемент, стоящий на пересечении разрешающих строки и столбца, называется разрешающим и отмечается .
Производится замена базисного допустимого решения на другое, при этом таблица будет иметь следующее содержание:
а) свободная переменная х j * , стоящая в разрешающем столбце, становится базисной, а
базисная переменная х ai* , стоящая в разрешающей строке, - свободной;
б) все элементы разрешающей строки в новой таблице имеют значения
в) все остальные элементы таблицы определяются по формулам:
Каждая новая таблица проверяется на оптимальность. Операции 1)-4) осуществляются до тех пор, пока не будет получено оптимальное значение целевой функции.
Устойчивость решений ЗЛП при небольших изменениях условий. Двойственный симплекс-метод
1. Обращенный базис, симплекс - множители.
2. Изменение значений правых частей ограничений.
3. Изменение значений коэффициентов целевой функции.
4. Включение дополнительных переменных.
5. Включение дополнительных ограничений.
7. Проблемы вырождения, зацикливания.
1. Обращен ный базис, симплекс - множители
Рассмотрим решение ЗЛП симплекс-методом с точки зрения алгебры. В матричном виде стандартная форма ЗЛП имеет вид: , Ах = b, где А mxn . Представим матрицу А в виде «склеенных» двух матриц А = В mxm R mx ( n - m ) . Здесь В mxm - матрица, состоящая из столбцов матрицы А, соответствующих переменным, которые в оптимальной таблице являются базисными. Матрица R mx ( n - m ) состоит из всех оставшихся столбцов. Предположим известна матрица В -1 . Умножим слева ограничения ЗЛП на В -1 :
В -1 (ВR)x = B -1 b, здесь х = (х б.п. , х св.п. ) (Е m B -1 R)x = B -1 b x б.п. = B -1 b , х св.п. = 0.
В НДБР базисным переменным соответствует единичная матрица, то есть А = С n - m E m . Так как А умножается на В -1 , то В -1 А = В -1 (С n - m E m ) = В -1 С В -1 , что соответствует матрице коэффициентов оптимальной таблицы. Следовательно, в оптимальной таблице в столбцах тех переменных, которые были базисными в НДБР, находится матрица В -1 .
Матрица В -1 называется обращенный базис. В оптимальной таблице В -1 находится среди коэффициентов ограничений, стоящих в столбцах тех переменных, которые были базисными в исходной таблице.
Запишем теперь канонический вид задачи.
x n + I , I = - уравновешивающие переменные.
Умножим каждое ограничение на некоторое число , соответственно и сложим с выражением целевой функции, получим
х 1 (С 1 + ) + … + х n (C n + ) + + … + = F(x) +
Значения можно подобрать таким образом, чтобы коэффициенты перед базисными переменными равнялись нулю. Без ограничения общности, например, первые m переменных являются базисными, тогда можно определить из системы
Если предположить, что подобрали таким образом, что перед базисными переменными коэффициенты равны нулю, а перед свободными - неотрицательны, то вид (1) будет соответствовать оптимальному виду таблицы. Следовательно, в оптимальной таблице коэффициенты в выражении целевой функции перед переменными, которые были базисными в исходной таблице, есть . Это и есть симплекс - множители. При этом,
Симплекс - множители - это такие числа , при умножении на которые каждого ограничения, соответственно, и сложении с выражением целевой функции будет получен такой вид целевой функции, что перед базисными переменными коэффициенты равны нулю, а перед свободными неотрицательны.
Замечание: если не все коэффициенты свободных переменных в выражении целевой функции неотрицательны, то это симплекс - множители промежуточного решения.
Обращенный базис и симплекс - множители позволяют использовать найденное решение ЗЛП, если происходят изменения условий задачи.
2. Изменение зна чений правых частей ограничений
Правые части ограничений выражают ограниченные объемы ресурсов или минимальные нормы потребления и т.п. Предположим правые части ограничений изменились на . Другими словами, встает задача найти новый оптимальный план, при b' = b + . Можно ли использовать результаты уже решенной задачи? Если задача была решена для прежнего значения b, то известными являются обращенный базис В -1 и симплекс - множители . При этом при определении В -1 и значения b никак не учитывались, эти значения влияют лишь на оптимальное значение целевой функции. Следовательно, новые значения целевой функции и переменных можно получить по формулам
Замечание. Указанный прием можно использовать лишь при небольших изменениях в b, то есть базисное решение должно остаться допустимым (неотрицательным). Таким образом, если для базисных переменных получено хотя бы одно отрицательное значение, то решение задачи можно продолжить двойственным симплекс-методом.
3. Изменение значений коэффициентов целевой функции
Коэффициенты целевой функции выражают цены реализации, стоимость затрат и т.п. Если изменения произошли в коэффициентах целевой функции, можно ли воспользоваться решением задачи с прежними коэффициентами? То есть, если
C j ' = C j + , а изменений в b не произошло, то и оптимальный план не изменится, а изменятся лишь оптимальные значения целевой функции и ее коэффициентов. В исходной таблице целевая функция имеет вид
F(x) = -C 1 x 1 - C 2 x 2 - … - C n x n
Пусть в оптимальной таблице базисными оказались первые m переменных, следовательно, коэффициенты перед ними в оптимальной таблице должны быть равны нулю, исключим эти переменные из выражения целевой функции. Чтобы получить выражение целевой функции оптимальной таблицы в общем виде, используют оптимальную таблицу.
Умножим все уравнения системы соответственно на С 1 , С 2 , … , С n и сложим с выражением целевой функции исходной таблицы в общем виде. Получим
Полученное выражение представляет оптимальное выражение целевой функции. При этом оптимальность таблицы также определятся коэффициентами целевой функции. Заметим, что С j не влияют на ограничения задачи. Если изменить С j , то изменятся условия оптимальности:
- если для С j ' коэффициента целевой функции окажутся неотрицательными, то найденное решение сохранится, то есть если, , то решение не изменится
- если хотя бы один коэффициент окажется меньше нуля, то следует перейти к другому базисному решению, то есть продолжить решение обычным симплекс-методом.
4. Вклю чение дополнительных переменных
Каждая переменная ЗЛП, если она не является уравновешивающей или искусственной, определяет план производства некоторой продукции, объем потребления и т.п. Предположим, поступило предложение выпускать новый вид продукции или использовать новую технологию. Стоит ли менять уже налаженное производство? Будет ли увеличение прибыли (сокращение расходов) весомым?
Пусть объем нового вида продукции х n +1 , технологические коэффициенты известны
Р = ( 1(n+1) , 2( n +1) , … , m ( n +1) ) T , предполагаемая прибыль от реализации единицы продукции С n +1 . Все остальные условия остаются прежними. Чтобы учесть эти изменения, не решая задачу с самого начала, необходимо дополнительные данные записать в оптимальную таблицу. Новая «исходная» матрица коэффициентов A' = A P, чтобы привести ее к виду оптимальной таблицы, необходимо умножить ее на В -1 . Таким образом, в оптимальной таблице добавляется еще один столбец Р* = В -1 Р. При этом свободные члены не изменяются. Осталось записать коэффициент целевой функции, это можно сделать с помощью симплекс - множителей. Умножим коэффициенты Р на соответствующие симплекс - множители и прибавим к коэффициенту целевой функции в стандартном виде:
Если C n +1 *, то х n +1 останется свободной ( то есть равной нулю), так как сохранится признак оптимальности. Следовательно, план менять не стоит.
Если C n +1 * < 0, то следует улучшить решение, а именно х n +1 ввести в базисные переменные. Следовательно, план изменится. При этом решение продолжается обычным симплекс-методом.
5. Включ ение дополнительных ограничений
Экономическая ситуация, в которой приходится решать производственные и плановые задачи, изменяется. Может оказаться так, что некоторый ресурс, считавшийся ранее неограниченным, окажется лимитирован. Например, введение веерного распределения электроэнергии т.п. Другими словами, необходимо проверить. Удовлетворяет ли рассчитанный план новым ограничениям, и как его изменить, если ограничения нарушаются.
Итак, пусть - новое дополнительное ограничение к уже решенной задаче. То есть х* уже найдено.
Если найденное х* = (х 1 , х 2 , … , х n ) удовлетворяет поставленному дополнительному ограничению, то план никак не изменится (ограничение не ограничивает данное производство).
Если х* = (х 1 , х 2 , … , х n ) не удовлетворяет новому ограничению, то необходимо изменить план, то есть продолжить решение.
Чтобы продолжить решение. Необходимо учесть новое ограничение, записав его в каноническом виде, соответствующем оптимальной таблице: дополнительное ограничение должно содержать одну переменную с коэффициентом 1, и чтобы в других уравнениях и выражении целевой функции она отсутствовала, кроме того, это уравнение не должно содержать базисных переменных оптимальной таблицы. Чтобы исключить базисные переменные оптимальной таблицы, используют оптимальный канонический вид. При этом решение продолжается двойственным симплекс-методом.
Для решения задачи двойственным симплекс-методом она должна иметь недопустимый канонический вид. И признак оптимальности должен выполняться.
Общая идея: начиная с недопустимого базисного решения при выполнении признака оптимальности, последовательно перейти к допустимому базисному решению, сохранив признак оптимальности.
1. Недопустимый канонический вид ограничений и оптимальный вид (С j ) целевой функции записывают в исходную таблицу.
2. Среди отрицательных свободных членов выбирают , соответствующую строку помечают * и называют разрешающей.
3. Среди всех отношений коэффициентов целевой функции к отрицательным элементам разрешающей строки выбирают , соответствующий столбец помечают, выполняют обычные симплекс-преобразования и называют разрешающим .
Замечание: 1. Обычный симплекс-метод при сохранении допустимости решения переходит последовательно к оптимальному решению. А двойственный симплекс-метод при сохранении оптимальности переходит последовательно от недопустимого решения к допустимому.
2. Правила двойственного симплекс-метода отличаются от правил обычного выбором разрешающих столбца и строки.
3. Если в разрешающей строке (для двойственного метода) нет ни одного отрицательного элемента, то задача не разрешима.
7. Пр облемы вырождения, зацикливания
Как правило, все базисные переменные отличны от нуля (то есть в симплекс-таблице все свободные члены ). Однако, нет никаких ограничений к тому, чтобы одна или несколько базисных переменных обратились в ноль.
Базисное решение (базис) является невырожденным, если оно содержит ровно m отличных от нуля компонент. В противном случае - вырожденным.
Если начальный план задачи невырожден, то никаких сложностей при решении не возникает, при правильном выборе разрешающего элемента. Если хотя бы одна базисная переменная в НДБР приняла нулевое значение, то по правилам симплекс-метода именно она должна будет войти в базис на следующем шаге, так как min b i /a ij * = 0. При этом значение целевой функции не изменится.
Двойственность в линейном программировании
1. Понятия двойственности, теневой цены, двойственной оценки.
2. Правила построения двойственной задачи.
3. Основные теоремы двойственности и их экономическое содержание.
1. Понятия двойственности, те не
Математическое программирование курс лекций. Программирование, компьютеры и кибернетика.
Реферат: Монеты Ольвии до гетского разгрома
Сочинение На Тему Белорусская
Контрольная работа по теме Способи боротьби з шумом на підприємствах. Пожежна безпека
Курсовая работа по теме Порядок формирования показателей отчета о движении денежных средств организации в бухгалтерской (финансовой) отчетности
Дипломная работа: Маркетинг в банковской сфере 2
Сочинение На Тему Я Горжусь Своей Семьей
Реферат На Тему Налоги И Налогообложение
Готовые Дипломные Работы По Медицине Бесплатно
Декабрьское Сочинение Последние Новости
Курсовая работа: Эволюция и перспективы развития электронных денег
Реферат: Місце і роль інституту охорони праці в системі трудового права України
Сочинение Сосновый Лес
Меры Пресечения Диссертация
Курсовая работа по теме Правовое регулирование расследований и учёта несчастных случаев на производстве по законодательству РФ
Сочинение по теме Малати и Малхава (Malati-madhava)
Сочинение В Чем Внутренний Конфликт Демона
Реферат по теме Этикет руководителя
Курсовая работа по теме Исследования социальной установки в отечественной и зарубежной психологии
Реферат На Тему Элементарные Стадии С Участием Координационных И Металлоорганических Соединений В Растворах И На Поверхности Металлов И Оксидов
Реферат по теме Патентный и нормативный документы
Основы формирования системы управления персоналом - Менеджмент и трудовые отношения курсовая работа
Изучение судебной реформы Петра I в XIX – начале XXI в. - История и исторические личности реферат
Административная юрисдикция органов внутренних дел - Государство и право контрольная работа