По курсу математические методы и модели исследования операций для студентов специальности 080801


НазваниеПо курсу математические методы и модели исследования операций для студентов специальности 080801
страница2/7
Дата публикации19.06.2013
Размер0.92 Mb.
ТипМетодические указания
userdocs.ru > Математика > Методические указания
1   2   3   4   5   6   7

Задачи
1.7. Решить симплекс-методом (с помощью симплекс-таблиц) задачу ЛП

f(x)=3x1+2x2  max,

x1x2≤2,

2x1+x2≤6,

x1, x2≥0.

1.8. Пищевой рацион должен содержать не менее восьми единиц вещества А и не менее десяти единиц вещества В.

Имеется 2 вида продуктов питания: П1 и П2. В единице продукта П1 содержатся 1 единица вещества ^ А и 2 единицы вещества В; в единице продукта П2 содержатся 2 единицы вещества А и 1 единица вещества В. Цена единицы продукта П1 составляет 3 д.е., цена единицы продукта П2 – 2 д.е.

Определить, какое требуется количество продуктов П1 и П2, чтобы обеспечить заданные условия при минимальной стоимости рациона.

Составить математическую модель задачи. Решить полученную задачу ЛП симплекс-методом.
^ 1.4. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛП
Каждой задаче ЛП можно определенным образом сопоставить некоторую другую задачу ЛП, называемую двойственной, по отношению к исходной или прямой. Так, общей задаче ЛП

(1.18)

(1.19)

(1.20)

(1.21)

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

(1.22)

(1.23)

(1.24)

(1.25)

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

− прямая задача является задачей максимизации, двойственная задача – задачей минимизации;

− число m переменных двойственной задачи равно числу ограничений прямой задачи, а число n ограничений двойственной задачи равно числу переменных прямой задачи;

− коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

− свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

− матрица коэффициентов ограничений двойственной задачи получается транспонированием матрицы коэффициентов ограничений прямой задачи;

− если i-е ограничение прямой задачи является неравенством вида « ≤ », то i-я переменная yi двойственной задачи должна быть неотрицательной, т.е. yi≥0; если i-е ограничение прямой задачи является равенством, то i-я переменная yi двойственной задачи может принимать произвольные значения;

− если j-я переменная xj прямой задачи должна быть неотрицательной, т.е. , то j-е ограничение двойственной задачи является неравенством вида « ≥ »; если j-я переменная xj прямой задачи может принимать произвольное значение, то j-е ограничение двойственной задачи является равенством.

В свою очередь прямая задача (1.18)÷(1.21) является двойственной по отношению к двойственной задаче (1.22)÷(1.25), рассматриваемой в качестве исходной. Для составления прямой задачи по известной двойственной можно использовать аналогичные вышеприведенным правила.

Задачи (1.18)÷(1.21) и (1.22)÷(1.25) образуют пару задач, называемых в ЛП двойственными задачами.

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





Двойственная симметричная задача имеет вид







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



где x*, y* – соответственно оптимальные решения прямой и двойственной задач.

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

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


где – соответственно коэффициенты целевой строки прямой и двойственной задач.

Благодаря этой взаимосвязи можно решить более простую из пары задач, а затем по найденному решению отыскать решение другой задачи.
Задачи
1.9. Составить задачу ЛП, двойственную к задаче



1.10. Пищевой рацион должен содержать не менее 8 единиц вещества А, не менее 10 единиц вещества В, не менее 8 единиц вещества С и не менее 30 единиц вещества D.

Имеется 2 вида продуктов питания: П1 и П2. В единице продукта П1 содержатся 1 единица вещества А, 2 единицы вещества В, 1 единица вещества С и 3 единицы вещества D; в единице продукта П2 содержатся 2 единицы вещества А, 1 единица вещества В, 1 единица вещества С и 5 единиц вещества D. Цена единицы продукта П1 составляет 3 д.е., единицы продукта П2 – 2д.е.

Определить, какое требуется количество продуктов П1 и П2, чтобы обеспечить заданные условия при минимальной стоимости рациона.

Составить математические модели прямой и двойственной задач. Решив симплекс–методом более простую из задач, найти решение поставленной задачи.
^ 1.5. ТРАНСПОРТНАЯ ЗАДАЧА
Постановка транспортной задачи формулируется следующим образом.

