Краткий курс лекций Саратов 2012 министерство сельского хозяйства






НазваниеКраткий курс лекций Саратов 2012 министерство сельского хозяйства
страница3/7
Дата публикации21.01.2015
Размер1.23 Mb.
ТипУчебное пособие
e.120-bal.ru > Документы > Учебное пособие
1   2   3   4   5   6   7
Симплекс-метод для решения задач линейного программирования.
С увеличением числа неизвестных геометрический метод решения ЗЛП становится затруднительным при трех переменных и невозможным при большем числе переменных.

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

Изложим суть симплекс-метода на примере задач с 5 неизвестными.

Пусть ЗЛП приведена к виду
(20)
при ограничениях:
, (21)
где ,
(22)
Про систему ограничений (21) говорят, что она имеет допустимый вид, если одни неизвестные () выражаются через остальные (), причем свободные члены этих выражений неотрицательны ().

Неизвестные и называются базисными, а неизвестные свободными.

Возможны два принципиальных случая:

1? Все коэффициенты при свободных неизвестных в выражении для F неположительны: и . Тогда для всякого неотрицательного решения системы уравнений (21) имеем и , а потому
или .
Следовательно, базисное решение является оптимальными, т. е. задача решена.

2? Имеется свободное неизвестное, коэффициент при котором в выражении для F положителен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны.

Для определенности положим . Исходя из базисного решения, станем наращивать значение , не меняя . Тогда значения базисных неизвестных будут оставаться неотрицательными:
,
а значение будет неограниченно возрастать, т.е. и задача решения не имеет.

Решения ЗЛП редуцируются к одному из случаев 1? или 2? путем перехода к новому базису, в котором целевая функция не уменьшит своего значения для базисного решения, а новая система ограничений должна иметь допустимый вид. Преобразование базиса и перестройку целевой функции и системы ограничений называют шагом в решении ЗЛП. Таким образом, сделав нужное число шагов, решают ЗЛП (20) – (22).

Применим симплекс-метод к первой задаче.

I. Основная задача в примере 1 имеет вид


Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(23)
(24)
Теперь приведем (23) к допустимому виду – неизвестные , и выразим через и , при этом свободные члены в правых частях полученных уравнений неотрицательны:
(25)
Здесь , и – базисные неизвестные, а и – свободные неизвестные.

Шаг 1: положим в (25) и , тогда , , . Получим неотрицательное решение системы уравнений (25). Его называют базисным решением. Для него .

Шаг 2: положим в (25) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.

.

Решая эти неравенства, найдем наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (25) к допустимому виду:
(26)
Получим неотрицательное решение системы уравнений (26). Для него
(27)
примет значение .

Сделаем выводы.

Во-первых, значение F по сравнению с 1-ым шагом увеличилось.

Во-вторых, в (27) коэффициент при отрицательный и для дальнейшего увеличения значения F надо положить и наращивать .

Шаг 3: положим в (26) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.

.

Откуда находим наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (27) к допустимому виду:
(28)
Получили неотрицательное решение системы уравнений (28). Для него
(29)
примет значение .

Сделаем выводы.

Во-первых, значение F по сравнению со 2-ым шагом увеличилось.

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

при . Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу: предприятие получит наибольшую прибыль 1104 единиц при изготовлении 36 единиц товара и 6 единиц товара , при этом остатки ресурсов и равны нулю (), а остаток ресурса равен 12 единицам.

Если решается ЗЛП, в которой требуется найти минимум целевой функции, то задачу либо сводят к рассмотренной выше задаче с целевой функцией , либо с помощью шагов приводят к одному из двух принципиальных случаев:

1? Все коэффициенты при свободных неизвестных в выражении для F неотрицательны: и . Тогда базисное решение является решением задачи.

2? Имеется свободное неизвестное, коэффициент при котором в выражении для F (20) отрицателен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны. Тогда задача решения не имеет.

Применим симплекс-метод ко второй задаче, Основная задача в примере 2 имеет вид


Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(30)
(31)
Приведем ограничения (30) к допустимому виду. Как показано выше, в качестве базисных неизвестных следует выбирать такие неизвестные, каждая из которых входит только в одно из уравнений системы ограничений (31), при этом нет таких уравнений системы, в которые не входит ни одна из этих неизвестных, и каждая базисная неизвестная имеет тот же знак, что и свободный член.

Нетрудно видеть, что , и не могут быть базисными неизвестными. Действительно,
(32)
и знаки , и противоположны знакам свободных членов.

Для выделения базисных неизвестных из системы ограничений (30) необходима ее перестройка.

Полагая в (32) (или ) найдем из условий неотрицательности , и :
.
наибольшее значение . Тогда и систему (32) запишем в виде
(33)
Получили систему ограничений, имеющую допустимый вид: , и – базисные неизвестные, и – свободные неизвестные. Перейдем к процедуре шагов.

Шаг 1: положим в (33) и , тогда получим базисное решение , для которого целевая функция
(34)
примет значение .

В (5.15) коэффициент при положительный и для дальнейшего уменьшения значения f надо положить и наращивать .

Шаг 2: положим в (33) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Откуда находим . Тогда . Объявив и свободными неизвестными, приведем (33) к допустимому виду:
(35)
Из (35) получим базисное решение . Для него
(36)
примет значение .

В (36) коэффициенты при свободных неизвестных положительны и дальнейшее уменьшение значения f невозможно: при . Задача решена.

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

Ежесуточная диета, обеспечивающая необходимое количество питательных веществ, состоит из единиц продукта , единиц продукта и ее минимальная стоимость единиц. При этом потребности организма в питательных веществах A и B отвечают требуемым минимальным объемам единиц и единиц соответственно (т.к. и ), а потребности в питательном веществе С больше требуемого минимального объема единиц на единиц.

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

Ответ утвердительный и содержится в следующей теореме.

Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.
Симплекс-таблицы для решения ЗЛП.

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

Оказывается, эти преобразования можно записать в виде последовательности однотипно заполненных таблиц, называемых симплекс-таблицами.

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

  1. Первая основная задача.

Для заполнения первой симплекс-таблицы необходимо переписать целевую функцию F и систему ограничений в виде:



Заполним таблицу


Базисные неизвестные

Свободные члены





















42

1


1

1

0

0



48

1

2

0

1

0



72

1

4

0

0

1

F

0

–25

–34

0

0

0


В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», отрицательные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем (из двух отрицательных чисел –25 и –34 выбирают меньшее по модулю), над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над –25 есть три положительных числа: 1; 1 и 1.

Найдем


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

Заполняем вторую симплекс-таблицу. Строка () из первой таблицы становится в ней строкой (). Далее преобразуем строки (), () и (F) первой таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью

  1. вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы;

  2. вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы;

  3. умножим элементы строки () на 25, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) второй таблицы.

В результате получим следующую симплекс-таблицу


Базисные неизвестные

Свободные члены





















42

1

1

1

0

0



6

0

1


–1

1

0



30

0

3

–1

0

1

F

1050

0

–9

25

0

0


В строке (F) есть отрицательное число –9. Поэтому продолжим поиск оптимального решения. Над –9 есть три положительных числа: 1; 1 и 3.

Найдем

Элемент, стоящий на пересечении строки () и столбца () разрешающий и равен 1. Неизвестная вводится в базис, а неизвестная выводится из него.

Заполняем третью симплекс-таблицу. Строка () из второй таблицы становится в ней строкой (). Далее преобразуем строки (), () и (F) второй таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью

  1. вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () третьей таблицы;

  2. умножим элементы строки () на 3, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () третьей таблицы;

  3. умножим элементы строки () на 9, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) третьей таблицы.

В результате получим следующую симплекс-таблицу


Базисные неизвестные

Свободные члены





















36

1

0

2

–1

0



6

0

1

–1

1

0



12

0

0

2

–3

1

F

1104

0

0

16

9

0


В строке (F) нет отрицательных чисел. Получили оптимальное решение:

при , , , .

Замечание. Симплекс-таблицы удобнее «пристыковывать» друг к другу по вертикали, что позволяет не писать многократно заглавную строку

  1. Вторая основная задача.

Для заполнения первой симплекс-таблицы перепишем целевую функцию F и систему ограничений (6.14), имеющую допустимый вид, следующим образом:



Заполним таблицу


Базисные неизвестные

Свободные члены





















9

3

1

0

–1

0



21

8


0

1

–3

0



64

23

0

0

–8

1

F

144

40

0

0

–16

0



1,125

0

1

–0,375

0,125

0



2,625

1

0

0,125

–0,375

0



3,625

0

0

–2,875

0,625

0

F

39

0

0

–5

–1

0


В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», положительные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем . Над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над 40 есть три положительных числа: 3; 8 и 23.

Найдем

Элемент, стоящий на пересечении строки () и столбца () разрешающий и равен 8. Неизвестная вводится в базис, а неизвестная выводится из него. Все элементы строки () разделим на разрешающий элемент. Полученные результаты запишем в новую симплекс-таблицу в строке ().

Преобразуем строки (), () и (F) первой таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью

  1. умножим элементы строки () на 3, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы;

  2. умножим элементы строки () на 23, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы;

  3. умножим элементы строки () на 40, вычтем из соответствующих элементов строки (F), и запишем полученные результаты в строку (F) второй таблицы.

В строке (F) нет положительных чисел. Получили оптимальное решение:

при , , , .
Замечание. Первая симплекс-таблица второй основной задачи была заполнена с учетом того, что система ограничений (6.11) была предварительно сведена к допустимому виду (6.14), т.е. был найден допустимый базис. Зачастую поиск такого базиса довольно затруднителен. Рассмотрим следующий метод нахождения допустимого базиса, который называют методом искусственного базиса или М-методом.
1   2   3   4   5   6   7

Похожие:

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconРоссийской Федерации Федеральное государственное бюджетное образовательное...
Учет и анализ: Краткий курс лекций для студентов направления подготовки 080200. 62 Менеджмент / Сост.: Кудряшова Е. В., Павленко...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconИнформация подготовлена по материалам, полученным из сети «Интернет»11. 03. 2012
России по реализации федеральной целевой программы «Социальное развитие села до 2013 года». Как сообщили 6 марта корреспонденту в...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconСписок новых книг, поступивших в библиотеку в ноябре 2012 года
Агафонов В. В. Криминалистика: краткий курс лекций – М.: Юрайт, 2013. – 184с. 10 экз

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconПоложение о Министерстве сельского хозяйства и продовольствия Республики...
Министерство сельского хозяйства и продовольствия Республики Татарстан (далее Министерство) является исполнительным органом государственной...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconПрограмма импортозамещения продукции в пензенской области на 2015-2017 годы
Министерство сельского хозяйства Пензенской области, Министерство строительства и жилищно-коммунального хозяйства Пензенской области,...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций Производственная безопасность. Часть 3
Пламя возникает в результате сложного взаимодействия химических и физических процессов

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

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconД. А. Медведев [и др.] // Экономика сельского хозяйства России. 2012. № С. 7-13
Агропромышленный комплекс требует повышенного внимания [Текст] / Д. А. Медведев [и др.] // Экономика сельского хозяйства России....

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по дисциплине
Учебное пособие предназначено для студентов Стгау всех направлений, изучающих курс «История, традиции и обычаи народов Северного...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по статистике автор: ильина г. Г.,к э. н
Статистика-наука,которая изучает приемы и методы сбора и обработки информации о каких –либо явлениях и процессах, происходящих в...






При копировании материала укажите ссылку © 2016
контакты
e.120-bal.ru
..На главную