Алгоритм Симплекс-метода:

1. Преобразовываем неравенства в равенства

2. Находим начальное допустимое базисное решение

3. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, то процесс закончен.

4. На основе условия допустимости выбираем исключаемая переменная

5. Вычисляем элементы новой ведущей строки

новая ведущая строка = текущая строка/ведущий элемент

6. Вычисляем элементы остальных строк, включая z-строку

новая строка = текущая строка – ее коэффициенты в ведущем столбце * новую ведущую строку

Переходим к шагу 3.

Для удобства записи итерационного процесса все значения записываем в Симплекс-таблицу.

2. Пример решения задачи лп с использованием пакета ms excel

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

Для нахождения решения в подобных моделях, можно использовать средство MS EXCEL – ПОИСК РЕШЕНИЯ.

Рассмотрим, как составить модель линейного программирования и найти ее решение на примере.

2.1. Постановка задачи

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

станки	Время обработки деталей (час)		Время работы станка за цикл производства (час)
	А	Б
I	1	2	16
II	1	1	10
III	3	1	24
Прибыль на одну деталь (тыс. р)	4	2

2.2. Построение математической модели

Обозначим через х₁ и х₂ количество единиц деталей видов А и Б, планируемое к выпуску. Тогда время обработки х₁ деталей вида А на первом станке составляет 1* х₁; х₂ деталей вида Б соответственно 2*х₂. Суммарное время работы станка I для изготовления планируемого количества деталей равно х₁ +2*х₂, оно ограничено 16 часами работы этого станка в течение одного цикла производства. Поэтому должно выполняться неравенство:

х₁ +2*х₂<=16;

Аналогично для станков II и III получаем неравенства соответственно:

х₁ + х₂<=10;

3*х₁ + х₂<=24;

Кроме того, по смыслу определения веденных величин х₁ и х₂ , должны выполняться условия: х₁>=0; х₂>=0;

Таким образом, получаем систему неравенств, называемую системой ограничений задачи:

Любое решение (х₁; х₂) системы ограничений называется планом выпуска продукции или допустимым планом задачи.

Прибыль от реализации х₁ единиц деталей вида А равна 4^.х₁, а прибыль от реализации х₂ единиц деталей вида Б равна 2х_2. Суммарная прибыль от реализации продукции, выпущенной согласно плану (х₁; х₂) равна:

F(х₁; х₂)=4х₁+2х₂ (тыс. руб).

Линейная функция F(х₁; х₂) называется целевой функцией задачи.

По условию задачи требуется найти такой план (х₁; х₂) при котором прибыль была бы максимальной.

Таким образом, построена математическая модель задачи как задачи линейного программирования:

F(х₁; х₂)=4х₁+2х₂→max