WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
И.А. Палий Учебное пособие СОДЕРЖАНИЕ ВВОДНЫЕ ЗАМЕЧАНИЯ.......................................... Ошибка! Закладка не определена.

ЧТО ТАКОЕ ЗАДАЧА ЛИНЕЙНОГО....................... Ошибка! Закладка не определена.

ПРОГРАММИРОВАНИЯ........................................... Ошибка! Закладка не определена.

1.1. Математическая модель задачи....................... Ошибка! Закладка не определена.

линейного программирования................................ Ошибка! Закладка не определена.

1.2 Примеры построений математических моделей....................Ошибка! Закладка не определена.

задач линейного программирования...................... Ошибка! Закладка не определена.

1.3. Задачи............................................................ Ошибка! Закладка не определена.

2. ЗДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Ошибка! Закладка не определена.

С ДВУМЯ ПЕРЕМЕННЫМИ..................................... Ошибка! Закладка не определена.

2.1. Графическое решение ЗЛП с двумя переменными...............Ошибка! Закладка не определена.

2.2 Понятие об анализе на чувствительность........ Ошибка! Закладка не определена.

2.3. Задачи................................................................. Ошибка! Закладка не определена.

КАНОНИЧЕСКАЯ ФОРМА ЗАДАЧИ...................... Ошибка! Закладка не определена.

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.................. Ошибка! Закладка не определена.

3.1. Определение канонической формы ЗЛП........ Ошибка! Закладка не определена.

3.2. Приведение произвольной ЗЛП....................... Ошибка! Закладка не определена.

к каноническому виду.............................................. Ошибка! Закладка не определена.

3.3 Задачи.................................................................. Ошибка! Закладка не определена.

4. ОПОРНЫЕ РЕШЕНИЯ (ОР)................................... Ошибка! Закладка не определена.

4.1. Решение системы линейных уравнений по.... Ошибка! Закладка не определена.

методу Гаусса (методу исключения неизвестных)Ошибка! Закладка не определена.

4.2. Опорные решения............................................. Ошибка! Закладка не определена.

4.3. Переход от одного опорного решения............ Ошибка! Закладка не определена.

к другому................................................................... Ошибка! Закладка не определена.

Вырожденные и невырожденные........................... Ошибка! Закладка не определена.

опорные решения..................................................... Ошибка! Закладка не определена.

4.5. Выражение целевой функции Z через............. Ошибка! Закладка не определена.

свободные переменные............................................ Ошибка! Закладка не определена.

Оценки свободных переменных............................. Ошибка! Закладка не определена.

4.6. Анализ значений целевой функции Z,............ Ошибка! Закладка не определена.

выраженной через свободные переменные........... Ошибка! Закладка не определена.

Признак неограниченности целевой функции...... Ошибка! Закладка не определена.

в допустимой области.............................................. Ошибка! Закладка не определена.

4.7. Анализ значений целевой функции Z,............ Ошибка! Закладка не определена.

выраженной через свободные переменные........... Ошибка! Закладка не определена.

Признак оптимальности опорного решения.......... Ошибка! Закладка не определена.

4.8 Теорема о достижимости оптимального.......... Ошибка! Закладка не определена.

значения целевой функции ЗЛП на опорном решении...............Ошибка! Закладка не определена.

4.9. Задачи................................................................. Ошибка! Закладка не определена.

5. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗЛП................. Ошибка! Закладка не определена.

5.1 Описание симплекс-метода............................... Ошибка! Закладка не определена.

5.2 Получение исходного ОР.................................. Ошибка! Закладка не определена.

Метод искусственного базиса................................. Ошибка! Закладка не определена.

5.3. Об альтернативных оптимальных решениях ЗЛП................Ошибка! Закладка не определена.

5.4. Об анализе на чувствительность...................... Ошибка! Закладка не определена.

5.5. Задачи................................................................. Ошибка! Закладка не определена.

6. Основы теории двойственности............................. Ошибка! Закладка не определена.

6.1. Определение пары двойственных задач......... Ошибка! Закладка не определена.

6.2. Несколько замечаний об умножении матриц. Ошибка! Закладка не определена.

Несколько замечаний о свойствах.......................... Ошибка! Закладка не определена.

Скалярного произведения векторов....................... Ошибка! Закладка не определена.

6.4. Теоремы двойственности................................. Ошибка! Закладка не определена.

6.5. Двойственный симплекс-метод....................... Ошибка! Закладка не определена.

6.6. Двойственность и анализ на чувствительность.....................Ошибка! Закладка не определена.

7.7. Задачи................................................................. Ошибка! Закладка не определена.

7. МЕТОД ПОТЕНЦИАЛОВ РЕШЕНИЯ.................. Ошибка! Закладка не определена.

ТРАНСПОРТНОЙ ЗАДАЧИ (ТЗ)............................... Ошибка! Закладка не определена.



7.1. Математическая модель транспортной задачи......................Ошибка! Закладка не определена.

7.2. Методы получения исходного......................... Ошибка! Закладка не определена.

допустимого решения ТЗ......................................... Ошибка! Закладка не определена.

7.3. Задача, двойственная к ТЗ................................ Ошибка! Закладка не определена.

Соотношения двойственности и............................. Ошибка! Закладка не определена.

описание метода потенциалов................................ Ошибка! Закладка не определена.

7.4. Циклы в матрице............................................... Ошибка! Закладка не определена.

7.5. Описание метода потенциалов........................ Ошибка! Закладка не определена.

7.6. Еще один пример (блокирование перевозок). Ошибка! Закладка не определена.

7.7 Задачи.................................................................. Ошибка! Закладка не определена.

8.ПАРОСОЧЕТАНИЯ.................................................. Ошибка! Закладка не определена.

8.1 Определения и примеры.................................... Ошибка! Закладка не определена.

8.2 Основная теорема о наибольших паросочетаниях.................Ошибка! Закладка не определена.

8.3. Наибольшее паросочетание в двудольном графе.................Ошибка! Закладка не определена.

8.4. Алгоритм отыскания увеличивающей............ Ошибка! Закладка не определена.

цепи для паросочетания в двудольном графе........ Ошибка! Закладка не определена.

8.5. Задача об оптимальных назначениях (ЗН)...... Ошибка! Закладка не определена.

9. ТРАНСПОРТНАЯ ЗAДAЧA И ВEНГEРСКИЙ AЛГОРИТМ EЁ РEШEНИЯ.Ошибка! Закладка не определена.

9.1. Потоки в сетях................................................... Ошибка! Закладка не определена.

9.2. Разрезы............................................................. Ошибка! Закладка не определена.

9.3. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе.................................................................................... Ошибка! Закладка не определена.

9.5. Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке (метод расстановки пометок).............................................. Ошибка! Закладка не определена.

9.5. Алгоритм Форда–Фалкерсона для транспортной сети, имеющей вид двудольного графа.......................................................................... Ошибка! Закладка не определена.

9.6. Венгерский алгоритм решения транспортной задачи..........Ошибка! Закладка не определена.

9.7. Задачи................................................................. Ошибка! Закладка не определена.

ВВОДНЫЕ ЗАМЕЧАНИЯ Этот учебное пособие составлено на основании многолетнего опыта чтения курсов «Математическое программирование» и «Экономикоматематические методы и модели» студентам экономических специальностей СибАДИ. В нестоящее время линейное программирование в СибАДИ излагается в следующих курсах: «Экономико-математические методы и модели» (для студентов экономических специальностей);

«Математическая экономика» (для студентов специальности 351400 - «Прикладная информатика в экономике»); «Теория принятия решений» (для студентов специальностей 220200 - «Автоматизированные системы обработки информации и управления»; и 075500 - «Комплексное обеспечение информационной безопасности автоматизированных систем»). Кроме того, материал, изложенный в этом пособии, используется в курсе «Дискретная математика», читаемом студентам специальности 075500 - «Комплексное обеспечение информационной безопасности автоматизированных систем».

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

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

Использованная литература 1. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

2. Бонди Б. Основы линейного программирования. - М.: Радио и связь, 1989.

3. Данциг Дж. Линейное программирование, его обобщение и приложения. - М. Прогресс, 1966.

4. Калихман И.Л. Сборник задач по математическому программированию. - М.: Высшая школа, 1975.

5. Карпелевич Ф.М., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. - М.: Наука, 1967.

6. Линейное и нелинейное программирование /Под ред. И.М.

Ляшенко - Киев: Вища школа, 1976.

7. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация.

Алгоритмы и сложность. - М.: Мир, 1985.

8. Таха Х. Введение в исследование операций: в 2-х книгах. Кн.1. - М.: Мир, 1985.

ЧТО ТАКОЕ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1.1. Математическая модель задачи линейного программирования Задача линейного программирования (ЗЛП) ставится следующим образом. Требуется отыскать условный экстремум (максимум или минимум) линейной целевой функции n переменных.

Z = c1x1 + c2x2 + L + cnxn max (min). (1.1) При этом на переменные x1, x2,L, xn наложены линейные ограничения a11x1 + a12x2 + L + a1nxn ( ; =; ) b1;





a x1 + a22x2 + L + a2nxn ( ; =; ) b2;

(1.2) LLLLLLLLLLLLLLLL am1x1 + am2x2 + L + amnxn ( ; =; ) bm.

Здесь коэффициенты c1, c2,L, cn; a11, a12,L, amn; b1, b2,L, bm - заданные числа, а величины x1, x2,L, xn - неизвестные. Каждое из ограничений системы - одно из трех возможных:, =,.

Совокупность целевой функции (1.1) и системы ограничений (1.2) называется математической моделью задачи линейного программирования.

Любой набор чисел x1, x2,L, xn, удовлетворяющий системе ограничений (1.2) называется допустимым решением данной ЗЛП.

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

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

1.2 Примеры построений математических моделей задач линейного программирования Пример 1. (Задача распределения ресурсов).