В пунктах производства А1, А2,…, Аm имеются запасы некоторого однородного продукта в количествах а1, а2,…, аm единиц. Данный продукт потребляют в пунктах В1, В2,…, Вn в количествах b1, b2,…, bn единиц. Из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки на перевозку единицы продукции из пункта Аi в пункт Вj составляют

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

Пусть xij – количество продукта, перевозимого из пункта Аi в пункт Вj, Тогда математическая модель транспортной задачи имеет следующий вид:

(1.26)

(1.27)

(1.28)

(1.29)

Условие (1.27) означает полный вывоз продукта из всех пунктов производства, а условие (1.28) − полное удовлетворение спроса во всех пунктах потребления.

Набор переменных xij, удовлетворяющий условиям (1.27)÷(1.29), записывают в виде матрицы



Матрицу Х называют планом перевозок транспортной задачи, а переменные хij − перевозками. План X*, при котором целевая функция минимальна, называется оптимальным планом.

Необходимым и достаточным условием разрешимости транспортной задачи является условие баланса

(1.30)

Это условие означает, что объем производства (предложение) должен быть равен объему потребления (спроса).

Модель (1.26)÷(1.29) транспортной задачи при выполнении условия (1.30) называется закрытой моделью, а при не выполнении условия (1.30) − открытой моделью.

Для своего решения задача, описываемая открытой моделью, должна быть сведена к задаче, описываемой закрытой моделью. При необходимо ввести фиктивный пункт производства Am+1 с объемом производства и транспортными издержками (в оптимальном решении Х* полагают ). При необходимо ввести фиктивный пункт потребления Bn+1 с объемом потребления и транспортными издержками (в оптимальном решении ^ Х* полагают ).

Число переменных хij в транспортной задаче с m пунктами производства и n пунктами потребления равно nm, а число уравнений в системах (1.27) и (1.28) равно n+m. Так как предполагается, что выполняется условие баланса (1.30), то число линейно независимых уравнений равно n+m−1. Следовательно, ранг системы ограничений (1.27)÷(1.28) и число базисных переменных равно n+m−1. Для транспортных задач вместо понятия «допустимое базисное решение» используется эквивалентное ему понятие «опорный план». Таким образом, опорный план транспортной задачи может иметь не более n+m−1 отличных от нуля компонент.

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

Для определения начального опорного плана разработаны несколько методов. Два из них – метод северо-западного угла и метод минимального элемента − рассматриваются на практическом занятии.

В случае метода северо-западного угла для определения начального опорного плана Х0 используются только вектор производства и вектор потребления . Заполнение таблицы для ^ Х0 начинается с левого верхнего элемента х11, что и обусловило название − метод северо-западного угла.

Процедура заполнения таблицы Х0 состоит из n+m−1 шагов (на каждом шаге определяется одна базисная переменная). На k-м, k=1,2,…,n+m−1, шаге выполняют следующие действия:

1. Определяют левый верхний элемент , причем незаполненной части таблицы



где − соответственно векторы производства и потребления, полученные на (k−1)-м шаге (первоначально полагают ).

При этом возможны 2 случая:

− если , то все незаполненные позиции ν-й строки (позиции свободных переменных) заполняют нулями;

− если , то все незаполненные позиции μ-го столбца (позиции свободных переменных) заполняют нулями.

2. Определяют новые вектор производства и вектор потребления по правилам:

(1.31)

Таким образом, как следует из соотношений (1.31), изменяются только ν-й элемент вектора и μ-й элемент вектора .

При определении начального опорного плана ^ Х0 строят таблицу размера m×n. Для удобства вычислений справа к таблице приписывают n+m m-разрядных столбцов, в которые записывают вектора производства , а снизу к таблице приписывают n+m n-разрядных строк, в которые записывают вектора потребления .








1

2

∙∙∙

n

a(0)

a(1)

∙∙∙

a(n+m-1)




1




























2

























X0 =

∙∙∙




























m




























b(0)




























b(1)




























∙∙∙




























b(n+m-1)


























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

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

Элементы матрицы ^ С нумеруют, начиная с минимального, в порядке возрастания и в том же порядке нумеруют элементы матрицы Х0. Заполнение матрицы Х0 осуществляется по правилам метода северо-западного угла, но на каждом шаге в незаполненной части таблицы выбирается не левый верхний элемент, а элемент с минимальным порядковым номером.

