«Модифицированный симплекс-метод»
Цель работы
Изучить алгоритм модифицированного симплекс-метода. Выявить его преимущества перед другими методами, в частности перед обычным симплекс-методом.
Порядок выполнения работы
1. Решить задачу линейного программирования, используя итерации модифицированного симплекс-метода.
2. Вычислить коэффициенты z-строки и определить включаемую в базис переменную 
.
3. Определить исключаемую переменную
4. Определить новый базис и перейти к шагу 2.
Практическое занятие №7.
«Целочисленное линейное программирование (ЗЦЛП)»
Цель работы
Найти оптимальное целочисленное решение.
Порядок выполнения работы
1. Исходными данными взять результаты, посчитанные симплекс-методом.
2. Найти решение ЗЦЛП:
2.1 методом Гомори;
2.2 методом ветвей и границ.
Краткая теория
Метод Гомори.
1. Построить исходную таблицу.
2. Проверить базисные переменные на целостность.
3. Ввести дополнительное ограничение для строки, содержащей в строке базисных переменных наибольшую дробную часть.
4. Перейти к новому базису, используя итерации двойственного симплекс-метода.
5. Вернуться к пункту 2.
Метод ветвей и границ.
1. Решить задачу, отбросив условие целочисленности, любым методом ЛП.
2. Проверить решение на целостность.
3. Добавляем новые ограничения, полученные округлением нецелочисленного оптимального значения в большую или меньшую сторону.
4. Решить каждую из полученных ЗЛП обычным симплекс-методом.
5. Проверяем каждое решение на целостность.
6. Если условие целостности не выполняется, возвращаемся к пункту 3.
7. Сравниваем оптимальные решения и выбираем.
Практическое занятие №8.
«Транспортная задача»
Цель работы
Решить заданную транспортную задачу.
Порядок выполнения работы
1. Из приложения 2 выбрать свой вариант.
2. Решить транспортную задачу:
2.1 методом северо-западного угла
2.2 методом минимального элемента
2.3 методом Фогеля
2.4 методом потенциалов
Краткая теория
Метод северо-западного угла.
На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из Ai или полностью удовлетворяется потребность Bj.
Метод минимального элемента.
1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают меньшее из чисел.
2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.
Метод Фогеля.
1. В каждой строке найти разность между двумя наименьшими стоимостями и записать ее около соответствующей строки справа;
2. В каждом столбце найти разность между двумя наименьшими стоимостями и записать ее под соответствующим столбцом;
3. Среди всех полученных разностей найти максимальную и распределить объем перевозки в клетку строки или столбца с наименьшей стоимостью;
4. Исключить из рассмотрения строку или столбец с распределенными поставками и вернуться к пункту 1.
5. Когда план построен, рассчитать транспортные расходы.
Метод потенциалов.
1) Каждой строке, столбцу ставится в соответствие некоторое число ui, vj.
2) Для каждой базисной переменной находят значения потенциалов (
). Для каждой небазисной переменной - косвенные тарифы (
).
3) Проверить полученный план на оптимальность (
)
4) Если план не оптимальный перейти к новому базисному плану путем перемещения перевозки в клетку, отвечающей условию 
.
5) Переменная, стоящая в выбранной клетке, вводится в базис. Строится замкнутый путь, соединяющий выбранную незаполненную клетку с ней же самой и проходящий через заполненные клетки.
6) В каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «-». В клетках со знаком «-» выбирается минимальная величина.
Строим новый базисный план путем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком «+», и вычитания этой величины из величин, стоящих в клетках со знаком «-».
7) Осуществляется переход к шагу 1.