Реферат: Методические указания для выполнения контрольных работ для студентов специальности 1 53 01 01 05 "Автоматизация технологических процессов и производств (легкая промышленность)"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

"ВИТЕБСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ"


ОСНОВЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ


МЕТОДИЧЕСКИЕ УКАЗАНИЯ

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

для студентов специальности 1 – 53 01 01 - 05 "Автоматизация

технологических процессов и производств (легкая промышленность)"


ВИТЕБСК

2008

УДК 621.865.8


Основы исследования операций. Методические указания для выполнения контрольных работ для студентов заочного факультета специальности 1-53 01 01-05 “Автоматизация технологических процессов и производств (легкая промышленность)”.

Витебск: Министерство образования РБ, УО «ВГТУ», 2008 г.


Составитель: доц. каф. АТПП, к.ф.-м.н. Вислобоков Н.Ю.


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

Методические указания составлены в соответствии с учебной программой курса «Основы исследования операций», изучаемого студентами заочной формы обучения специальности 1-53 01 01-05 “Автоматизация технологических процессов и производств (легкая промышленность)”.


Одобрено кафедрой «Автоматизация технологических процессов и производств» УО «ВГТУ» ___.11.2008 г. протокол № _.


Рецензент: ст. преп. Куксевич В.Ф.

Редактор: доц. Смелков Д.В.


Рекомендовано к опубликованию редакционно-издательским советом УО «ВГТУ» ___.11.2008 г., протокол № _


Ответственный за выпуск Букин Ю.А.


Учреждение образования «Витебский государственный технологический университет»

_______________________________________________________________

Подписано в печать___________. Формат_________. Уч.-изд. лист._____. Печать ризографическая. Тираж_____экз. Заказ №_____. Цена_______руб.


Отпечатано на ризографе Учреждения образования «Витебский государственный технологический университет».

Лицензия № 02330/0133005 от 1 апреля 2004 г.

210035, Республика Беларусь, г. Витебск, Московский пр-т, 72.


СОДЕРЖАНИЕ


^ 1. ВВЕДЕНИЕ. ЦЕЛИ И ЗАДАЧИ КУРСА «ОСНОВЫ

ИССЛЕДОВАНИЯ ОПЕРАЦИЙ», ЕГО МЕСТО В

ОБРАЗОВАТЕЛЬНОМ ПРОЦЕССЕ СТУДЕНТОВ

ТЕХНОЛОГИЧЕСКИХ ВУЗОВ…..………………………………………..4


^ 2. БАЗОВАЯ УЧЕБНАЯ ПРОГРАММА КУРСА «ОСНОВЫ

ИССЛЕДОВАНИЯ ОПЕРАЦИЙ»……………...………………………..…4


3. ОБЩИЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ

КОНТРОЛЬНЫХ РАБОТ…...………………………………………………8


^ 4. РАБОТА №1. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ…………..……8


5. РАБОТА №2. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ ТАБЛИЧНЫМ

СИМПЛЕКС-МЕТОДОМ…..……………………………………………….9


^ 6. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ

КОНТРОЛЬНЫХ РАБОТ № 1 И № 2…………………………………......10


7. ЛИТЕРАТУРА………………………………………………………………18


^ 1 ВВЕДЕНИЕ. ЦЕЛИ И ЗАДАЧИ КУРСА «ОСНОВЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ», ЕГО МЕСТО В ОБРАЗОВАТЕЛЬНОМ ПРОЦЕССЕ СТУДЕНТОВ ТЕХНОЛОГИЧЕСКИХ ВУЗОВ.


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

В результате изучения дисциплины студент должен знать:

- общие принципы и методологию исследования операций;

- математические модели и классификацию типовых задач исследования операций;

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

Студент должен уметь:

- формулировать оптимизационные задачи, критерии оптимизации, строить математические модели задач исследования операций;

- осуществлять математическую постановку и разрабатывать компьютерные модели оптимизационных задач обоснования принятия решений;

- использовать стандартные алгоритмы и программы решения задач исследования операций.


^ 2 БАЗОВАЯ УЧЕБНАЯ ПРОГРАММА КУРСА «ОСНОВЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ»


Введение


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


ГЛАВА 1. Базовые понятия и определения ИССЛЕДОВАНИЯ ОПЕРАЦИЙ


Понятие и определение математической модели задачи исследования операций. Типовые задачи математического программирования и их модели. Факторы и факторные пространства, характеристики. Ограничения на факторы и характеристики, допустимые области решений. Критерий оптимизации – целевая функция. Векторно-матричные формы задач математического программирования. Классификация допустимых областей и задач математического программирования.


ГЛАВА 2. Линейное программирование


Примеры задач линейного программирования (ЗЛП). Формы записи задач линейного программирования, их эквивалентность и способы преобразования. Каноническая форма ЗЛП. Понятия плана, допустимого и оптимального плана. Геометрическая интерпретация ЗЛП и частных случаев решения. Графический метод решения ЗЛП. Понятие симплекса и симплексного метода решения ЗЛП. Симплексная таблица, анализ плана и свойств ЗЛП по симплексной таблице. Симплексные преобразования. Алгоритм симплекс-метода: общая идея, построение начального опорного плана, вычислительные процедуры. Реализация симплекс-метода на ЭВМ. Использование стандартных программ для решения ЗЛП.


ГЛАВА 3. Двойственность в линейном Программирова-нии


Понятие двойственности. Построение двойственных задач и их свойства. Математические модели двойственных ЗЛП, основные теоремы двойственности. Решение двойственной задачи и интерпретация результата.


^ ГЛАВА 4. ЭЛЕМЕНТЫ ТЕОРИИ ИГР


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

Решение матричных игр в смешанных стратегиях. Сведение матричной игры в смешанных стратегиях к паре двойственных задач линейного программирования. Алгоритм решения матричной игры в смешанных стратегиях.

Статистические игры. Критерии Байеса, Лапласа, Вальда, Сэвиджа, Гурвица для решения статистических игр.


^ ГЛАВА 5. ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ


Примеры и особенности целочисленных задач линейного программирования (ЦЗЛП). Метод отсечения решения ЦЗЛП. Понятие правильного отсечения. Общий алгоритм метода Гомори.


^ ГЛАВА 6. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

Математические модели задач нелинейного программирования и их классификация. Условия оптимальности задач нелинейного программирования: а) нелинейная задача на безусловный экстремум; б) задача нелинейного программирования с ограничениями равенствами; в) задача нелинейного программирования с ограничениями неравенствами.

Численные методы нелинейной безусловной оптимизации. Градиентные методы поиска безусловного экстремума. Метод наискорейшего спуска, градиентный метод с памятью. Квазиградиентные методы. Метод Ньютона безусловной оптимизации. Области применимости численных методов безусловной оптимизации.

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


^ ГЛАВА 7. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ


Понятие дискретной величины и дискретной модели. Математические модели задач дискретного программирования.

Графы, математические модели графов. Анализ графов по моделям матрицы инцидентности и матрицы смежности. Примеры задач дискретного программирования.


Заключение


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


^ ПРИМЕРНАЯ ТЕМАТИКА ЛАБОРАТОРНЫХ ЗАНЯТИЙ


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

Разработка процедуры нахождения начального опорного плана ЗЛП.

Решение матричной игры в смешанных стратегиях.

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

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


^ ПРИМЕРНАЯ ТЕМАТИКА ПРАКТИЧЕСКИХ ЗАНЯТИЙ


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

Анализ симплекс таблицы и решение задач линейного программирования симплекс-методом.

Нахождение начального опорного плана задачи линейного программирования.

Решение матричных игр в чистых стратегиях.

Решение статистических игр.

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

Решение задач нелинейного программирования методом множителей Лагранжа.

Решение задач нелинейного программирования градиентным методом.

Постановка и решение задач дискретного программирования.


^ ПРИМЕРНАЯ ТЕМАТИКА КОНТРОЛЬНЫХ РАБОТ


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

 Решение табличным симплекс-методом приведенных и не приведенных к каноническомой форме задач линейного программирования.


ЛИТЕРАТУРА


Вентцель, Е.С. Исследование операций: задачи, принципы, методология / Е.С. Вентцель -М.: Наука, Главная редакция физико-математической литературы, 1980. - 208 с.

Кузнецов, А.В. Математическое программирование / А.В. Кузнецов, Н.И. Холод -Мн.: Вышэйшая школа, 1994. - 221 с.

Кузнецов, А.В. Сборник задач по математическому программированию / А.В. Кузнецов и др. -Мн.: Вышэйшая школа, 1985. - 143 с.

Батищев, Д.И. Методы оптимального проектирования.: Учеб. Пособие для вузов / Д.И. Батищев -М.: Радио и связь, 1984. - 248 с.

Кузнецова, А. Б. Математика для экономистов на базе Mathcad / А.Б. Кузнецова, О. Мельникова, В. Новикова, А. Черняка С-Пб.: БХВ -Санкт-Петербург, 2003. - 485 с.

Таха, Х.А. Введение в исследование операций Вильямс / Х.А. Таха, - ISBN: 5-8459-0180-4, 2001. -127 с..

Хэмди, А. Введение в исследование операций / А. Хэмди – 6-е издание, 2006.

Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский - М.: Энергия, 1988.- 480с.

Прохоров, Г.В. Математический пакет Maple. / Г.В. Прохоров, и др. -М.: Петит.-1997.-200 с.

Норенков, И.П. Учебный курс “Оптимизация” / И.П. Норенков, -М.: Петит.-2007.-188 с.

Королев, В.А. Лекции по курсу "Иследование операций" / В.А. Королев, - М.: Энергия, 2003.- 180с.


^ 3. ОБЩИЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ КОНТРОЛЬНЫХ РАБОТ


При выполнении и оформлении контрольных работ следует:

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

использовать стандартные листы бумаги формата А4;

при расчетах пользоваться международной системой единиц СИ;

в формулах и на графиках пояснять все используемые обозначения;

перечень литературы должен быть оформлен в полном соответствии с требованиями библиографического описания документов.



4. РАБОТА № 1

^ РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ


Графическим методом решить задачу линейного программирования (ЗЛП) на максимум вариантам 1–16 (номер задачи в таблице 1 соответствует номеру варианта) и на минимум вариантам 17–32 (номер задачи соответствует номеру варианта, уменьшенному на 16). Решить ЗЛП на максимум/минимум означает найти экстремальное значение целевой функции и план, при котором достигается экстремум.


Таблица 1 – Задания к контрольной работе № 1

Задача № 1

Задача № 2

Задача № 3

Задача № 4













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.

Задача № 5

Задача № 6

Задача № 7

Задача № 8













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.

Задача № 9

Задача № 10

Задача № 11

Задача № 12













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.

Задача № 13

Задача № 14

Задача № 15

Задача № 16













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.













x1 ≥ 0; x2 ≥ 0.


5 РАБОТА № 2

^ РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ТАБЛИЧНЫМ СИМПЛЕКС-МЕТОДОМ


Привести ЗЛП к канонической форме и решить её табличным симплекс-методом (варианты заданий соответствуют номерам задач в таблице 2).


Таблица 2 – Задания к контрольной работе № 2

Задача № 1

Задача № 2

Задача № 3

























Задача № 4

Задача № 5

Задача № 6

























Задача № 7

Задача № 8

Задача № 9

























Задача № 10

Задача № 11

Задача № 12

























Задача № 13

Задача № 14

Задача № 15

























Задача № 16

Задача № 17

Задача № 18

























Задача № 19

Задача № 20

Задача № 21

























Задача № 22

Задача № 23

Задача № 24

























Задача № 25

Задача № 26

Задача № 27

























Задача № 28

Задача № 29

Задача № 30


























^ 6 МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ РАБОТ № 1, 2


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

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


Общая задача ЛП (ОЗЛП) – задача по отысканию целевой функции записанной в виде:


(1)

при ограничениях:



где cj, aij, bj – заданные действительные числа; а х = (x1 ,; ...; xn) – план задачи.

Каноническая форма записи ЗЛП:

(2)


Эквивалентность и способы преобразования

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

Пусть исходная ЗЛП имеет вид

(3)

(4)


Далее ЗЛП преобразуется к каноническому виду. Вводятся т дополнительных (балансовых) неотрицательных переменных xn+i ≥ 0 (i = 1, …, m). Для того чтобы неравенства ограничений типа преобразовать в равенства, к их левым частям прибавляются дополнительные переменные xn+i (i = 1, …, m1); для того чтобы неравенства ограничений типа преобразовать в равенства, из их левых частей вычитаются дополнительные переменные xn+i (i = m1+1, …, m). В целевую функцию балансовые переменные вводятся с коэффициентами, равными нулю.

Получается задача в канонической форме:

(5)

(6)

Система уравнений (6) эквивалентна системе неравенств (4), т.е. оптимальному решению ( x10; …; xn0) задачи (3)–(4) соответствует оптимальное решение ( x10; …; xn0; xn+10; …; xn+m0) задачи (5)–(6).


Геометрическая интерпретация и графическое решение ЗЛП

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

Пусть дана задача (7)

(8)

Геометрическая интерпретация ограничений. Каждое из ограничений (3.36) задает на плоскости x1Ox2 некоторую полуплоскость, пересечение которых является областью допустимых решений задачи.




Рисунок 1 – Геометрическая интерпретация целевой функции ЗЛП
Переход к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – непустое множество, например многоугольник A1 A2 A3 A4 A5 A6 на рисунке 1. Выберается произвольное значение целевой функции Z = Z0 . Получается . Это уравнение прямой линии. В точках прямой N M целевая функция сохраняет одно и то же постоянное значение Z0 . С учётом того, что в равенстве (7) Z–параметр, получается уравнение семейства параллельных прямых, называемых линиями уровня целевой функции.

Теперь необходимо определить направление возрастания (убывания) целевой функции. Пусть .

Тогда с1 и с2 – скорости возрастания Z вдоль осей ОX1 и OX2 , а вектор градиента показывает направление наискорейшего возрастания целевой функции (вектор антиградиента – наискорейшего убывания целевой функции).

Порядок графического решения ЗЛП:

строится область допустимых решений Ω.

строится вектор градиента/антиградиента.

проводится произвольная линия уровня.

при решении задачи на максимум линия уровня перемещается в направлении вектора градиента так, чтобы она касалась границы области допустимых решений (A4 на рис. 1). В случае решения задачи на минимум линию уровня перемещается в антиградиентном направлении (А1 на рис. 1).

Определяется оптимальный план х* и экстремальное значение целевой функции Z = z(х*).


Пример решения ЗЛП графическим методом

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





1. Определяется полуплоскость решений, ограниченная первым неравенством. Для этого строится прямая x1 + 2x2 = 1. В неравенство x1 + 2x2 ≤ 1 подставляется любая точка, например, (0; 0). После подстановки, в данном случае получается верное неравенство, значит точка (0; 0) находится в полуплоскости решений, ограниченных первым неравенством. Аналогично находим полуплоскости решений для остальных неравенств. Пересечение всех полуплоскостей будет областью допустимых решений (рис. П1а).

2. После определения частных производных Z (здесь с1=1; с2=1) строится вектор градиента (рис. 2).

3. Проводится линия уровня Z0, например, через (0; 0) (рис. 2).


4. Видно, что в данном случае точка минимума уже найдена. Далее необходимо “сфокусироваться” на области решений и путём параллельного переноса линии уровня вдоль направления вектора градиента найти точку максимума (рис. 3) – через точку максимума проведена вторая пунктирная линия уровня). Координаты точки максимума – координаты точки пересечения прямых (3x1 + x2 = 1) и (–x1 + 4.5x2 = 1).

5. Оптимальный план для задачи на минимум (x1 = 0; x2 = 0), min(Z) = 0, а для задачи на максимум (x1 = 0.241379; x2 = 0.275862), max(Z) = 0.517241.






Рисунок 2 – Определение области допустимых решений Ω ЗЛП и направления градиента (пунктирная прямая – линия уровня).

Рисунок 3 – Графическое решение ЗЛП: определение максимума и минимума целевой функции Z.


Симплексный метод

Общая идея симплексного метода: последовательное улучшение плана путём перехода от одного допустимого плана к другому – нехудшему.

Пусть ЗЛП представлена системой ограничений в каноническом виде:


(9)


^ Ограничение ЗЛП имеет предпочтительный вид, если при неотрицательности правой части левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения-равенства – с коэффициентом, равным нулю.

Если каждое ограничение ЗЛП в каноническом виде имеет предпочтительный вид, то говорят, что система ограничений представлена в предпочтительном виде.

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

Например, в системе ограничений:

базисными являются переменные х2, х3 и х4, свободными x1, x5; начальный опорный план (0, 10, 80, 32, 0)

Для решения симплексным методом ЗЛП в неканонической форме переходят к эквивалентной ЗЛП в канонической форме (см. пункт “Эквивалентность и способы преобразования”).

Симплексные таблицы. Признак оптимальности опорного плана.

При решении ЗЛП симплексным методом используются симплексные таблицы, заполняемые согласно условию задачи. Составляется симплексная таблица для ЗЛП c ограничениями (9) (таблица 3).


Таблица 3 –Симплексная таблица.

БП

CБ

А0

x1

xi

xm

xm+1

xj

xn

c1

ci

cm

cm+1

cj

cn

x1

c1

b1

1

0

0

a1 m+1

a1j

a1 n

xi

ci

bi

0

1

0

…

…

…

xm

cm

bm

0

0

1

am m+1

am j

am n

zj-cj

Δ0

0

0

0

Δm+1

Δj

Δn


сБ = (с1; с2; …; сm) – вектор коэффициентов целевой функции при базисных переменных;

А0=(b1; b2; … ;bm)T – вектор-столбец свободных переменных;

Аij=(a1j; a2j; … ;amj)T – вектор-столбец переменных;

aij – коэффициент при xj, в j-ом ограничении.

– оценки ( Δ0 =max(min)Z ). (10)

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

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

Переход к нехудшему опорному плану.

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


План перехода к следующей итерации

Определяются разрешающие столбец (j0), строку(i0) и элемент (ai0j0).

Вводятся разрешающий элемент в базис (xi↔xj, где xi – “старая” базисная переменная, а xj – “новая” базисная переменная ).

Все элементы разрешающей строки делятся на разрешающий элемент.

Все элементы разрешающего столбца, кроме разрешающего элемента, зануляются.

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

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

Разрешающий столбец .

Для положительных элементов разрешающего столбца вычисляются симплексные соотношения, и выбирается разрешающая строка i0 по правилу


.


Элемент, находящийся на пересечении i0 и j0 () – разрешающий.

Верхним индексом обозначается номер итерации. Переменная, соответствующая разрешающему столбцу, вносится в базис (s+1) итерации вместо переменной, соответствующей разрешающей строке базиса s-ой итерации. Пересчёт элементов таблицы (за исключением элементов разрешающих строки и столбца) осуществляется по правилу


, (11)


где Ã матрица, объединяющая А0, коэффициенты при xij ограничениях и оценочную строку (Δ) (визуально в нахождении aijs+1 участвуют элементы, находящиеся в углах прямоугольника, одна из диагоналей которого – разрешающий–искомый элемент).

Контроль вычислений осуществляется путём пересчёта оценок по формулам (10) и сравнением их с полученными согласно (11).


Пример решения ЗЛП табличным симплекс методом.

Привести задачу линейного программирования к канонической форме и решить её табличным симплекс-методом.



