Программная реализация на языке Delphi

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

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

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

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

Алгоритм  решения задач  симплекс - методом

1) Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения).

2) Полученное  математическое описание приводят  к канонической форме.

3) Каноническую  форму приводят к матричному  виду.

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

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

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

Признаком оптимальности  решения является наличие в векторе  решений только отрицательных или  нулевых коэффициентов при всех ограничениях.

Ответ записывается следующим образом:

- Каждому отрицательному  коэффициенту в векторе решения  ставится в соответствие нулевой  коэффициент для соответствующей  переменной в ответе.

- Для каждого  нулевого коэффициента в векторе  решения ставится в соответствие  значение свободного члена из  строки, содержащей единицу в  столбце данной переменной.

- Фиктивные переменные  в ответе не учитываются.

Ведущим может  быть назначен любой столбец, удовлетворяющий  одному из условий:

1) Первый столбец,  содержащий положительный элемент  в векторе решений.

2) Столбец, содержащий  наибольший положительный элемент  в строке решения.

3) Если столбец  удовлетворяет условию max(C_j min b_j/a_ij) при решении на max, и min(C_j min b_j/a_ij) при решении задач на min.

C_j - коэффициент целевой функции в столбце j, a_ij - коэффициент в столбце j и строке i.

Решение задачи

Определим максимальное значение целевой функции  F(X) = 3500 x₁ +3200 x₂ +1500 x₃ при следующих условиях ограничений.

4 x₁ + 2 x₂ + 5 x₃ <=190

5 x₁ + 3 x₂ + 4 x₃ <=320

7 x₁ + 9 x₂ + 5 x₃ <=454

Для построения первого опорного плана систему  неравенств приведем к системе уравнений путем введения дополнительных переменных.

4x₁ + 2x₂ + 5x₃ + 1x₄ + 0x₅ + 0x₆ = 190

5x₁ + 3x₂ + 4x₃ + 0x₄ + 1x₅ + 0x₆ = 320

7x₁ + 9x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 454

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений  и притом с единичным коэффициентом.

Решим систему  уравнений относительно базисных переменных:

x₄ , x₅ , x₆

Полагая, что  свободные переменные равны 0, получим  первый опорный план: X1 = (0,0,0,190,320,454)

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

Переходим к  основному алгоритму симплекс-метода.

Итерация  №0

Текущий опорный  план неоптимален, так как в индексной строке находятся отрицательные коэффициенты

В качестве ведущего выберем столбец, соответствующий  переменной x₁, так как наибольший коэффициент по модулю.

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

и из них выберем  наименьшее:

Следовательно, 1-ая строка является ведущей

Разрешающий элемент  равен 4 и находится на пересечении  ведущего столбца и ведущей строки

Формируем следующую  часть симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x₁

Строка, соответствующая  переменной x₁ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=4

На месте разрешающего элемента в плане 1 получаем 1.

В остальных  клетках столбца x₁ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁ .

Все остальные  элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые  расположены в вершинах прямоугольника и всегда включают разрешающий элемент  РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент  старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

Итерация  №1

Текущий опорный  план неоптимален, так как в индексной строке находятся отрицательные коэффициенты

В качестве ведущего выберем столбец, соответствующий  переменной x₂, так как наибольший коэффициент по модулю.

Вычислим значения D _i по строкам как частное от деления и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей

Разрешающий элемент  равен 5.5 и находится на пересечении  ведущего столбца и ведущей строки

Формируем следующую  часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x₂

Строка, соответствующая  переменной x₂ в плане 2, получена в результате деления всех элементов строки x₆ плана 1 на разрешающий элемент РЭ=5.5

На месте разрешающего элемента в плане 2 получаем 1.

В остальных  клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂ .

Все остальные  элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.