Табличный алгоритм обмена переменных
Содержание
ВВЕДЕНИЕ.............................................................................................. 2
ЛАБОРАТОРНАЯ РАБОТА № 1.......................................................... 3
ЛАБОРАТОРНАЯ РАБОТА № 2........................................................ 18
ВВЕДЕНИЕ
Данные методические указания являются описанием лабораторных работ по курсу «Исследование операций». Они имеют цель дать обучающимся возможность самостоятельной разработки и реализации наиболее популярных алгоритмов курса
При выполнении лабораторных работ используется язык программирования Турбо Паскаль либо другой по согласованию с преподавателем.
Методические указания предназначены для студентов факультета автоматизации и вычислительной техники, и могут быть использованы студентами других специальностей для выполнения лабораторных работ по курсу «Исследование операций» а также «Основы алгоритмизации и программирования».
ЛАБОРАТОРНАЯ РАБОТА № 1
Решение задач линейного программирования Симплекс-методом
Теоретические положения
Симплекс-метод применяется для решения основной задачи линейного программирования (ОЗЛП), которая ставится следующим образом.
Для ряда переменных 
требуется найти такие неотрицательные значения этих переменных, которые удовлетворяли бы системе линейных уравнений:
и, кроме того, обращали бы в максимум называемую целевой (ЦФ) линейную функцию
Очевидно, случай поиска минимума ЦФ сводится к предыдущему, если изменить знак функции и рассмотреть вместо неё функцию
Условимся называть допустимым решением ОЗЛП любую совокупность переменных
удовлетворяющую уравнениям (1.1).
Оптимальным решением будем называть то из допустимых решений, при котором ЦФ (1.2) обращается в максимум.
Будем считать, что все уравнения нашей системы линейно независимы (т.е. никакое из них нельзя представить в виде линейной комбинации других). Тогда, если число уравнений ОЗЛП 
меньше числа переменных 
, то система линейных уравнений имеет бесчисленное множество решений. При этом 
переменным мы можем придавать произвольные значения (так называемые свободные переменные), а остальные переменных выразятся через них (эти переменных мы будем называть базисными).
На практике ограничения в задаче линейного программирования часто задаются не уравнениями, а неравенствами.
Пусть имеется задача линейного программирования с переменными, с ограничениями, заданными в виде неравенств. Т.к. ограничения со знаком неравенства " 
" сводятся к ограничениям со знаком " 
" простой переменой знака обеих частей, зададим все ограничения неравенства в стандартной форме:
Введём обозначения:
где 
— некоторые новые переменные, которые мы будем называть "добавочными". Согласно условиям , эти добавочные переменные, так же, как и основные, должны быть неотрицательными.
Таким образом, перед нами в чистом виде основная задача линейного программирования (ОЗЛП): найти такие неотрицательные значения 
переменных ; чтобы они удовлетворяли системе уравнений и одновременно обращали в максимум линейную функцию этих переменных:
Уравнения заданы в форме, уже разрешённой относительно базисных переменных , которые выражены через свободные переменные . Общее количество переменных равно .
Таким образом, задача линейного программирования с ограничениями-неравенствами сведена нами к ОЗЛП, но с большим числом переменных, чем было первоначально.
Преобразуем теперь систему уравнений , представив их правые части как разности между свободными членами и суммой остальных:
где 
; 
; … ; 
.
Форму записи уравнений будем называть стандартной. Приведём также к стандартной форме и целевую функцию:
где ; 
; … ; 
.
Очевидно, вместо того, чтобы полностью записывать уравнения , (1.6), можно ограничиться заполнением стандартной таблицы, где указаны только свободные члены и коэффициенты при переменных:
Таблица 1.1.
| Свободный член |  |  | … |  | |
 |  |  |  | … |  |
 |  |  |  | … |  |
 |  |  |  | … |  |
| … | … | … | … | … | … |
 |  |  |  | … |  |
Для дальнейшего удобства переобозначим коэффициенты:
Таблица 1.2
| Свободный член | | | … | | |
| |  |  |  | … |  |
| |  |  |  | … |  |
| |  |  |  | … |  |
| … | … | … | … | … | … |
| |  |  |  | … |  |
Нахождение решения каждой задачи линейного программирования распадается на два этапа:
1) отыскание опорного решения;
2) отыскание оптимального решения, максимизирующего линейную целевую функцию.
Оба этапа используют табличный алгоритм обмена переменных.
Табличный алгоритм обмена переменных
Пусть требуется произвести замену 
, т.е. перевести переменную 
в число базисных, а переменную 
в число свободных. Будем называть столбец с заголовком разрешающим столбцом, а строку с заголовком — разрешающей строкой. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца ( 
), будем называть разрешающим элементом.
Для замены переменных следует выполнить следующие действия:
1. Меняются местами заголовки разрешающей строки и разрешающего столбца 
.
2. Разрешающий элемент заменяется на обратную ему величину 
.
3. Все элементы разрешающего столбца (кроме самого разрешающего элемента) меняют знак и умножаются на новый разрешающий элемент:
.
4. Каждый из элементов, кроме принадлежащих разрешающей строке или разрешающему столбцу, подвергаются следующему преобразованию: к нему прибавляется произведение элемента, стоящего в разрешающей строке (пока это старое значение) на том же месте по порядку (т.е. в том же столбце), на элемент стоящий в новом разрешающем столбце на соответствующем месте (т.е. в той же строке, что и наш элемент):
5. Все элементы разрешающей строки (кроме разрешающего) умножаются на новый разрешающий элемент:
