Линейное программирование, учебное пособие, Палий И.А., 2008

Линейное программирование, учебное пособие, Палий И.А., 2008.

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

Фрагмент из книги.
8. Бройлерное хозяйство фабрики насчитывает 20000 цыплят, которых выращивают до 8-недельного возраста, а затем продают. Недельный расход корма для цыплят зависит от их возраста, но можно положить, что в среднем одному цыпленку требуется 500 г корма в сутки.
Кормовой рацион должен удовлетворять определенным требованиям по питательности, для чего составляются смеси из различных ингредиентов. Для простоты ограничимся тремя составляющими: известняком, зерном и соевыми бобами. Учитываются три вида питательных веществ: кальций, белок, клетчатка. Данные о содержании питательных веществ в ингредиентах приведены в таблице.





Оглавление
ВВЕДЕНИЕ.
ГЛАВА 1
ЧТО ТАКОЕ ЗАДАЧА ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ.
1.1. Математическая модель задачи линейного программирования.
1.2. Примеры построения математических моделей задач линейного программирования.
1.3. Задачи.
ГЛАВА 2
ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
С ДВУМЯ ПЕРЕМЕННЫМИ.
2.1. Графическое решение ЗЛП с двумя переменными.
2.2. Понятие об анализе на чувствительность.
2.3. Задачи.
ГЛАВА 3
ОПОРНЫЕ РЕШЕНИЯ.
3.1. Определение канонической формы ЗЛП.
3.2. Приведение произвольной ЗЛП
к каноническому виду.
3.3. Решение системы линейных уравнений по методу Гаусса (методу исключения неизвестных).
3.4. Опорные решения.
3.5. Переход от одного опорного решения к другому
3.6. Вырожденные и невырожденные опорные решения.
3.7. Выражение целевой функции Z через свободные переменные. Оценки свободных переменных.
3.8. Анализ значений целевой функции Z, выраженной через свободные переменные. Признак неограниченности целевой функции
в допустимой области.
3.9. Анализ значений целевой функции Z, выраженной через свободные переменные. Признак оптимальности опорного решения
3.10. Теорема о достижимости оптимального значения целевой функции ЗЛП на опорном решении.
3.11. Задачи.
ГЛАВА 4
СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗЛП.
4.1. Описание симплекс-метода.
4.2. Получение исходного ОР. Метод искусственного базиса.
4.3. Об альтернативных оптимальных решениях ЗЛП.
4.4. Об анализе на чувствительность.
4.5. Задачи.
ГЛАВА 5
ОСНОВЫ ТЕОРИИ ДВОЙСТВЕННОСТИ.
5.1. Определение пары двойственных задач.
5.2. Несколько замечаний об умножении матриц.
5.3. Несколько замечаний о свойствах скалярного произведения векторов.
5.4. Теоремы двойственности.
5.5. Двойственный симплекс-метод.
5.6. Двойственность и анализ на чувствительность.
Изменение коэффициентов целевой функции.
Включение в исходную модель дополнительных переменных.
Включение дополнительных ограничений.
5.7. Задачи.
ГЛАВА 6
МЕТОД ПОТЕНЦИАЛОВ РЕШЕНИЯ
ТРАНСПОРТНОЙ ЗАДАЧИ.
6.1. Математическая модель транспортной задачи.
6.2. Методы получения исходного допустимого решения ТЗ.
6.3. Задача, двойственная к ТЗ. Соотношения двойственности и описание метода потенциалов.
6.4. Циклы в матрице.
6.5. Описание метода потенциалов.
6.6. Еще один пример (блокирование перевозок).
6.7. Задачи.
ГЛАВА 7
ПАРОСОЧЕТАНИЯ.
7.1. Определения и примеры.
7.2. Основная теорема о наибольших паросочетаниях.
7.3. Наибольшее паросочетание в двудольном графе.
7.4. Алгоритм отыскания увеличивающей цепи для паросочетания в двудольном графе.
7.5. Задача об оптимальных назначениях.
ГЛАВА 8
ТРАНСПОРТНАЯ ЗАДАЧА И ВЕНГЕРСКИЙ
АЛГОРИТМ ЕЕ РЕШЕНИЯ.
8.1. Потоки в сетях.
8.2. Разрезы.
8.3. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе.
8.4. Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке (метод расстановки пометок).
8.5. Алгоритм Форда-Фалкерсона для транспортной сети, имеющей вид двудольного графа.
8.6. Венгерский алгоритм решения транспортной задачи.
8.7. Задачи.
ЛИТЕРАТУРА.

Купить .





Теги: Палий :: программирование :: 2008