Нахождение первого базисного решения

У нас остался открытым вопрос – а как найти первое базисное решение? Вполне может получиться так, что после выражения базисных переменных через свободные мы получим одно из чисел b_j отрицательным. Тогда нулевые значения свободных переменных не будут задавать допустимое решение. Данная проблема решается последовательным применением таких же шагов, что и в описанном выше симплекс методе. Мы сначала выбираем любое из уравнений, где свободный член отрицателен. Далее мы в этом уравнении выбираем свободную переменную, при увеличении которой наша базисная переменная будет увеличиваться от b_j к нулю. (Возможен и вариант недопустимой задачи, когда в уравнении с отрицательным свободным членом при увеличении любой свободной переменной нужная нам базисная переменная только уменьшается). При увеличении нужной переменной мы также отслеживаем, какая из базисных переменных первая обратится в ноль, и производим пересчет таблицы по алгоритму симплекс-метода. Если первой обратится в ноль та базисная переменная, которую мы увеличиваем, то мы получим новое решение, которое уже будет являться базисным. Если нет, то после пересчета процесс будет повторен сначала.

Рассмотрим пример нахождения базисного решения для задачи: найти максимум целевой функции f=x₁+2x₂ при ограничениях

Введем дополнительные неотрицательные переменные, чтобы свести задачу к каноническому виду:

Мы можем видеть, что эта система разрешена относительно переменных х₃, х₄ и х₅. Однако, если положить значение свободных переменных равным нулю, то получится решение (0, 0, -1, 3, 3), которое не является допустимым, т.к. значение х₃ отрицательно.

Применим описанное выше преобразование системы с целью избавиться от отрицательных свободных членов (такой есть только в первом уравнении). Мы можем увеличить значение базисной переменной х₃, увеличивая свободную переменную х₂. При этом переменная х₅ не препятствует росту х₂, а переменная х₄ позволяет х₂ расти до 3, после чего х₄ обратится в 0. Однако, мы замечаем, что нам повезло, и уже при х₂=1 переменная х₃ сама обратится в 0, поэтому уже после одного шага избавления от отрицательных свободных членов мы получим базисное решение со свободными переменными х₁ и х₃. Выразив х₂ из первого уравнения и подставив во второе, получим систему и соответствующее ей базисное решение (0, 1, 0, 2, 3). В дальнейшем можно действовать по алгоритму симплекс-метода и получить решение задачи.

Сформулируем еще одну полезную для практического применения (вторую) теорему двойственности. Для этого введем соответствие между исходными переменными Х и дополнительными переменными У, и, наоборот, между дополнительными переменными Х и исходными переменными У. (дополнительные переменные возникают при сведении общей задачи линейного программирования к канонической). Оказывается, что

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

Содержание лабораторной работы.

1. Ответить на вопросы двух контролирующих программ.

2. Решить предложенный вариант задачи графическим способом

3. Решить предложенный вариант задачи вручную симплекс-методом, используя графическое решение для контроля правильности вычислений.

4. Составить, отладить и протестировать на контрольных примерах программу решения задачи линейного программирования симплекс-методом в среде Excel и на любом из языков программирования. Решить задачу для своего варианта. Учтите, что первое базисное решение может не быть допустимым.

5. Замените ввод данных на чтение из файла и проверьте работу Вашей программы на всех тестах. Файлы данных имеют следующую структуру: в первой строке записано через пробел количество уравнений K и количество неизвестных N. Во второй строке через пробел указываются К номеров базисных переменных. В последующих K строках через пробел записаны по N+1 числу – сначала свободный член соответствующего уравнения, а затем коэффициенты этого уравнения. В последней строке в том же порядке указаны коэффициенты представления целевой функции через переменные.

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

7. Составить отчет, содержащий цель и назначение работы, постановку задачи и текст программы.

Варианты заданий.

Вариант 1

Ответ: X = 120 Y = 40 F = 280

Вариант 2

Ответ: X = 110 Y = 40 F = 560

Вариант 3

Ответ: X = 80 Y = 50 F = 750

Вариант 4

Ответ: X = 90 Y = 80 F = 170

Вариант 5

Ответ: X = 70 Y = 50 F = 500

Вариант 6

Ответ: X = 70 Y = 60 F = 200

Вариант 7

Ответ: X = 110 Y = 60 F = 280

Вариант 8

Ответ: X = 90 Y = 70 F = 910

Вариант 9

Ответ: X = 100 Y = 50 F = 250

Вариант 10

Ответ: X = 50 Y = 80 F = 1120

Вариант 11

Ответ: X = 110 Y = 40 F = 260

Вариант 12

Ответ: X = 110 Y = 50 F = 750

Вариант 13

Ответ: X = 90 Y = 80 F = 920

Вариант 14

Ответ: X = 100 Y = 30 F = 360

Вариант 15

Ответ: X = 100 Y = 60 F = 260

Вариант 16

Ответ: X = 100 Y = 50 F = 650

Вариант 17

Ответ: X = 80 Y = 50 F = 550

Вариант 18

Ответ: X = 120 Y = 60 F = 300