Отметим, что после построения начального опорного плана нули в клетках матрицы, соответствующих свободным переменным, опускают, чтобы отличать эти клетки от клеток, содержащих нулевые базисные переменные. Таким образом, число заполненных клеток матрицы Х0 равно n+m−1, остальные клетки – свободные.

Для проверки оптимальности текущего опорного плана X используется оценочная матрица Z. Схема расчета Z заключается в следующем. Пунктам производства Аi , , и потребления Вj, , ставятся в соответствие числа ui и vj, называемые их потенциалами. Для каждой базисной переменной хij опорного плана потенциалы должны удовлетворять уравнению

(1.32)

Эти уравнения образуют систему, состоящую из n+m−1 уравнений, в которых фигурируют n+m неизвестных. Значения потенциалов можно определить из этой системы, придавая одному из них произвольное значение (обычно полагают u1=0).

Элементы zij оценочной матрицы определяются из соотношений

(1.33)

Очевидно, что элементы zij, соответствующие базисным переменным xij, будут равны нулю.

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

Для включения в базис выбирается свободная переменная xpq , которой соответствует максимальный положительный элемент zpq оценочной матрицы Z. Для определения исключаемой переменной в таблице Х строят замкнутый цикл, который начинается и заканчивается выбранной свободной переменной. Цикл состоит из последовательности горизонтальных и вертикальных (связанных) отрезков, концами которых должны быть базисные переменные. Это означает, что каждая вершина цикла должна содержать базисную переменную.

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

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

Таким образом, алгоритм решения транспортной задачи методом потенциалов заключается в следующем:

1. Определяют начальный опорный план Х0 (при этом число заполненных клеток должно быть равно n+m−1).

2. Используя соотношения (1.32), находят потенциалы ui, , vj, , соответственно пунктов производства и потребления.

3. Используя соотношения (1.33), вычисляют оценочную матрицу Z.

4. Проверяют условие оптимальности текущего опорного плана: оценочная матрица не содержит положительных элементов.

Если условие выполняется, то текущий опорный план является оптимальным опорным планом Х*.

Если условие не выполняется, то переходят к п. 5.

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

6. Производят сдвиг по циклу пересчета и получают новый опорный план. Затем переходят к п.2.

Вычисления завершают, когда найден оптимальный опорный план Х* (п.4).
1   2   3   4   5   6   7

Похожие:

По курсу математические методы и модели исследования операций для студентов специальности 080801 iconМетодические указания по проведению практических занятий и выполнению...
Методические указания предназначены для проведения практических занятий и выполнения домашних заданий по дисциплине «Экономико-математические...
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconКлючевые понятия 54 Контрольные вопросы 55
К65 Математические методы исследования операций в экономикеЎєспб: Питер, 2000. ЎЄ 208 с.: ил. ЎЄ (Серия «Краткий курс»)
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconПрограммные вопросы по курсу «Психология» для студентов специальности...
История предмет, структура педагогической психологии ее задачи и методы исследования
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconПлан семинарских занятий
Для студентов 4 курса очного отделения, обучающихся по специальности «математические методы в экономике»
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconМетодические указания к лабораторным работам по курсу рспсит для...
Методические указания к лабораторным работам по курсу рспсит для специальности 080801. 65-Прикладная информатика в экономике
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconДисциплина «Методология и методы психологического исследования» для...
Классификация методов психологического исследования (Классификация Пирьова; Б. Г. Ананьева; М. С. Роговина и Г. В. Залевского; В....
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconСеминар №2 по дисциплине «Методология и методы психологического исследования»...
Проблемная ситуация и проблема исследования. Требования к формулированию проблемы научного исследования
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconРабочая программа дисциплины математические методы в исторических исследованиях
Целью освоения дисциплины Математические методы в исторических исследованиях является формирование целостного, системного представления...
По курсу математические методы и модели исследования операций для студентов специальности 080801 icon1. Понятие о науке а/х и методы исследования, которыми она располагает
Математические методы используют для проверки точности опытов и установлении достоверности полученных результатов. Выявления кариляционных...
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconПрограмма междисциплинарного экзамена по специальности 080801. 65...
Охватывает вопросы ряда специальных дисциплин, предусмотренных учебным планом вэпи по данной специальности и позволяет оценить качество...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница