Алгоритм модифицированного симплекс-метода

-исходный обращенный базис,

-вектор номеров базисных столбцов.

Шаг 1.

Определяем вектор и вычисляем вектор

Шаг 2.

Вычисляем симплекс-разности

и находим

k – номер столбца, вводимого в базис

Шаг 3.

Если то вычисляем

- оптимальный план и оптимальное значение функции;

Шаг 4.

Вычисляем

Шаг 5.

Если

то ЗЛП не имеет конечного решения;

Шаг 6.

Вычисляем

Находим

- направляющий элемент;

Шаг 7.

В ычисляем

полагаем

,

Шаг 8.

Полагаем

и переходим к шагу 1

Решение задачи модифицированным симплекс-методом

(1)

Выразим из третьего уравнения

и подставим эти ограничения в целевую функцию и остальные ограничения:

(2)

Приведем ЗЛП к каноническому виду

(3)

Выпишем расширенную матрицу системы ограничений ЗЛП (3):

Она является К-матрицей.

Вектор ,

Нулевая итерация: S=0.

Шаг 1.

Определяем

Вычисляем

Шаг 2.

Вычисляем симплекс - разности

, j=1,2

,

Находим

пусть k=1

Шаг 3.

Так как то переходим к шагу 4.

Шаг 4.

Вычисляем

Шаг 5.

Так как , то переходим к шагу 6.

Шаг 6.

В ычисляем и находим

_, направляющий элемент;

Шаг 7.

Вычисляем

полагаем

Шаг 8.

и переходим к шагу 1 первой итерации.

 S=1. Первая итерация

Шаг 1.

Шаг 2.

Шаг 3.

Так как , то переходим к шагу 4.

Шаг 4.

Шаг 5.

Так как то переходим к шагу 6.

Шаг 6.

- направляющий элемент;

Шаг 7.

Шаг 8.

S = 1 + 1 = 2 и переходим к шагу 1.

S = 2.

Вторая итерация.

Шаг 1.

Шаг 2.

Шаг 3.

Так как и , то вычисляем

= (1/12; 4/12; 7/12) - оптимальный опорный план.

Итак, решение задачи

или

2.9. Решение злп на основе Ms Excel

Решим задачу, математическая модель которой имеет вид:

max f ( )=7,5X₁+3X₂+6X₃+12X₄ (целевая функция)

при

2X₁+X₂+0,5Х₃+4Х₄ ≤ 2400

ограничения

X₁+5X₂+3Х₃ ≤ 1200

3X₁+6X₃+Х₄ ≤ 2000

X_1,2,3,4 ≥0

Таблица 2.10

				7,5	3	6	12	0	0	0
S	i
0	1	5	0	2	1	0,5	4	1	0	0	2400	600
	2	6	0	1	5	3	0	0	1	0	1200	-
	3	7	0	3	0	6	1	0	0	1	2000	2000
	4		∆	-7,5	-3	-6	-12	0	0	0
1	1	4	12	0,5	0,25	0,125	1	0,25	0	0	600	4800
	2	6	0	1	5	3	0	0	1	0	1200	400
	3	7	0	2,5	-0,25	5,875	0	-0,25	0	1	1400	238,3
	4			-1,5	0	-4,5	0	3	0	0
2	1	4	12	0,4468	0,2553	0	1	0,2553	0	-0,021	570,213	2233,3
	2	6	0	-0,2766	5,1277	0	0	0,1277	1	-0,511	485,106	94,606
	3	3	6	0,4255	-0,0426	1	0	-0,043	0	0,1702	238,298	-
	4			0,4149	-0,1915	0	0	2,8085	0	0,766
3	1	4	12	0,4606	0	0	1	0,249	-0,0498	0,0041	546,058
	2	2	3	-0,0539	1	0	0	0,0249	0,19502	-0,1	94,6058
	3	3	6	0,4232	0	1	0	-0,041	0,0083	0,166	242,324
	4			0,4046	0	0	0	2,8133	0,03734	0,7469	8290,46

Решим данную ЗЛП с помощью Ms Excel

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис»:

Если в версии Excel, установленной на вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения».

Рассмотрим на примере использование данной надстройки. Решим с ее помощью задачу, математическая модель которой имеет вид:

max f ( )=7,5X₁+3X₂+6X₃+12X₄ (целевая функция)

при

2X₁+X₂+0,5Х₃+4Х₄ ≤ 2400

X₁+5X₂+3Х₃ ≤ 1200

3X₁+6X₃+Х₄ ≤ 2000

X_1,2,3,4 ≥0

Составим шаблон в редакторе Excel,как показано на шаблоне 1.

Шаблон 1.

Теперь занесем в данную задачу числовую информацию (шаблон 2)

Шаблон 2. Исходные данные задачи

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

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

Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение 7,5X₁+3X₂+6X₃+12X₄, можно рассматривать как произведение вектора (7,5, 3, 6, 12) на вектор (Х₁,Х₂,X₃,X₄).

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку H5 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5:F5) и ячеек, в которые в результате решения будут помещены значения Х₁, Х₂, X₃, X₄ (ячейки С4:F4) (шаблон 3).

Шаблон 3. Вызов функции СУММПРОИЗВ

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение 2X₁+X₂+0,5Х₃+4Х₄ (для первого ограничения 2X₁+X₂+0,5Х₃+4Х₄≤2400) будем рассматривать как произведение вектора коэффициентов (2, 1, 0,5, 4) и вектора переменных (Х₁,Х₂,X₃,X₄).

В ячейке, отведенной для формулы левой части первого ограничения (G9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов С9:F9 и адрес значений переменных C4:F4 (шаблон 4).

Шаблон 4.

В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введенными формулами показан на шаблон 5.

Шаблон 5.

К моменту вызова сервиса «Поиск решения» на рабочем столе с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.

В меню Сервис выбираем Поиск решения. В появившемся окне задаем следующую информацию:

а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции H5

б) «флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае, целевая функция дохода подлежит максимизации;

в) в качестве изменяемых ячеек заносится адрес строки значений переменных С4:F4;

г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (Шаблон 6).

Шаблон 6.

д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения G9, выбирается требуемый знак неравенства (в нашем случае, <=), в поле «Ограничение» заносится ссылка на правую часть ограничения I9 (Шаблон 7):

Шаблон 7.

е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Таким образом, окно «Поиск решения с занесенной информацией выглядит следующим образом (Шаблон 8):

Шаблон 8.

Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (Шаблон 9).

Шаблон 9. Установка параметров

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата поиска решения (Шаблон 10).

Шаблон 10. Окно результата решения

Если в результате всех действий получено окно с сообщением «Решение найдено», то Вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи (Шаблон 11)

Шаблон 11. Результат применения «Поиска решения»

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

Шаблон 12. Сообщение об ошибке

В окне «Поиск решения» имеется кнопка «Параметры»:

Установим флажок «Показывать результаты итераций», после нажимаем «ОК»:

Затем нажать кнопку «Выполнить»:

Ms Excel выдаст следующее окно:

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

После чего нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты второй итерации:

Затем снова нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты третьей итерации:

При следующим нажатии кнопки «Продолжить», программа выдает окно «Результаты поиска решения», где необходимо сохранить найденное решение и выбрать тип отчета: