Программный комплекс для решения задач линейного программирования симплексным методом

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ТЕМА: «ПК для решения задач линейного программирования симплексным методом»

ВВЕДЕНИЕ

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.

Назначение метода состоит в следующем. В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.

Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число «шагов» мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).

Основная цель курсового проекта по дисциплине «Математические методы исследования операций» — получение навыков разработки интеллектуального программного продукта для решения задачи оптимизации (поддержки решения) в заданной предметной области.

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

1 АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ «ПК ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ»

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

— рационального использования сырья и материалов; задачи оптимального раскроя;

— оптимизации производственной программы предприятий;

— оптимального размещения и концентрации производства;

— составления оптимального плана перевозок, работы транспорта;

— управления производственными запасами;

— и многие другие, принадлежащие сфере оптимального планирования.

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

Первым исследованием по линейному программированию является работа Л. В. Канторовича «Математические методы организации и планирования производства», опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающих множителей решения задач линейного программирования и дано его теоретическое обоснование.

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

Математическое программирование — это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.

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

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

1.1 Постановка задачи линейного программирования

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

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

Перед решением задачи линейного программирования симплексным методом ее нужно записать в канонической форме:

; (1)

; (2)

. (3)

Симплекс-метод включает в себя:

— определение одной из вершин многогранника (исходного опорного плана);

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

1.2 Алгоритм решения задачи линейного программирования симплексным методом

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

Определение 1. Допустимым решением (планом) задачи ЛП называется вектор X=(x1,x2,…, xn), удовлетворяющий всем ее ограничениям (2), (3).

Определение 2. План X=(x1,x2,…, xn) задачи (1) — (3) называется опорным (допустимым базисным решением), если векторы условий Aj=(a1j, a2j,…, amj) T, входящие в разложение вектора A0=(b1,b2,…, bm) T:

(4)

с положительными коэффициентами xj, линейно независимы.

Определение 3. Система m линейно независимых векторов условий {Asi}, , включающая все те Asi, для которых xsi> 0, называется базисом опорного плана и обозначается через Бx.

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

Таким образом, если X0=(xs1,xs2,…, xs0,0,…, 0) — исходный опорный план задачи с единичным базисом As1,…, Asm и каноническая модель задачи, которая имеет следующий вид

(5)

Из системы (5) следует, что в исходном опорном плане X0 базисные переменные xsi=bi,. Алгоритм симплексного метода начинается с вычисления оптимального решения по такому опорному плану:

X0=(b1,b2,…,bm, 0,…, 0). (6)

Для исследования X0 на оптимальность необходимо разложить все векторы Aj по векторам базиса Asi:

(7)

и подсчитать разности:

j=Zj-cj. (8)

В равенстве (7) xij=aij, поскольку векторы Asi образуют единичный базис.

Записав всю исходную информацию о задаче в таблицу, получим исходную (нулевую) симплексную таблицу (Таблица 1).

Таблица 1 — Нулевая симплексная таблица

i

Бх

Сб

А0

c1

csr

ck

cn

t

A1

Asr

Ak

An

1

As1

cs1

xs1

xs11

0

x1k

x1n

t0

2

As2

cs2

xs2

xs21

0

x2k

x2n

r

Asr

csr

xsr

xr1

1

xrk

xrn

m

Asm

csm

xsm

xm1

0

xmk

xmn

m+1

-

-

Z0

sr=0

k

n

Симплекс-таблица заполняется в следующей последовательности: столбец i, строка С, столбец Бx, столбец Сб, столбец A0, столбцы A1,…, An. Так заполняются первые m строк.

В нулевой столбец (m+1)-й строки записывается значение линейной формы для имеющегося опорного плана. Это значение вычисляется по формуле

. (9)

В последующие клетки (m+1)-й строки записываются значения оценок векторов условий Aj (величины j), которые вычисляются по формуле

(10)

Базисные разности si=0.

Для проверки опорного плана на оптимальность просматриваем (m+1)-ю строку. При этом могут встретиться такие случаи:

1) Все разности j0. Тогда опорный план X0 является оптимальным и minZ=Z0.

2) Для некоторого фиксированного j j> 0 и все коэффициенты xij0,. Тогда линейная форма не ограничена множеством допустимых решений задачи. В обоих случаях процесс вычисления на этом заканчивается.

3) Для некоторых индексов j имеются j> 0 и для каждого такого j, по крайней мере, одно из чисел xij> 0. Это свидетельствует о том, что опорный план не является оптимальным и его можно улучшить за счет введения в базис вектора, отвечающего одной из таких разностей. В базис необходимо ввести тот вектор, которому отвечает maxj. Если таких разностей несколько, то берут вектор с меньшим номером.

Пусть. Тогда в базис следует ввести вектор Ak на место вектора, которому отвечает минимальное значение выражения

. (11)

Необходимо вывести из базиса вектор Asr, новый базис будет состоять из векторов: As1,As2,…, Asr-1,Asr+1,…, Asm, Ak. В этом случае xrk называют разрешающим элементом симплексной таблицы. Столбец k и строка r называются разрешающими.

Все элементы новой симплексной таблицы с нулевого столбца по n-й и с первой строки по (m+1)-ю преобразовываются при переходе к новому опорному плану по следующим рекуррентным формулам:

(12)

Обычно симплексную таблицу преобразовывают следующим образом. Направляющую строку r делят на разрешающий элемент xrk. В новой симплексной таблице на месте разрешающего элемента получается единица: x=1, а на месте разрешающего столбца получается единичный вектор с единицей в направляющей строке. Остальные строки преобразовываются так: из той строки исходной таблицы, которую необходимо преобразовать, вычитаем преобразованную направляющую, умноженную на тот элемент строки, на месте которого следует получить нуль.

В результате преобразования нулевой симплекс-таблицы по формулам (12) получаем следующую таблицу, в которой содержится новый опорный план. Опять просматриваем (m+1)-ю строку. Если все j0, то опорный план оптимален. В противном случае переходим к новому опорному плану. Процесс продолжается до тех пор, пока придем либо к оптимальному плану, либо убедимся в неограниченности линейной формы. Алгоритм симплексного метода в виде блок-схемы представлен на Рисунке 1.

/

Рисунок 1 — Представление симплекс-метода в виде блок-схемы

2. ПРОЕТИРОВАНИЕ ПК ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ

2.1 Тестовый вариант решения задачи линейного программирования симплекс-методом

Условие задачи: для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 т. Количество сырья каждого вида, необходимое для производства единицы цемента первоговида соответственно равны: 12, 4 и 3. Для цемента второго вида: 3, 5 и 14. Прибыль от реализации цемента первого вида составляет 6 у.е., от цемента второго вида — 4 у.е.

Найти максимальное значение целевой функции F (X) = 6×1 + 4×2.

Составить план, обеспечивающий наибольшую прибыль производству:

— записать математическую модель;

— решить задачу симплекс-методом;

Решение:

Математическая модель.

x1 — производство цемента первого вида;

x2 — производство цемента второго вида;

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

Определим максимальное значение целевой функции F (X) = 6×1+4×2 при следующих условиях (ограничениях).

12×1 + 3×2? 264;

4x1 + 5×2? 136;

3x1 + 14×2? 266.

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

12×1 + 3×2 + 1×3 + 0×4 + 0×5 = 264;

4x1 + 5×2 + 0×3 + 1×4 + 0×5 = 136;

3x1 + 14×2 + 0×3 + 0×4 + 1×5 = 266.

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

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

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

x3, x4, x5.

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

Таблица 2 — Первый опорный план в виде нулевой таблицы

План

Базис

В

x1

x2

x3

x4

x5

0

x3

264

12

3

1

0

0

x4

136

4

5

0

1

0

x5

266

3

14

0

0

1

Индексная строка

F (X0)

0

-6

-4

0

0

0

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

Таблица 3 — Первая симплекс-таблица

План

Базис

В

x1

x2

x3

x4

x5

min

1

x3

264

12

3

1

0

0

22

x4

136

4

5

0

1

0

34

x5

266

3

14

0

0

1

88. 67

Индексная строка

F (X1)

0

-6

-4

0

0

0

0

Итерация № 0.

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

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

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

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

Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен 12 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x1. Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3плана 0 на разрешающий элемент, равный 12. На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x1 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент 12

НЭ = СЭ — (А*В)/РЭ, где

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

Таблица 4 — Вторая симплекс-таблица

План

Базис

В

x1

x2

x3

x4

x5

min

2

x1

22

1

0. 25

0. 0833

0

0

88

x4

48

0

4

-0. 3333

1

0

12

x5

200

0

13. 25

-0. 25

0

1

15. 09

Индексная строка

F (X2)

132

0

-2. 5

0. 5

0

0

0

Итерация № 1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:

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

Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x2. Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=4. На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x2 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Конец итераций: индексная строка не содержит отрицательных элементов — найден оптимальный план.

Таблица 5 — Окончательный вариант симплекс-таблицы

План

Базис

В

x1

x2

x3

x4

x5

3

x1

19

1

0

0. 1042

-0. 0625

0

x2

12

0

1

-0. 0833

0. 25

0

x5

41

0

0

0. 8542

-3. 31

1

Индексная строка

F (X3)

162

0

0

0. 2917

0. 625

0

Оптимальный план можно записать так:

x1 = 19; x2 = 12;

F (X) = 6*19 + 4*12 = 162.

3. РАЗРАБОТКА ПК ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ

3.1 Выбор языка программирования и среды разработки ПК для решения задач линейного программирования симплексным методом

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

3.2 Модули и их взаимодействие между собой

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

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

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

SDT-диаграмма (диаграмма переходов состояний) демонстрирует поведение разрабатываемой программной системы при получении управляющих воздействий (извне), как показано на Рисунке 5.

Рисунок — 5 Диаграмма переходов состояний (STD)

3.3 Описание П К для решения задач линейного программирования симплексным методом

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

Для работы с программой необходимо открыть exe-файл под названим LP. После чего нужно запустить программу и получить окно следующего вида, показанного на Рисунке 6.

Рисунок 6 — Окно начала работы программы

Для того чтобы создать задачу, нужно нажать на кнопку «Создать новую задачу», которая находится на панели инструментов. Вы увидите на экране окно, изображенное на Рисунке 7, где будут отображаться вводимые пользователем параметры задачи.

Рисунок 7 — Окно для вводимых параметров задачи

После чего на панели инструментов выбрать кнопку «Параметры задачи», где задаются значения функции, ее ограничения, как изображено на Рисунках 8−9.

Рисунок 8 — Задание функции и поиска решений

Рисунок 9 — Задание ограничений задачи

После создания задачи линейного программирования, сохраняем ее, используя кнопку на панели инструментов под названием «Сохранить».

Чтобы решить данную задачу симплекс-методом, выбираем на панели кнопку «Решить задачу симплекс-методом» и получаем исход решения: количество итераций с результатами, а также максимальное значение функции и вектор функции, то есть значения параметров Х, как показано на Рисунке 10.

Рисунок 10 — Полученный результат реализации решения задачи ПК

Для вызова справки необходимо выбрать кнопку на панели инструментов «Справка», после чего на экране отобразиться окно с руководством по эксплуатации разработанного ПК (Рисунок 11).

Рисунок 11 — Вызов справки

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

ВЫВОДЫ

программа линейный симплекс модуль

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

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

ЛИТЕРАТУРА

1 http: //ru. wikipedia. org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0% BB% D0%B5%D0%BA%D1%81%D0%BC%D0%B5%D1%82%D0%BE%D0%B4

2 http: //saim. ts6. ru/pages/8. htm

3 Г. Жимерин, В. А. Мясников — «Автоматизированные и автоматические системы уравнения» — 1975 г.

4 Е. С. Венцель — «Исследование операций» — 1972 г.

5 http: //math. semestr. ru/simplex/primersolve. php

6 МУ к ЛР «Методы условной оптимизации «по дисциплине «Методы синтеза и оптимизации"/Сост.: Г. Б. Билык, О. В. Веремей. — Краматорск: ДГМА, 2000. — 56с.

7 Мину М. Математическое программирование. — М.: Наука, 1990. — 488 с.

ПРИЛОЖЕНИЕ А

Листинг программы:

private

{ Private declarations }

procedure CreateChild (const Name: String);

public

{ Public declarations }

end;

var

MainForm: TMainForm;

ItemDel: integer;

implementation

uses Parameters, About;

{$R *. DFM}

procedure TMainForm. CreateChild (const Name: String);

var

Child: TChildForm;

begin

Child: =TChildForm. Create (Application);

child. Caption:=Name;

end;

procedure TMainForm. ExitPClick (Sender: TObject);

begin

Close;

end;

procedure TMainForm. NewClick (Sender: TObject);

begin

CreateChild ('Задача '+IntToStr (MDIChildCount+1));

end;

procedure TMainForm. FileMenuClick (Sender: TObject);

begin

if ActiveMDIChild< >nil then

begin

MainForm. CloseChild. Enabled:=true;

MainForm. Save. Enabled:=true;

MainForm. SaveAs. Enabled:=true;

MainForm. Print. Enabled:=true

end

else

begin

MainForm. CloseChild. Enabled:=false;

MainForm. Save. Enabled:=false;

MainForm. SaveAs. Enabled:=false;

MainForm. Print. Enabled:=false

end

end;

procedure TMainForm. CloseChildClick (Sender: TObject);

begin

if ActiveMDIChild< >nil then ActiveMDIChild. Close;

end;

procedure TMainForm. EditClick (Sender: TObject);

begin

if ActiveMDIChild< >nil then

begin

MainForm. ChangeFun. Enabled:=true;

MainForm. AddLim. Enabled:=true;

MainForm. DelLim. Enabled:=true;

MainForm. N8. Enabled:=true;

MainForm. N20. Enabled:=true;

MainForm. N22. Enabled:=true;

MainForm. N24. Enabled:=true;

MainForm. N25. Enabled:=true;

end

else

begin

MainForm. ChangeFun. Enabled:=false;

MainForm. AddLim. Enabled:=false;

MainForm. DelLim. Enabled:=false;

MainForm. N8. Enabled:=false;

MainForm. N20. Enabled:=false;

MainForm. N22. Enabled:=false;

MainForm. N24. Enabled:=false;

MainForm. N25. Enabled:=false;

end

end;

procedure TMainForm. ChangeFunClick (Sender: TObject);

begin

ParametersForm. PageControl1. ActivePageIndex:=0;

ParametersForm. ShowModal;

end;

procedure TMainForm. AddLimClick (Sender: TObject);

begin

ParametersForm. PageControl1. ActivePageIndex:=1;

ParametersForm. ShowModal;

end;

procedure TMainForm. N2Click (Sender: TObject);

begin

MainForm. Enabled:=False;

AboutForm. Visible:=true;

end;

procedure TMainForm. N14Click (Sender: TObject);

begin

Cascade

end;

procedure TMainForm. N15Click (Sender: TObject);

begin

Tile

end;

procedure TMainForm. N16Click (Sender: TObject);

begin

ArrangeIcons

end;

procedure TMainForm. N18Click (Sender: TObject);

var i: integer;

begin

for i: =mdichildcount-1 downto 0 do

mdichildren[i]. WindowState:=wsminimized;

end;

procedure TMainForm. N5Click (Sender: TObject);

begin

if ActiveMDIChild< >nil then

begin

MainForm. N6. Enabled:=true;

MainForm. N7. Enabled:=true;

MainForm. N30. Enabled:=true

end

else

begin

MainForm. N6. Enabled:=false;

MainForm. N7. Enabled:=false;

MainForm. N30. Enabled:=false;

end

end;

procedure TMainForm. N13Click (Sender: TObject);

begin

if ActiveMDIChild< >nil then

begin

MainForm. N14. Enabled:=true;

MainForm. N15. Enabled:=true;

MainForm. N16. Enabled:=true;

MainForm. N18. Enabled:=true;

end

else

begin

MainForm. N14. Enabled:=false;

MainForm. N15. Enabled:=false;

MainForm. N16. Enabled:=false;

MainForm. N18. Enabled:=false;

end;

end;

procedure TMainForm. N4Click (Sender: TObject);

begin

Application. HelpCommand (3, 0);

end;

//Симплекс-метод

procedure TMainForm. N6Click (Sender: TObject);

var

SimplexTable, SimplexTableNew: array of array of extended;

GoalFun: array of extended;

ArtFun: array of extended;

ExtrEstimation: extended;

k, i, j, MoreCount, LessCount, EquallyCount, extrItem, WLine, IterCount: integer;

Art, bil: boolean;

label fin, up;

begin

Art: =true;bil:=false;IterCount:=0;

SimplexTable: =nil;

MoreCount: =0;LessCount:=0;EquallyCount:=0;

{1}//Сортировка ограничений: 1) > =; 2) =; 3) <=.

{2}//Порождение начального базиса

{3}//Итерационное построение симплекс-таблиц

{1}//---------------------------------------------------------------------------

//Сортировка «Больше»

with MainForm. ActiveMDIChild as TChildForm do

begin

//строки в таблицах дочернего окна нумеруются с 1

//нулевая строка резервная

for i: =1 to SignsChild. RowCount-1 do

begin

if (SignsChild. Cells[0,i]='>') or (SignsChild. Cells[0,i]='>=') then

begin

inc (MoreCount);

SetLength (SimplexTable, LimChild. ColCount+2,MoreCount);

//коэффициенты

for j: =0 to LimChild. ColCount-1 do

SimplexTable[j+2,MoreCount-1]: =StrToFloat (LimChild. cells[j, i]);

//Пока нули (потом базис…)

SimplexTable[0,MoreCount-1]: =0;

//Значение (B i-ый)

SimplexTable[1,MoreCount-1]: =StrToFloat (BChild. cells[0,i]);

end;

end;

//Сортировка «Равно»

for i: =1 to SignsChild. RowCount-1 do

begin

if SignsChild. Cells[0,i]='=' then

begin

inc (EquallyCount);

SetLength (SimplexTable, LimChild. ColCount+2,MoreCount+EquallyCount);

//коэффициенты

for j: =0 to LimChild. ColCount-1 do

SimplexTable[j+2,MoreCount+EquallyCount-1]: =StrToFloat (LimChild. cells[j, i]);

//Пока нули (потом базис…)

SimplexTable[0,MoreCount+EquallyCount-1]: =0;

//Значение (B i-ый)

SimplexTable[1,MoreCount+EquallyCount-1]: =StrToFloat (BChild. cells[0,i]);

end;

end;

//Сортировка «Меньше»

for i: =1 to SignsChild. RowCount-1 do

begin

if (SignsChild. Cells[0,i]='<') or (SignsChild. Cells[0,i]='<=') then

begin

inc (LessCount);

SetLength (SimplexTable, LimChild. ColCount+2,MoreCount+EquallyCount+LessCount);

//коэффициенты

for j: =0 to LimChild. ColCount-1 do

SimplexTable[j+2,MoreCount+EquallyCount+LessCount-1]: =StrToFloat (LimChild. cells[j, i]);

//Пока нули (потом базис…)

SimplexTable[0,MoreCount+EquallyCount+LessCount-1]: =0;

//Значение (B i-ый)

SimplexTable[1,MoreCount+EquallyCount+LessCount-1]: =StrToFloat (BChild. cells[0,i]);

end;

end;

end;

{2}//---------------------------------------------------------------------------

//Порождение начального базиса

//2.1 Добавить коэф. -1 (> =)

for j: =0 to MoreCount-1 do

begin

Setlength (SimplexTable, length (SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i: =length (SimplexTable)-MoreCount+1 to length (SimplexTable)-1 do

SimplexTable[i, j]: =0;

SimplexTable[length (SimplexTable)-1,j]: =-1;

end;

//2.2 Добавить коэф. 1 (< =)

for j: =MoreCount+EquallyCount to MoreCount+EquallyCount+LessCount-1 do

begin

Setlength (SimplexTable, length (SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i: =length (SimplexTable)-LessCount+2 to length (SimplexTable)-1 do

SimplexTable[i, j]: =0;

SimplexTable[length (SimplexTable)-1,j]: =1;

end;

//2.3 Добавить искусственные коэф. (>= и =)

for j: =0 to MoreCount+EquallyCount-1 do

begin

Setlength (SimplexTable, length (SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i: =length (SimplexTable)-MoreCount+1 to length (SimplexTable)-1 do

SimplexTable[i, j]: =0;

SimplexTable[length (SimplexTable)-1,j]: =1;

end;

//Целевая функция GoalFun

GoalFun: =nil;

with MainForm. ActiveMDIChild as TChildForm do

begin

SetLength (GoalFun, GoalChild. ColCount+1);

for i: =1 to GoalChild. ColCount do

begin

if parametersForm. Min. Checked then GoalFun[i]: =StrToFloat (goalChild. Cells[i-1,1])

else GoalFun[i]: =-1*StrToFloat (goalChild. Cells[i-1,1]);

end;

end;

//Искусственная функция ArtFun

ArtFun: =nil;

SetLength (ArtFun, length (SimplexTable)-1-MoreCount);

//i=1 — Значение иск. функции

for i: =1 to length (SimplexTable)-3 do

for j: =0 to MoreCount-1 do ArtFun[i-1]: =ArtFun[i-1]-SimplexTable[i, j];

//------------------------------------------------------------------------------

//Минимизация искусственной функции

//Базис

if MoreCount>0 then

begin

for j: =0 to MoreCount-1 do

SimplexTable[0,j]: =length (simplexTable)-MoreCount+j-1;

for i: =MoreCount to length (simplexTable[0])-1 do

SimplexTable[0,i]: =length (simplexTable)-(LessCount+EquallyCount+MoreCount)+(i-MoreCount)-1;

end

else

for i: =0 to LessCount+EquallyCount-1 do

SimplexTable[0,i]: =length (simplexTable)-(LessCount+EquallyCount+MoreCount)+i-1;

//2 нижние строки для оценок

SetLength (SimplexTable, length (SimplexTable), length (SimplexTable[0])+2);

for i: =0 to length (GoalFun)-1 do SimplexTable[i+1,length (SimplexTable[0])-2]: =goalFun[i];

for i: =0 to length (ArtFun)-1 do SimplexTable[i+1,length (SimplexTable[0])-1]: =ArtFun[i];

SimplexTableNew: =nil;

SetLength (SimplexTableNew, length (SimplexTable), length (SimplexTable[0]));

//итерации…

up:

repeat

if not art then inc (IterCount);

if IterCount=Parametersform. CountIteration. Value then

begin

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Достигнуто предельное число итераций. Решение не найдено');

exit;

end;

end;

{

//Может функция не ограничена? => поиск столбца с отрицательными коэф.

k: =0;

if art then

for i: =2 to length (simplexTable)-1 do

begin

if simplexTable[i, length (SimplexTable[0])-1]<0 then

begin

// k: =0;

for j: =0 to length (SimplexTable[0])-3 do

if simplexTable[i, j]< =0 then inc (k);

if k=length (SimplexTable[0])-2 then

begin

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Невозможно найти начальный базис');

exit;

end;

k: =0;

end;

end;

end;

k: =0;

if not art then

for i: =2 to length (simplexTable)-1 do

begin

if simplexTable[i, length (SimplexTable[0])-1]<0 then

begin

k: =0;

for j: =0 to length (SimplexTable[0])-2 do

if simplexTable[i, j]< =0 then inc (k);

if k=length (SimplexTable[0])-1 then

begin

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Целевая функция не ограничена');

exit;

end;

end;

end;

end;

}

//поиск первой минимальной из отрицательных оценки искуственной функции

ExtrEstimation: =100 000;

extrItem: =0;

for i: =2 to length (simplexTable)-1 do

if (SimplexTable[i, length (SimplexTable[0])-1]< ExtrEstimation) and (SimplexTable[i, length (SimplexTable[0])-1]< 0) then

begin

extrItem: =i-1;{новый базис}

ExtrEstimation: =SimplexTable[i, length (SimplexTable[0])-1];

end;

if ExtrEstimation=100 000 then goto fin;

{ВНИМАНИЕ!!! Delphi пропускает не используемые (по мнению Delphi) операторы. }

//выбор рабочей строки (поиск минимального из положительных)

ExtrEstimation: =100 000;

WLine: =0;

for j: =0 to length (simplexTable[0])-2 do

begin

if SimplexTable[extrItem+1,j]< >0 then

if (SimplexTable[1,j]/SimplexTable[extrItem+1,j]< ExtrEstimation) and (SimplexTable[1,j]*SimplexTable[extrItem+1,j]> 0) then

begin

WLine: =j;

ExtrEstimation: =SimplexTable[1,j]/SimplexTable[extrItem+1,j];

end;

end;

//новый базис

for i: =0 to length (SimplexTable[0])-1 do SimplexTableNew[0,i]: =SimplexTable[0,i];

SimplexTableNew[0,WLine]: =extrItem;

//перерасчет рабочей строки

for i: =1 to length (SimplexTable)-1 do SimplexTableNew[i, WLine]: =SimplexTable[I, wlINE]/SimplexTable[extrItem+1,wlINE];

//перерасчет коэффициентов

for i: =1 to length (SimplexTable)-1 do

for j: =0 to length (SimplexTable[0])-1 do

if j< >WLine then

SimplexTableNew[i, j]: =SimplexTable[i, j]-SimplexTable[i, Wline]*SimplexTable[extrItem+1,j]/SimplexTable[extrItem+1,WLine];

//копирование таблиц

for i: =0 to length (SimplexTable)-1 do for j: =0 to length (SimplexTable[0])-1 do SimplexTable[i, j]: =SimplexTableNew[i, j];

//Вывод текущего решения

if ParametersForm. CheckBox1. Checked then begin

bil: =false;

if not art then

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Итерация '+InttoStr (IterCount));

for i: =0 to GoalChild. ColCount-1 do

begin

for j: =0 to length (SimplexTable[0])-1 do

if i+1=SimplexTable[0,j] then

begin

task. Items. Add (' '+GoalChild. Cells[i, 0]+'='+FloatToStr (SimplexTable[1,j]));

bil: =true;

end;

if not bil then task. Items. Add (' '+GoalChild. Cells[i, 0]+'=0');

bil: =false;

end;

end;

end;

until false;

fin:

if art then

begin

art: =false;

SetLength (SimplexTable, Length (SimplexTable)-MoreCount, Length (SimplexTable[0])-1);

goto up;

end;

//Результат

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Результат');

for i: =0 to GoalChild. ColCount-1 do

begin

for j: =0 to length (SimplexTable[0])-1 do

if i+1=SimplexTable[0,j] then

begin

task. Items. Add (' '+GoalChild. Cells[i, 0]+'='+FloatToStr (SimplexTable[1,j]));

bil: =true;

end;

if not bil then task. Items. Add (' '+GoalChild. Cells[i, 0]+'=0');

bil: =false;

end;

task. Items. Add ('');

if parametersForm. Min. Checked then

task. Items. Add ('Минимальное значение функции '+FloatToStr (-1*(SimplexTable[1,length (SimplexTable[0])-1])))

else

task. Items. Add ('Максимальное значение функции '+FloatToStr (SimplexTable[1,length (SimplexTable[0])-1]));

end;

end;

procedure TMainForm. SaveAsClick (Sender: TObject);

var

FExt: String;

begin

with SaveDialog1 do

begin

if ActiveMDIChild. Caption[1]='З' then

FileName: =ActiveMDIChild. Caption+'. tsk'

else

FileName: =ActiveMDIChild. Caption;

FExt: =ExtractFileExt (FileName);

if length (Fext)=0 then

FExt: ='. tsk';

filter: ='Files (*'+FExt+')|*'+FExt;

if Execute then

with ActiveMDIchild as TChildForm do

SaveData (FileName);

end;

end;

procedure TMainForm. PrintClick (Sender: TObject);

begin

PrintDialog1. Execute;

end;

procedure TMainForm. OpenClick (Sender: TObject);

var

s: string;

i, k: integer;

begin

if OpenDialog1. Execute then

begin

with fileMenu do

begin

if not N11. Visible then N11. Visible:=true;

k: =IndexOf (N1Name1);

for i: =count-3 downto k+1 do

begin

s: =items[i-1]. caption;

s[2]: =chr (ord ('0')+(i-k+1));

Items[i]. Caption:=S;

Items[i]. Visible:=Items[i-1]. Visible;

end;

n1name1. Caption:='&1 '+OpenDialog1. FileName;

n1name1. Visible:=true;

end;

CreateChild (OpenDialog1. FileName);

with ActiveMDIChild as TChildForm do

LoadData (OpenDialog1. FileName);

ParametersForm. FormShow (Sender);

ParametersForm. Button3Click (Sender);

end;

end;

procedure TMainForm. N27Click (Sender: TObject);

begin

N27. checked:=not N27. checked;

if N27. checked then toolbar1. Visible:=true else toolbar1. Visible:=false;

end;

procedure TMainForm. N28Click (Sender: TObject);

begin

N28. checked:=not N28. checked;

if N28. checked then statusbar1. Visible:=true else statusbar1. Visible:=false;

end;

procedure TMainForm. N7Click (Sender: TObject);

var

SimplexTable, SimplexTableNew: array of array of extended;

GoalFun: array of extended;

ArtFun: array of extended;

ExtrEstimation: extended;

k, i, j, MoreCount, LessCount, EquallyCount, extrItem, WLine, IterCount: integer;

Art, bil: boolean;

label fin, up, up2;

begin

Art: =true;bil:=false;IterCount:=0;

SimplexTable: =nil;

MoreCount: =0;LessCount:=0;EquallyCount:=0;

{1}//Сортировка ограничений: 1) > =; 2) =; 3) <=.

{2}//Порождение начального базиса

{3}//Итерационное построение симплекс-таблиц

{1}//---------------------------------------------------------------------------

//Сортировка «Больше»

with MainForm. ActiveMDIChild as TChildForm do

begin

//строки в таблицах дочернего окна нумеруются с 1

//нулевая строка резервная

for i: =1 to SignsChild. RowCount-1 do

begin

if (SignsChild. Cells[0,i]='>') or (SignsChild. Cells[0,i]='>=') then

begin

inc (MoreCount);

SetLength (SimplexTable, LimChild. ColCount+2,MoreCount);

//коэффициенты

for j: =0 to LimChild. ColCount-1 do

SimplexTable[j+2,MoreCount-1]: =StrToFloat (LimChild. cells[j, i]);

//Пока нули (потом базис…)

SimplexTable[0,MoreCount-1]: =0;

//Значение (B i-ый)

SimplexTable[1,MoreCount-1]: =StrToFloat (BChild. cells[0,i]);

end;

end;

//Сортировка «Равно»

for i: =1 to SignsChild. RowCount-1 do

begin

if SignsChild. Cells[0,i]='=' then

begin

inc (EquallyCount);

SetLength (SimplexTable, LimChild. ColCount+2,MoreCount+EquallyCount);

//коэффициенты

for j: =0 to LimChild. ColCount-1 do

SimplexTable[j+2,MoreCount+EquallyCount-1]: =StrToFloat (LimChild. cells[j, i]);

//Пока нули (потом базис…)

SimplexTable[0,MoreCount+EquallyCount-1]: =0;

//Значение (B i-ый)

SimplexTable[1,MoreCount+EquallyCount-1]: =StrToFloat (BChild. cells[0,i]);

end;

end;

//Сортировка «Меньше»

for i: =1 to SignsChild. RowCount-1 do

begin

if (SignsChild. Cells[0,i]='<') or (SignsChild. Cells[0,i]='<=') then

begin

inc (LessCount);

SetLength (SimplexTable, LimChild. ColCount+2,MoreCount+EquallyCount+LessCount);

//коэффициенты

for j: =0 to LimChild. ColCount-1 do

SimplexTable[j+2,MoreCount+EquallyCount+LessCount-1]: =StrToFloat (LimChild. cells[j, i]);

//Пока нули (потом базис…)

SimplexTable[0,MoreCount+EquallyCount+LessCount-1]: =0;

//Значение (B i-ый)

SimplexTable[1,MoreCount+EquallyCount+LessCount-1]: =StrToFloat (BChild. cells[0,i]);

end;

end;

end;

{2}//---------------------------------------------------------------------------

//Порождение начального базиса

//2.1 Добавить коэф. -1 (> =)

for j: =0 to MoreCount-1 do

begin

Setlength (SimplexTable, length (SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i: =length (SimplexTable)-MoreCount+1 to length (SimplexTable)-1 do

SimplexTable[i, j]: =0;

SimplexTable[length (SimplexTable)-1,j]: =-1;

end;

//2.2 Добавить коэф. 1 (< =)

for j: =MoreCount+EquallyCount to MoreCount+EquallyCount+LessCount-1 do

begin

Setlength (SimplexTable, length (SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i: =length (SimplexTable)-LessCount+2 to length (SimplexTable)-1 do

SimplexTable[i, j]: =0;

SimplexTable[length (SimplexTable)-1,j]: =1;

end;

//2.3 Добавить искусственные коэф. (>= и =)

for j: =0 to MoreCount+EquallyCount-1 do

begin

Setlength (SimplexTable, length (SimplexTable)+1,MoreCount+EquallyCount+LessCount);

for i: =length (SimplexTable)-MoreCount+1 to length (SimplexTable)-1 do

SimplexTable[i, j]: =0;

SimplexTable[length (SimplexTable)-1,j]: =1;

end;

//Целевая функция GoalFun

GoalFun: =nil;

with MainForm. ActiveMDIChild as TChildForm do

begin

SetLength (GoalFun, GoalChild. ColCount+1);

for i: =1 to GoalChild. ColCount do

begin

if parametersForm. Min. Checked then GoalFun[i]: =StrToFloat (goalChild. Cells[i-1,1])

else GoalFun[i]: =-1*StrToFloat (goalChild. Cells[i-1,1]);

end;

end;

//Искусственная функция ArtFun

ArtFun: =nil;

SetLength (ArtFun, length (SimplexTable)-1-MoreCount);

//i=1 — Значение иск. функции

for i: =1 to length (SimplexTable)-3 do

for j: =0 to MoreCount-1 do ArtFun[i-1]: =ArtFun[i-1]-SimplexTable[i, j];

//------------------------------------------------------------------------------

//Минимизация искусственной функции

//Базис

if MoreCount>0 then

begin

for j: =0 to MoreCount-1 do

SimplexTable[0,j]: =length (simplexTable)-MoreCount+j-1;

for i: =MoreCount to length (simplexTable[0])-1 do

SimplexTable[0,i]: =length (simplexTable)-(LessCount+EquallyCount+MoreCount)+(i-MoreCount)-1;

end

else

for i: =0 to LessCount+EquallyCount-1 do

SimplexTable[0,i]: =length (simplexTable)-(LessCount+EquallyCount+MoreCount)+i-1;

//2 нижние строки для оценок

SetLength (SimplexTable, length (SimplexTable), length (SimplexTable[0])+2);

for i: =0 to length (GoalFun)-1 do SimplexTable[i+1,length (SimplexTable[0])-2]: =goalFun[i];

for i: =0 to length (ArtFun)-1 do SimplexTable[i+1,length (SimplexTable[0])-1]: =ArtFun[i];

//итерации…

up:

repeat

if not art then inc (IterCount);

if IterCount=Parametersform. CountIteration. Value then

begin

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Достигнуто предельное число итераций. Решение не найдено');

exit;

end;

end;

//Может функция не ограничена? => поиск столбца с отрицательными коэф.

k: =0;

if art then

for i: =2 to length (simplexTable)-1 do

begin

if simplexTable[i, length (SimplexTable[0])-1]<0 then

begin

// k: =0;

for j: =0 to length (SimplexTable[0])-3 do

if simplexTable[i, j]< =0 then inc (k);

if k=length (SimplexTable[0])-2 then

begin

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Невозможно найти начальный базис');

exit;

end;

k: =0;

end;

end;

end;

k: =0;

if not art then

for i: =2 to length (simplexTable)-1 do

begin

if simplexTable[i, length (SimplexTable[0])-1]<0 then

begin

k: =0;

for j: =0 to length (SimplexTable[0])-2 do

if simplexTable[i, j]< =0 then inc (k);

if k=length (SimplexTable[0])-1 then

begin

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Целевая функция не ограничена');

exit;

end;

end;

end;

end;

//поиск первой минимальной из отрицательных оценки искуственной функции

ExtrEstimation: =100 000;

extrItem: =0;

for i: =2 to length (simplexTable)-1 do

if (SimplexTable[i, length (SimplexTable[0])-1]< ExtrEstimation) and (SimplexTable[i, length (SimplexTable[0])-1]< 0) then

begin

extrItem: =i-1;{новый базис}

ExtrEstimation: =SimplexTable[i, length (SimplexTable[0])-1];

end;

if ExtrEstimation=100 000 then goto fin;

{ВНИМАНИЕ!!! Delphi пропускает не используемые (по мнению Delphi) операторы. }

//выбор рабочей строки (поиск минимального из положительных)

ExtrEstimation: =100 000;

WLine: =0;

for j: =0 to length (simplexTable[0])-2 do

begin

if SimplexTable[extrItem+1,j]< >0 then

if (SimplexTable[1,j]/SimplexTable[extrItem+1,j]< ExtrEstimation) and (SimplexTable[1,j]*SimplexTable[extrItem+1,j]> 0) then

begin

WLine: =j;

ExtrEstimation: =SimplexTable[1,j]/SimplexTable[extrItem+1,j];

end;

end;

up2:

SimplexTableNew: =nil;

SetLength (SimplexTableNew, length (SimplexTable), length (SimplexTable[0]));

//новый базис

for i: =0 to length (SimplexTable[0])-1 do SimplexTableNew[0,i]: =SimplexTable[0,i];

SimplexTableNew[0,WLine]: =extrItem;

//перерасчет рабочей строки

for i: =1 to length (SimplexTable)-1 do SimplexTableNew[i, WLine]: =SimplexTable[I, wlINE]/SimplexTable[extrItem+1,wlINE];

//перерасчет коэффициентов

for i: =1 to length (SimplexTable)-1 do

for j: =0 to length (SimplexTable[0])-1 do

if j< >WLine then

SimplexTableNew[i, j]: =SimplexTable[i, j]-SimplexTable[i, Wline]*SimplexTable[extrItem+1,j]/SimplexTable[extrItem+1,WLine];

//копирование таблиц

for i: =0 to length (SimplexTable)-1 do for j: =0 to length (SimplexTable[0])-1 do SimplexTable[i, j]: =SimplexTableNew[i, j];

//Вывод текущего решения

if ParametersForm. CheckBox1. Checked then begin

bil: =false;

if not art then

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Итерация '+InttoStr (IterCount));

for i: =0 to GoalChild. ColCount-1 do

begin

for j: =0 to length (SimplexTable[0])-1 do

if i+1=SimplexTable[0,j] then

begin

task. Items. Add (' '+GoalChild. Cells[i, 0]+'='+FloatToStr (SimplexTable[1,j]));

bil: =true;

end;

if not bil then task. Items. Add (' '+GoalChild. Cells[i, 0]+'=0');

bil: =false;

end;

end;

end;

until false;

fin:

if art then

begin

art: =false;

SetLength (SimplexTable, Length (SimplexTable)-MoreCount, Length (SimplexTable[0])-1);

goto up;

end;

//Если среди базисных переменных нет дробных то конец…

bil: =false;

for i: =0 to ParametersForm. dim1. Value-1 do

if (SimplexTable[0,i]< =ParametersForm. dim1. Value) and (SimplexTable[1,i]< >trunc (SimplexTable[1,i])) then bil: =true;

if not bil then

begin

//Результат

with MainForm. ActiveMDIChild as TChildForm do

begin

task. Items. Add ('');

task. Items. Add ('Результат');

for i: =0 to GoalChild. ColCount-1 do

begin

for j: =0 to length (SimplexTable[0])-1 do

if i+1=SimplexTable[0,j] then

begin

task. Items. Add (' '+GoalChild. Cells[i, 0]+'='+FloatToStr (SimplexTable[1,j]));

bil: =true;

end;

if not bil then task. Items. Add (' '+GoalChild. Cells[i, 0]+'=0');

bil: =false;

end;

task. Items. Add ('');

if parametersForm. Min. Checked then

task. Items. Add ('Минимальное значение функции '+FloatToStr (-1*(SimplexTable[1,length (SimplexTable[0])-1])))

else

task. Items. Add ('Максимальное значение функции '+FloatToStr (SimplexTable[1,length (SimplexTable[0])-1]));

end;

exit;

end;

//Дополнительная строка и столбец

SetLength (SimplexTable, Length (SimplexTable)+1,Length (SimplexTable[0])+1);

For i: =0 to Length (SimplexTable)-1 do

SimplexTable[i, Length (SimplexTable[0])-1]: =SimplexTable[i, Length (SimplexTable[0])-2];

for i: =0 to Length (SimplexTable[0])-1 do SimplexTable[Length (SimplexTable)-1,i]: =0;

SimplexTable[Length (SimplexTable)-1,Length (SimplexTable[0])-2]: =1;

//поиск максимальной дробной части

ExtrEstimation: =0;

WLine: =0;

for i: =0 to Length (SimplexTable[0])-3 do

begin

if (abs (SimplexTable[1,i]-trunc (SimplexTable[1,i]))> ExtrEstimation) and (abs (SimplexTable[1,i]-round (SimplexTable[1,i]))>0. 001) then

begin

ExtrEstimation: =abs (SimplexTable[1,i]-trunc (SimplexTable[1,i]));

WLine: =i;

end;

end;

SetLength (goalfun, Length (goalfun)+1);

GoalFun[Length (goalfun)-1]: =0;

SimplexTable[0,Length (SimplexTable[0])-2]: =Length (SimplexTable)-2;

SimplexTable[1,Length (SimplexTable[0])-2]: =-ExtrEstimation/ExtrEstimation;

for i: =2 to Length (SimplexTable)-2 do

begin

SimplexTable[i, Length (SimplexTable[0])-2]: =-(abs (SimplexTable[i, WLine]-trunc (SimplexTable[i, WLine])))/ExtrEstimation;

end;

SimplexTable[round (SimplexTable[0,WLine])+1,Length (SimplexTable[0])-2]: =0;

//поиск первой минимальной из положительных оценки искуственной функции

ExtrEstimation: =100 000;

extrItem: =0;

for i: =2 to length (simplexTable)-1 do

if (SimplexTable[i, length (SimplexTable[0])-1]< ExtrEstimation) and (SimplexTable[i, length (SimplexTable[0])-1]> 0) then

begin

extrItem: =i-1;{новый базис}

ExtrEstimation: =SimplexTable[i, length (SimplexTable[0])-1];

end;

//??? if ExtrEstimation=-100 000 then goto fin;

WLine: =length (SimplexTable[0])-2;

goto up2;

end;

procedure TMainForm. SaveClick (Sender: TObject);

begin

if pos ('Задача', activemdichild. caption)=1 then

SaveAsClick (Sender) else with activemdichild as TChildForm do

SaveData (Caption);

end;

procedure TMainForm. DelLimClick (Sender: TObject);

var i: byte;

begin

with ActiveMDIChild as TChildForm do

begin

if ItemDel<4 then MessageDlg ('Ограничение не выбрано', mtWarning,[mbOK], 0) else

begin

ParametersForm. FormShow (Sender);

for i: =0 to ItemDel-5 do ParametersForm. BitBtn3Click (Sender);

ParametersForm. BitBtn1Click (Sender);

ParametersForm. Button3Click (Sender);

end;

end;

end;

procedure TMainForm. N8Click (Sender: TObject);

var i: byte;

begin

with Mainform. ActiveMDIChild as TChildForm do

begin

GoalChild. ColCount:=2;

LimChild. ColCount:=2;

LimChild. RowCount:=1;

BChild. RowCount:=1;

SignsChild. RowCount:=1;

for i: =0 to 1 do

GoalChild. Cells[i, 1]:='0';

GoalChild. Cells[0,0]:='X1';

GoalChild. Cells[1,0]:='X2';

Task. Clear;

end;

end;

procedure TMainForm. N1Name1Click (Sender: TObject);

var FileName: string;

begin

with sender as TMenuItem do

begin

FileName: =caption;

System. Delete (FileName, 1,2);

end;

CreateChild (OpenDialog1. FileName);

with ActiveMDIChild as TChildForm do

LoadData (OpenDialog1. FileName);

ParametersForm. FormShow (Sender);

ParametersForm. Button3Click (Sender);

end;

end.

ПоказатьСвернуть
Заполнить форму текущей работой