- •Математические модели задач лп
- •1.1. Постановка задачи лп
- •1.2. Рекомендации к составлению математических моделей
- •1.3. Пример задачи лп --- задача о диете
- •Графическое решение задач лп
- •2.1. Каноническая форма задачи лп
- •2.2 Пример
- •2.3. Общие рекомендации к графическому решению задач лп
- •2.4. Пример
- •3. Численные методы решения задач лп
- •3.1. Симплекс – метод
- •3.2. Алгоритм симплекс-метода для задачи на минимум
- •3.3. Алгоритм симплекс-метода для задачи на максимум
- •На шаге 2::
- •На шаге 4: .
- •3.4. Пример
- •3.5. Метод искусственного базиса
- •3.6. Пример
- •3.7. Двойственный симплекс-метод
- •3.8. Пример
- •4. Двойственность в лп
- •4.1. Постановка задачи
- •4.2. Пример
- •4.3. Теоремы двойственности
- •4.4. Пример
- •4.5. Пример
- •5. Метод Гомори
- •5.1. Постановка задачи цлп
- •5.2. Алгоритм метода Гомори
- •Замечания.
- •5.3. Пример
- •6. Транспортная задача лп
- •6.1. Постановка задачи
- •6.2. Построение опорного плана транспортной задачи
- •6.3. Метод северо-западного угла
- •6.4. Пример
- •6.5. Метод минимальной стоимости
- •6.6. Пример
- •6.7. Метод потенциалов
- •6.8. Вычислительная схема метода потенциалов
- •6.9. Пример
- •7. Задания для самостоятельной работы
- •7.1. Построить математическую модель задачи
- •7.2. Привести задачу лп к канонической форме
- •Список литературы
5.2. Алгоритм метода Гомори
Шаг 1.Симплекс-методом находим оптимальное решение задачи (22) без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В случае алгоритм завершает работу.
Шаг 2.Пусть оптимальная таблица имеет вид:
|
b |
… | ||
L |
… | |||
… | ||||
… |
… |
………….. | ||
/ |
… |
Если элементы – целые, то оптимальное решениеявляется целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.
Шаг 3.Среди дробных компоненттаблицы выбираем элементс максимальной дробной частьюи по строкеiсоставляем дополнительное ограничение:
Здесь - целая часть числа(наибольшее целое число, не превышающее число).
Шаг 4.Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к шагу 2.
Замечания.
Признаком отсутствия целочисленного решения служит появление в таблице хотя бы одной строки с дробнымсвободным членом ицелымиостальными коэффициентами (поскольку соответствующее уравнение неразрешимо в целых числах).
На шаге 4 двойственный симплекс-метод применяется до тех пор, пока не будет получена оптимальная симплексная таблица (возможно потребуется несколько итераций).
Если на шаге 4 в базис вводится переменная дополнительного ограничения , то эта строка вычеркивается из симплексной таблицы (соответствующее ограничение является избыточным).
5.3. Пример
Решить задачу ЦЛП.
Решаем задачу без условия целочисленности симплекс-методом.Оптимальная таблица имеет вид:
|
b | ||
L |
-14/3 |
-4/3 |
-2/3 |
5/3 |
1/3 |
2/3 | |
4/3 |
2/3 |
-2/3 |
Оптимальное решение не является целочисленным. Выберем среди нецелочисленных переменныхпеременнуюс максимальной дробной частью и построим соответствующее отсечение:
Приписывая это ограничение к симплексной таблице и проводя стандартное преобразование двойственным симплекс-методом, получим:
|
b | ||
L |
-14/3 |
-4/3 |
-2/3 |
5/3 |
1/3 |
2/3 | |
4/3 |
2/3 |
-2/3 | |
-2/3 |
-1/3 |
-2/3 |
|
b | ||
L |
-4 |
-1 |
-1 |
1 |
0 |
1 | |
2 |
1 |
-1 | |
1 |
½ |
-3/2 |
Полученная таблица является оптимальной. Соответствующее оптимальное решение является целочисленным. Значение функции на этом решении.
6. Транспортная задача лп
6.1. Постановка задачи
Классическая транспортная задача ЛП формулируется следующим образом. Имеется mпунктов производства (поставщиков) иnпунктов потребления (потребителей) однородного продукта. Заданы величины:
- объем производства (запас)i-го поставщика,;
- объем потребления (спрос)j-го потребителя,;
- стоимость перевозки (транспортные затраты) единицы продукции отi-го поставщика кj-му потребителю.
Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен и при этом общая стоимость всех перевозок была бы минимальна [1,3].
Транспортная задача, в которой суммарные запасы и суммарные потребностисовпадают, называетсязакрытоймоделью; в противном случае –открытой. Открытая модель решается приведением к закрытой.
Математическая закрытая модель транспортной задачи имеет вид:
В случае, когда суммарные запасы превышают суммарные потребности, т.е. , вводится фиктивныйn+1 потребитель, потребности которого .
В случае, когда суммарные потребности превышают суммарные запасы, т.е. , вводится фиктивныйm+1 поставщик, запасы которого.
Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к закрытой модели.