1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной — на минимум. 2

Матрица/! (13)

а„ а,г ... аы

составленная из коэффициентов при неизвестных в системе ограничениях (10) исходной задачи (9) — (10) и аналогичная матрица в двойственной задаче (11) — (12) получаются друг из друга транспонированием. 3.

Число переменных в двойственной задаче (11) — (12) равно числу ограничений в системе (10) исходной задачи, а число ограничений в системе (12) двойственной задачи — числу переменных в исходной задаче. 4.

Коэффициентами при неизвестных в целевой функции (11) двойственной задачи являются свободные члены в системе (10) исходной задачи, а правыми частями в ограничениях системы (12) двойственной задачи — коэффициенты при неизвестных в целевой функции (9) »сходной задачи. 5.

Если переменная дгу исходной задачи (9) — (10) может принимать^ только лишь неотрицательные значения, тоу-е ограничение в системе (12) двойственной задачи является неравенством вида > Если же переменная дгу может принимать как положительные, так и отрицательные значения, тоу-е ограничение в системе (12) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (10) исходной задачи и переменными двойственной задачи Если /-с ограничение в системе (10)|1 исходной задачи является неравенством, то <-я переменная двойственной задачи у, > 0. Если же /-с ограничение есть уравнение, то переменная и может принимать как положительные, так и отрицательные значения. 1

Идея последовательного улучшения решения легла в основу универ-" сального метода решения задач линейного программирования — симплекс- метода Геометрический смысл этого метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мерс, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптимальное решение — вершина, I

де достигается оптимальное значение функции цели (если задача имеет конечный оптимум) Идеи метода были опубликованы российским ученым Л В Канторовичем в 1939 г.

Для применения симплекс-метода в ограничения задачи вводятся дополнительные переменные. .^у, и условие исходной задачи принимает вид:

/ = с\х1 + С2Х2 + + СЛ тах

а,,*,+а|2дгг+ ... + а|ллг(,+>>, <6, аг\х\ +а22х2 +-” + а:лдгл +Уг - Ьг

(14)

ат1х1+ат2х2+... + атпх„+ук <Ьт дг, > 0, хг > 0,...,дгл > О,^ >0

Эту постановку можно представить в виде таблицы — первой таблицы симплекс-метода (табл. 7.1).

Таблица 7.1

Первая симплекс-таблица Базис Свободные члены Свободные переменные I *. I I У, ь\ °п «I. >'2 ь2 °2, °22 °2, Ьт “»2 ат„ Индексная

строка 0 -с. -сг -с. Для составления симплекс-таблиц можно применять определенные правила. 1.

Для первой таблицы

а) в первый столбец записывают^ — базисные переменные, которые находятся в уравнениях слева;

б) свободные переменные атп выносят в верхнюю строку таблицы, в) в остальные столбцы записывают коэффициенты перед свобо ь ными переменными. 2

Для последующих таблиц:

а) выбирается наименьший отрицательный элемент в индексной строке при отыскании максимума, но наибольший положительный — при опускании минимума, исключая вектор свободных членов;

б) этот элемент определяет ключевой вектор-столбец и он вводи гея в базис;

в) компоненты вектора свободных членов делятся на положительные элементы ключевого столбца;

г) из полученных отношений выбирается наименьшее;

д) вектор-строка, содержащая наименьшее положительное частное,— ключевая и выводится из базиса;

е) на пересечении ключевых строк и столбца находится разрешающий элемент;

ж) преобразование матрицы: —

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

ключевой столбец в новой таблице — нули, за исключением разрешающего элемента, —

остальные элементы новой таблицы рассчитываются по схеме: ^

Новый элемент = Старый элемент - Элемент ключевой строки х Элемент ключевого столбца Разрешающий элемент —

если нулевая строка (столбец) содержит пуль, то соответствующий столбец (строка) в новой таблице не изменится 3.

Пункты «а» — «ж» повторяются до тех пор, пока в индексной строке не останется ни одного отрицательного элемента при отыскании максимума (но ни одного положительного при отыскании минимума)

Пример 7.1. Требуется принять решение об оптимальном плане производства трикотажа на месяц на ОАО «Сейм» с применением симплекс- метода

Определим оптимальный плаи выпуска моделей мужского трикотажа с целью получения максимальной прибыли при заданных ресурсах с помощью построения математической модели. Исходные данные представлены в табл 7 2. |

В таблице 7 2 приведены запасы ресурсов па март 2002 г и число единиц ресурсов, затрачиваемых на изготовление единицы изделий каждой из моделей. Количество каждого /-го ресурса для производства каж- югоу'-го вида продукции называют нормой расхода (ду) Из таблицы 7.