Предприятие изготовляет n типов продукции, для производства которой требуется m видов сырья. Для изготовления единицы j-го типа продукции требуется aij единиц сырья i-го вида, i =1,L, m; j =1,L, n (некоторые из чисел aij могут равняться нулю). Запасы сырья ограничены и составляют bi единиц для i-го вида сырья, i =1,L, m. Прибыль от реализации одной единицы продукции j-го типа равна с единиц, j j =1,L, n. Сколько единиц продукции каждого вида нужно произвести, чтобы получить максимальную прибыль и уложиться в имеющиеся запасы ресурсов Описывая математическую модель задачи линейного программирования, будем последовательно определять неизвестные задачи, целевую функцию и систему ограничений.

Описание неизвестных. Неизвестно, сколько единиц продукции каждого типа нужно произвести. Обозначим эти величины через x1, x2,L, xn. Всего в задаче n неизвестных, x - количество единиц j продукции j-го типа, j =1,L, n.

Описание целевой функции. Требуется максимизировать прибыль от реализации продукции. Если единица продукции первого типа приносит сединиц прибыли, то прибыль от реализации x1 единиц этой продукции составит c1x1 единиц прибыли. Соответственно x2 единиц продукции второго типа дадут c2x2 единиц прибыли. Тогда прибыль от реализации всей продукции равна n Z = c1x1 + c2x2 + L + cn xn = x max.

c j j j =Описание системы ограничений. Запасы сырья ограничены.

Подсчитаем, сколько сырья первого вида уйдет на производство всей продукции. Если на производство единицы продукции первого типа требуется a11 единиц сырья первого вида, то на производство x1 единиц этой продукции будет затрачено a11 x1 единиц сырья первого вида. Для выпуска x2 единиц продукции второго типа потребуется a12x2 единиц сырья первого вида. Чтобы произвести xn единиц продукции n -го типа, нужно затратить a1nxn единиц сырья первого вида. Всего же потребуется n a11x1 + a12x2 + L + a1nxn = a x единиц сырья первого вида. Расход 1 j j j =этого вида сырья не может превысить имеющегося запаса, должно выполняться неравенство a11x1 + a12x2 + L + a1nxn b1.

Подобным образом составляются ограничения по запасам сырья остальных видов. Система ограничений такова a11x1 + a12x2 + L + a1nxn b1;

LLLLLLLLLLLL a x1 + ai2x2 + L + ain xn bi;

iLLLLLLLLLLLL x1 + am2x2 + L + amnxn bm.

amВсего в системе m ограничений по запасам. Кроме того, необходимо добавить еще условие неотрицательности переменных; нельзя выпускать отрицательное число единиц продукции: x1 0; x2 0;L; xn 0.

Пример 2. (Задача о раскрое).

Для изготовления брусьев трех длин (0,2; 0,3; и 0,5 м) на распил поступили бревна длиной 1м. Нужно получить не менее 150 и не более брусьев длиной 0,1 м; не менее 200 и не более 300 брусьев длиной 0,3 м; не менее 300 и не более 330 брусьев длиной 0,5 м. Как распиливать бревна, чтобы обеспечить нужное число брусьев каждого размера и при этом минимизировать отходы Прежде всего, опишем все способы распила одного бревна. Например, бревно длиной 1 м можно распилить на 5 брусьев длиной 0,2 м, отходов в этом случае нет. Или можно получить 3 бруса длиной 0,3 м, тогда в отходы уйдет 0,1 м бревна. Варианты распила приведены в табл. 1.1.

Таблица 1. Количество брусьев длиной, м Величина Способ отходов, м 0,2 0,3 0,1 5 0 0 2 3 1 0 0,3 2 2 0 4 2 0 1 0,5 1 1 1 6 0 3 0 0,7 0 0 2 Опишем математическую модель задачи.

Описание неизвестных. Неизвестно, сколько бревен следует распиливать каждым из способов, указанных в табл. 1.1. Обозначим через x, ( j =1, 2,L, 7 ) количество бревен, распиленных j-м способом. Всего j неизвестных, каждое из них может принимать только целые значения: 0, 1, 2, 3,….

Описание целевой функции. Требуется минимизировать суммарные отходы. Отходы остаются только в случае применения 2, 4, 6-го способов.

Если распил одного бревна дает единицу отходов (0,1 м), то распил x j бревен дает x единиц отходов. Суммарное величина отходов равна j Z = x2 + x4 + x6 min.

Описание системы ограничений. Всего брусьев длиной 0,2 м будет получено 5x1 + 3x2 + 2x3 + 2x4 + x5 штук (6-й и 7-й способы распила не дают брусьев длиной 0,2 м). По условию число брусьев длиной 0,2 м должно лежать в пределах от 150 до 200, получаем два ограничения 5x1 + 3x2 + 2x3 + 2x4 + x5 150;

5x1 + 3x2 + 2x3 + 2x4 + x5 200.

Аналогично строятся ограничения по числу брусьев длиной 0,3 м и длиной 0,5 м.

x2 + 2x3 + x5 + 3x6 x2 + 2x3 + x5 + 3x6 x4 + x5 + 2x7 x4 + x5 + 2x7 330.

Добавим также условие неотрицательности и целочисленности переменных: x 0, x N, j =1, 2,L, 7.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.