- •Глава 1. Линейное программирование 3
- •Глава 2. Транспортная задача линейного программирования (тз) 68
- •Глава 3. Динамическое программирование 98
- •Глава 1. Линейное программирование
- •1.1. Математическая модель задачи линейного программирования
- •1.2. Формы записи задач линейного программирования
- •Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой
- •1.3. Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными
- •Алгоритм графического метода решения злп с двумя переменными
- •1.4. Графический метод решения задач линейного программирования сnпеременными
- •1.5. Симплексный метод решения задач линейного программирования
- •Алгоритм решения злп симплексным методом
- •Нахождение начального опорного плана злп ( )
- •Нахождение начального опорного плана злп методом искусственного базиса
- •Нахождение начального опорного плана злп методом Жордановых исключений
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при решении злп на
- •Переход к новому опорному плану
- •1.6. Двойственные задачи линейного программирования
- •Правила построения двойственной задачи.
- •Глава 2. Транспортная задача линейного программирования (тз)
- •2.1. Математическая модель транспортной задачи
- •Закрытая и открытая модели транспортной задачи
- •2.2. Решение транспортной задачи
- •Алгоритм решения транспортной задачи
- •Нахождение начального опорного плана методом «минимального элемента»
- •Нахождение начального опорного плана методом «северо-западного угла»
- •Нахождение начального опорного плана методом Фогеля
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов
- •Переход к новому опорному плану
- •Цикл пересчета
- •Глава 3. Динамическое программирование
- •3.1. Задача оптимального распределения ресурсов
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •3.2. Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •Список использованной литературы
Исследование на оптимальность опорного плана при решении злп на
Заполним симплексную таблицу (табл. 1.2), исходя из задачи, записанной в виде:
; (1.20)
(1.21)
где , а – предпочтительные переменные.
Если начальный опорный план был найден методом Жордановых исключений, то воспользуемся таблицей, в которой уже найден начальный опорный план.
Оценками называются элементы симплексной таблицы, расположенные на пересечении последней строки (Z-строки) и столбцов «СП» (элементы табл. 1.2).
Если все оценки положительные (отрицательные) – найденный в таблице план оптимальный и единственный.
Если все оценки неотрицательные (неположительные), т.е. наряду с положительными (отрицательными) оценками присутствуют нулевые, – найденный в таблице план оптимальный, но не единственный.
Если есть отрицательные (положительные) оценки, а в соответствующих им столбцах нет положительных элементов, то целевая функция неограниченна и задача не имеет решения.
Если есть отрицательные (положительные) оценки и в соответствующих им столбцах есть положительные элементы, то можно перейти к новому опорному плану, более близкому к оптимальному.
Переход к новому опорному плану
1) В табл. 1.2 выбираем разрешающий элемент в столбце с наибольшей по абсолютной величине отрицательной (положительной) оценкой. Пусть столбец будет разрешающим, тогда еслидля, то– разрешающий элемент.
2) Перейти к новому плану преобразовав симплексную таблицу по алгоритму шага Жордановых исключений.
Пример 1.17
Решить симплексным методом ЗЛП, составленную в примере 1.2.
Решение
В предыдущем примере 1.16 для этой задачи был найден начальный опорный план. Для проверки его на оптимальность воспользуемся табл. 1.6, в которой он записан. Т.к. среди оценок есть положительные оценки, то найденный опорный план не оптимален. Поскольку единственная положительная оценка находится в столбце , то он и будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (табл. 1.7). По наименьшему отношению выберем разрешающую строку. Т.к., то-строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент «1» (табл. 1.7).
Таблица 1.7
|
|
СП |
| ||
БП |
1 |
|
|
отношения | |
|
6,2 |
0 |
0,8 |
6,2/0,8 | |
|
6 |
0,5 |
0 |
– | |
|
3,8 |
1 |
–0,8 |
– | |
|
4 |
–0,5 |
1 |
4/1 | |
Z |
61,6 |
–6 |
2,4 |
|
Шаг Жордановых исключений переводит табл. 1.7 в табл. 1.8, в которой будет получен новый опорный план, более близкий к оптимальному.
Таблица 1.8
|
|
СП | |
БП |
1 |
|
|
|
3 |
0,4 |
–0,8 |
|
6 |
0,5 |
0 |
|
7 |
0,6 |
0,8 |
|
4 |
–0,5 |
1 |
Z |
52 |
–4,8 |
–2,4 |
Т.к. все оценки отрицательные, то полученный в табл. 1.8 опорный план оптимален и единственен. Выпишем его, приравняв свободные переменные к нулю, т.е. , а базисные переменные – к соответствующим элементам столбца «1», т.е..
Итак, оптимальный план, и.
Перейдем к решению исходной задачи (имеющей переменные ):и.
Пример 1.18
Решить симплексным методом ЗЛП примера 1.14.
Решение
Воспользуемся найденным в примере 1.14 начальным опорным планом.
Для проверки плана на оптимальность заполним симплексную таблицу (табл.1.9), переписав М-задачу в виде (1.20 – 1.21):
Таблица 1.9
|
|
|
СП |
|
| |
БП |
1 |
|
|
|
отношения | |
|
2 |
–1 |
4 |
–1 |
2/4 | |
|
8 |
0 |
1 |
2 |
8/1 | |
|
6 |
0 |
–3 |
4 |
– | |
Z |
2М |
–М–6 |
4М+4 |
–М–1 |
|
Т.к. среди оценок есть положительные оценки, то найденный опорный план не оптимален. Поскольку единственная положительная оценка находится в столбце , то он и будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (табл. 1.9). По наименьшему отношению выберем разрешающую строку. Т.к., то-строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент «4» (табл. 1.9). Шаг Жордановых исключений переводит табл. 1.9 в табл. 1.10, в которой будет получен новый опорный план, более близкий к оптимальному.
Таблица 1.10
|
|
|
СП |
|
БП |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z |
–2 |
–5 |
|
0 |
Полученный в табл. 1.10 опорный план оптимален, но не единственен, т.к. наряду с отрицательными оценками присутствует нулевая оценка. Выпишем его, приравняв свободные переменные к нулю, т.е. , а базисные переменные – к соответствующим элементам столбца «1», т.е..
Итак, оптимальный план и. Перейдем к решению исходной задачи (имеющей переменные):и.
Пример 1.19
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
Здесь каждое ограничение системы имеет предпочтительную переменную. Начальный опорный план найдем, приравняв свободные переменные ик нулю, а предпочтительные переменныеи– к правой части соответствующих ограничений. Итак, начальный опорный план:и.
Для проверки плана на оптимальность заполним симплексную таблицу. Для этого представим каноническую запись в виде (1.20 – 1.21):
Заполним симплексную таблицу:
|
|
СП |
| |
БП |
1 |
|
|
отношения |
|
2 |
2 |
–1 |
2/2 |
|
4 |
1 |
0 |
4/1 |
|
0 |
3 |
–1 |
|
Т.к. среди оценок есть отрицательная оценка, а в соответствующем столбце нет положительных элементов, то целевая функция неограниченна и задача не имеет решения.
Пример 1.20
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (табл. 1.11) представим каноническую форму записи в виде (1.18 – 1.19):
Здесь в первом ограничении предпочтительная переменная оставлена в левой части.
Таблица 1.11
|
|
СП |
| ||
БП |
1 |
|
|
|
отношения |
|
2 |
2 |
1 |
0 |
2/1 |
0 |
12 |
3 |
4 |
–1 |
12/4 |
|
5 |
–1 |
–4 |
0 |
|
Начальный опорный план будет найден, если в первом столбце таблицы все нули в ходе преобразований таблицы будут заменены переменными.
Пусть -столбец будет разрешающим. Для нахождения разрешающей строки составим отношения свободных членов к соответствующим положительным элементам этого столбца. Т.к., то элемент «1» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.11 в табл. 1.12.
Таблица 1.12
|
|
СП | ||
БП |
1 |
|
|
|
|
2 |
2 |
1 |
0 |
0 |
4 |
–5 |
–4 |
–1 |
|
13 |
7 |
4 |
0 |
Т.к. в табл.1.12 есть 0-строка, в которой нет положительных элементов в основной части таблицы, то опорный план отсутствует, и задача не имеет решения вследствие несовместности системы ограничений.
Пример 1.21
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
где .
Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (табл. 1.13) представим каноническую форму записи в виде (1.18 – 1.19):
где .
Здесь во втором ограничении предпочтительная переменная оставлена в левой части.
Таблица 1.13
|
|
СП |
| |||
БП |
1 |
|
|
|
|
отношения |
0 |
3 |
–3 |
3 |
–1 |
–1 |
3/3 |
|
1 |
–1 |
1 |
–2 |
0 |
1/1 |
|
0 |
–12 |
12 |
–2 |
0 |
|
Т.к. только в -столбце есть положительные элементы в основной части таблицы, то только он может быть разрешающим. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Этои(табл. 1.13). Т.к., то любая строка может быть разрешающей, но для получения начального опорного плана необходимо избавиться от нулей в столбце «БП», следовательно, целесообразно 0-строку взять разрешающей. На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент «3» и шаг Жордановых исключений переводит табл. 1.13 в табл. 1.14.
Таблица 1.14
|
|
СП | ||
БП |
1 |
|
|
|
|
1 |
–1 |
|
|
|
0 |
0 |
|
|
|
–12 |
0 |
2 |
4 |
В табл. 1.14 найден начальный опорный план: и. Этот опорный план оптимален, но не единственен, т.к. наряду с положительными оценками присутствует нулевая оценка.
Итак, оптимальный план и. Перейдем к решению исходной задачи (имеющей переменные, где):и.
Пример 1.22
Решить симплексным методом ЗЛП:
Решение
Математическую модель задачи представим в канонической форме с неотрицательной правой частью:
Найдем начальный опорный план ЗЛП методом Жордановых исключений. Для заполнения первой таблицы Жордана (табл. 1.15) представим каноническую форму записи в виде (1.18 – 1.19):
Здесь предпочтительные переменные иоставлена в левой части.
Таблица 1.15
|
|
СП |
| |||
БП |
1 |
|
|
|
|
отношения |
|
6 |
3 |
2 |
–1 |
0 |
6/3 |
0 |
2 |
1 |
–4 |
0 |
–1 |
2/1 |
|
5 |
1 |
–1 |
0 |
0 |
5/1 |
|
20 |
8 |
5 |
–3 |
0 |
|
Пусть -столбец будет разрешающим. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Это,и(табл. 1.15). Т.к. минимальные отношения, то любая из этих двух строк (-строка или 0-строка) может быть разрешающей, но для получения начального опорного плана необходимо избавиться от нулей в столбце «БП», следовательно, целесообразно 0-строку взять разрешающей. На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент «1» и шаг Жордановых исключений переводит табл. 1.15 в табл. 1.16.
Таблица 1.16
|
|
СП |
| |||
БП |
1 |
|
|
|
отношения | |
|
0 |
14 |
–1 |
3 |
0/14 | |
|
2 |
–4 |
0 |
–1 |
– | |
|
3 |
3 |
0 |
1 |
3/3 | |
|
4 |
37 |
–3 |
8 |
|
В табл. 1.16 найден начальный опорный план: и. Т.к. среди оценок есть положительные, то найденный план не оптимален. Перейдем к новому плану, более близкому к оптимальному. Выбираем разрешающий элемент в столбце с наибольшей по абсолютной величине положительной оценкой. Это будет-столбец. Найдем отношения свободных членов к соответствующим положительным элементам этого столбца. Этои(табл. 1.16). Т.к., то элемент «14» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.16 в табл. 1.17.
Таблица 1.17
|
|
СП |
| |||
БП |
1 |
|
|
|
отношения | |
|
0 |
|
|
|
0: | |
|
2 |
|
|
|
– | |
|
3 |
|
|
|
3: | |
|
4 |
|
|
|
|
Т.к. среди оценок есть положительная, то найденный план не оптимален. Перейдем к новому плану, более близкому к оптимальному. Выбираем разрешающий элемент в столбце с единственной положительной оценкой. Это будет -столбец. По наименьшему отношению выбираем-строку разрешающей. Тогда элемент «» будет разрешающим. Шаг Жордановых исключений относительно найденного разрешающего элемента переводит табл. 1.17 в табл. 1.18.
Таблица 1.18
|
|
СП | ||
БП |
1 |
|
|
|
|
0 |
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
Т.к. все оценки отрицательные, то полученный в табл. 1.18 опорный план оптимален и единственен. Выпишем его, приравняв свободные переменные к нулю, т.е. , а базисные переменные – к соответствующим элементам столбца «1», т.е..
Итак, оптимальный план, и.
Перейдем к решению исходной задачи (имеющей переменные ):и.
Задачи
Решить ЗЛП симплексным методом (1.5.1 – 1.5.8)
1.5.1 ;
1.5.3 ;
1.5.5 ;
1.5.7 ;
|
1.5.2 ;
1.5.4 ;
1.5.6 ;
1.5.8 ;
|
1.5.9 – 1.5.12
Решить задачи 1.1.5 – 1.1.8 (соответственно) симплексным методом.
1.5.13 – 1.5.16
Решить задачи 1.2.1 – 1.2.4 (соответственно) симплексным методом.
1.5.17 – 1.5.26
Решить задачи 1.3.3 – 1.3.12 (соответственно) симплексным методом.
1.5.27 – 1.5.34
Решить задачи 1.4.1 – 1.4.8 (соответственно) симплексным методом.