Получили ЗЛП в каноническом виде (эквивалентную исходной), система ограничений которой представлена в предпочтительном виде. Заполним симплексную таблицу (добавив столбец с номером итерации “№” и симплексными отношениями “СО”). Для упрощения понимания в левом верхнем углу ячеек таблицы 4 (нулевой итерации) записаны условные обозначения, использовавшиеся при изложении теоретического материала.


Таблица 4 – Симплексная таблица на нулевой итерации.

№

БП

cБ

A0

x1

x2

x3

x4

x5

СО

c1

3

c2

4

c3

0

c4

0

c5

0

0

x3

с3

0

b3

550

a11

1

a12

1

a13

1

a14

0

a15

0

550

x4

с4

0

b4

1200

a21

2

a22

3

a23

0

a24

1

a25

0

400

x5

с5

0

b5

9600

a31

12

a32

30

a33

0

a34

0

a35

1

320

zj-cj

Δ0

0

Δ1

-3

Δ2

-4

Δ3

0

Δ4

0

Δ5

0





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




Симплексная таблица на первой итерации – таблица 5.


Таблица 5 – Симплексная таблица на первой итерации.

№

БП

cБ

A0

x1

x2

x3

x4

x5

3

4

0

0

0

1

x3

0

230

3/5

0

1

0

-1/30

x4

0

240

4/5

0

0

1

-0.1

x2

4

320

2/5

1

0

0

1/30

zj-cj

1280

-7/5

0

0

0

2/15




ΔКВ

1280

-7/5

0

0

0

2/15


Cтрока i0 и cтолбец j0 заполняются в соответствии с пунктами c). и d). плана перехода к следующей итерации. Пример: элемент b31 (прямоугольник с диагональю b30–a320 ) вычисляется по формуле

.

Остальные элементы таблицы вычисляются аналогично. Контроль вычислений приведён в строке ΔКВ.

Например: .

Опорный план нехудший ( [Z1(x)=1280] > [Z1(x)=0] ), но и не оптимальный – переход к следующей итерации. На 1-ой итерации разрешающий элемент a21=4/5, соответственно при переходе ко второй итерации x1 вводится в базис на место x4 (таблица 6).


Таблица 6 – Симплексная таблица на второй итерации.

№

БП

cБ

A0

x1

x2

X3

x4

x5

3

4

0

0

0

2

x3

0

50

0

0

1

-3/4

1/24

x1

3

300

1

0

0

5/4

-1/8

x2

4

200

0

1

0

-0.5

1/12

zj-cj

1700

0

0

0

7/4

-1/24




Δкв

1700

0

0

0

7/4

-1/24


Разрешающий элемент a15=1/24, соответственно вводится в базис x5 на место x3 и осуществляется переход к следующей итерации (таблица 7).


Таблица 7 – Симплексная таблица на третьей итерации.

№

БП

cБ

A0

x1

x2

x3

x4

x5

3

4

0

0

0

3

x5

0

1200

0

0

24

-18

1

x1

3

450

1

0

3

-1

0

x2

4

100

0

1

-2

1

0

zj-cj

1750

0

0

1

1

0




Δкв

1750

0

0

1

1

0


Оптимальный план найден x*(x1=450, x2=100, x3=0, x4=0, x5=1200), соответственно оптимальный план исходной задачи x*(x1=450, x2=100), а maxZ(450,100)=1750.


7. ЛИТЕРАТУРА


Вентцель, Е.С. Исследование операций: задачи, принципы, методология / Е.С. Вентцель -М.: Наука, Главная редакция физико-математической литературы, 1980. - 208 с.

Кузнецов, А.В. Математическое программирование / А.В. Кузнецов, Н.И. Холод -Мн.: Вышэйшая школа, 1994. - 221 с.

Батищев, Д.И. Методы оптимального проектирования.: Учеб. Пособие для вузов / Д.И. Батищев -М.: Радио и связь, 1984. - 248 с.

Таха, Х.А. Введение в исследование операций Вильямс / Х.А. Таха, - ISBN: 5-8459-0180-4, 2001. -127 с..

Хэмди, А. Введение в исследование операций / А. Хэмди – 6-е издание, 2006.