Алгоритмическая схема метода

↑

▷ Содержание

⇐ ПредыдущаяСтр 5 из 7Следующая ⇒

Шаг 1. Найти точку - решение задачи линейного программирования (1)-(3) (без условия целочисленности). Положить к=1.

Шаг 2. Если -целочисленная, то решение найдено, останов. Иначе зафиксировать множества I и J –индексов базисных и небазисных переменных.

Шаг 3. Выбрать номер   такой, что координата - дробная.

Шаг 4. Добавить в симплекс-таблицу новое ограничение: .

Шаг 5. С учетом добавленного ограничения отыскать новое решение . Положить k = k +1. Перейти на шаг 2.

Замечание 2. Использование обычного симплекс-метода при решении данной задачи неудобно, так как добавление нового ограничения каждый раз будет приводить к необходимости вызова метода искусственного базиса. Более предпочтительным в данной ситуации является двойственный симплекс-алгоритм. В таком случае новое ограничение вводится в систему в виде:

,

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

Пример. Решить задачу целочисленного линейного программирования.

Решение. Приведем задачу к каноническому виду (предварительно умножив второе ограничение на 2).

Оформим решение в виде симплекс-таблицы

На 3-й итерации симплекс-метода найдено нецелочисленное решение . Выбираем, например,  - дробную базисную координату и по соответствующей строке таблицы формируем новое ограничение: . Или: . Добавляем это ограничение в таблицу и осуществляем одну итерацию двойственного симплекс-метода. В результате получаем точку . Выбираем дробную координату  и добавляем ограничение  и т.д.

На последней итерации получена точка , которая является целочисленной. Останов.

Ответ: ,

УПРАЖНЕНИЯ

1. Решить ЦЗЛП методом отсечений:

Ответ: =(5,3)              Ответ: =(6,9)                 Ответ: =(2,5)

Приложение

1. Решение задач линейного программирования 2. Решение задач нелинейного программирования

РЕШЕНИЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ СРЕДСТВАМИ EXCEL

В данном параграфе приводятся алгоритмы решения задач линейного и нелинейного программирования средствами EXCEL.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры