Решение транспортной задачи методом потенциалов

Решение транспортной задачи методом потенциалов

ВВЕДЕНИЕ

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

В общем, виде математическая постановка экстремальной задачи состоит в определении наибольшего и наименьшего значения целевой функции f (x1,x2, …,xn) при условиях gi (x1,x2, …,xn) ? bi (i=), где f и gi -заданные функции, а bi - некоторые действительные числа.

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

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

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

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

1. СПЕЦИАЛЬНАЯ ЧАСТЬ

Математическая постановка задачи состоит в определении минимального значения функции

(1.1)

при условиях

(1.2)

(1.3)

xij0 (i= j=) (1.4)

Поскольку переменные xij (i= j=) удовлетворяют системам линейных уравнений (2) и (3) и условию неотрицательности (1.4), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Всякое неотрицательное решение систем линейных уравнений (1.2) и (1.3), определяемое матрицей X=(xij) (i= j=), называется планом транспортной задачи.

План X*=(x) (i= j=), при котором функция (1.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные задачи записывают в виде таблицы.

Таблица 1.2 -пример заполнения

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

=, (1.5)

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

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

В случае превышения запаса над потребностью, т.е. > вводится фиктивный (n+1)-й пункт назначения с потребностью bn+1= - и составляющие тарифы считаются равными нулю: cin+1=0 (i=). Полученная задача является транспортной задачей, для которой выполняется равенство (1.5).

Аналогично, при <вводится фиктивный (m+1)-й пункт отправления с запасом груза am+1= - и тарифы полагаются равными нулю: cm+1j=0 (j=). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (1.5).

Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (1.2) и (1.3) равно n+m. Так как мы предполагаем, что выполняется условие (1.5), то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше - то вырожденным.

1.3 Алгоритм метода

Для решения транспортной задачи методом потенциалов необходимо:

1. Построить опорный план по данному из методов.

2. Вычислить потенциалы поставщиков и потребителей, решив систему уравнений вида Ui+Vj=Cij.

3. Вычислить оценки Sij для всех свободных клеток по формуле Sij= Cij-( Ui+Vj). Если все Sij?0, то получим план являющийся оптимальным, при этом если все Sij?0, то полученный оптимальный план единственный. В случае если хотя бы одна оценка Sij=0 имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

Алгоритм метода потенциалов для транспортной задачи:

Vj - Ui=C, если xi,j>0, (1.1)

Vj - Ui ?C, если xi,j=0, (1.2)

Критерий (1.1) - (1.2) положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949 г. Л.В. Канторовичем и М.К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом.

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

Алгоритм начинается с выбора некоторого допустимого базисного плана. Если данный план не вырожденный, то он содержит m+n -1 ненулевых базисных клеток, и по нему можно так определить потенциалы Ui Vj , чтобы для каждой базисной клетки (т.е. для той, в которой xi,j>0) выполнялось условие

Vj - Ui =C, если xi,j>0

Поскольку система (1.3) содержит m+n -1 уравнение и m+n неизвестных, то один из потенциалов можно задать произвольно (например, приравнять V1 или U1 к нулю). После этого остальные неизвестные Ui и Vj определяются однозначно.

Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере.

Потенциал первого пункта потребления принимаем равным нулю (V1=0). Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками. В данном случае их два (это первый и второй пункты), получим:

U1=V1-C1,2=0-14=-14, U2=V1-C2,2=0-10=-10.

 Имея U2 и учитывая, что во второй строке таблицы существуют ещё ненулевые компоненты X2,2 и X2,3 , можно определить V2=U2+C2,2= -10+17=7 и V3=U2+C2,3= -10+15=5, после чего появляется возможность рассчитать U3=V3-C3,3=5-25=-20 и, наконец, V4=U3+C3,4= -20+21=1. В результате получаем полную систему потенциалов, показанную в таблице 1.1.

Таблица 1.1

Для свободных клеток транспортной таблицы вычисляются величины ?i,j=Vj-Ui , называемое разностями потенциалов. В таблице 1.2 они выписаны для всех небазисных клеток под ценами.

Таблица 1.2

Разность потенциалов ?i,j можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j. Согласно критерию оптимальности (1.1) - (1.2), если все ?i,j?Ci,j , то план оптимален, в противном случае, если существует хотя бы одна разность потенциалов ?i,j>Ci,j , то он может быть улучшен. Процесс "улучшения" плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

Кандидатом на ввод, очевидно, может быть любая клетка, в которой ?i,j>Ci,j , поскольку после ввода в базис будет обеспечено равенство ?i,j=Ci,j. Для определённости обычно рекомендуется брать ту клетку, в которой оценка ?i,j-Ci,j максимальна. В рассматриваемом нами примере это клетка (3,1).

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

Таблица 1.3

Логика алгоритма построения цепочки достаточно проста: "выйдя" из клетки (3,1) в горизонтальном направлении, мы должны "остановиться" в той же занятой клетке плана, из которой сможем двигаться дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка (3,4). Однако цепочка от (3,4) не может быть продолжена дальше, в то время как, двигаясь от (3,3) по вертикали к (2,3) и далее к (2,1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл.

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины знаком "+", а чётные "-". Знаком "+" отмечается те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком "-" - те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком "-", выбирается клетка с наименьшим значением xi,j (обозначим его ?). Она и становится кандидатом на вывод, так как уменьшение объема перевозок на большую величину может привести к отрицательным значениям xi,j в других "минусовых" клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком "+", добавляется объем ?, а из объемов клеток, помеченных знаком "-", он вычисляется. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описаны выше действия, повторяются.

В нашем примере знаком "-" отмечены клетки (2,1) и (3,3), причем x2,1=6, x3,3=26. Вычислив значение ?=min{x2,1, x3,3}=6, осуществляем преобразование и переходим к следующему базисному плану, показанному в таблице 1.4.

Таблица 1.4

Для вновь полученного плана повторяются действия стандартной итерации: рассчитываются потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план в таблице 1.3.4 также не является оптимальным (в клетке (1,3) ?i,j=25>Ci,j=21), поэтому вновь строим цепочку преобразования плана и переходим к следующему базисному плану (таблица 1.5).

Таблица 1.5

Из транспортной таблицы 1.5 видно, что полученный план оптимален, так как все разности потенциалов для небазисных клеток ?i,j=Vj - Ui не превышают соответствующих цен Ci,j. По данному плану вычисляется оптимальное (наименьшее) значение суммарных издержек на перевозку

F(x*)=10*30+16*20+20*25+18*0+5*0+16*35+13*10=1810.

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком "-", то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m+n-1 ненулевых компонент. Способ преодоления вырожденности в транспортной задачи весьма прост, а именно: предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и деле действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая задач линейного программирования. К такому выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем.

1.4 Обоснование выбора программного обеспечения

На сегодняшний день существует достаточно языков и сред программирования, при помощи которых можно создавать приложения. Наиболее известные: Delphi, Pascal, C++ и т.д.

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

Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем.

Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным.

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

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

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

Широкой популярности Pascal (его версии: Turbo Pascal и Pascal+ ) среди программистов способствовали следующие причины:

- благодаря своей компактности, удачному первоначальному описанию Pascal оказался достаточно легким для изучения;

- язык Pascal позволяет четко реализовать идеи структурного программирования и структурной организации данных;

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

- применение языка Pascal значительно подняло надежность разрабатываемых программ за счет его требований к описанию используемых в программе переменных, к проверке согласованности программы при компиляции без ее выполнения;

- использование в Pascal простых и гибких структур управления: ветвлений, циклов.

Дальнейшим развитием языка Pascal стала среда объектно-ориентированного программирования Delphi.

Delphi представляет сочетание объектное - ориентированного и визуального программирования.

Для разработки проекта была выбрана среда Delphi. Выбор данной среды обусловлен рядом особенностей Delphi:

- интегрированная среда разработки приложений - позволяет создавать компилировать, тестировать и редактировать проект или группу проектов в единой среде программирования;

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

- данное средство разработки работает под графическими операционными системами Windows;

- создаваемые приложения могут работать в различных операционных системах;

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

- в среде могут создаваться не только приложения, но и динамические библиотеки;

- библиотека компонентов содержит множество стандартных компонентов, которые можно использовать при создании приложений.

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

Delphi - это комбинация нескольких важнейших технологий:

- Высоко производительный компилятор в машинный код;

- Объектно-ориентированная модель компонент;

- Визуальное (а, следовательно, и скоростное) построение приложений и программных продуктов;

- Масштабные средства для построения баз данных.

Delphi имеет удобный пользовательский интерфейс, причём каждый пользователь имеет возможность настроить по своему вкусу.

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

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

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

В этой среде можно создать программы для Интернета и сетей, основанных на протоколах TCP\IP, а также использование программных компонентов способных работать с разными СУБД на различных компьютерах сети, не только в локальной, но и в глобальной сети. Также Delphi позволяет создавать Web - приложения.

В результате проведенного анализа наиболее популярных средств программирования можно прийти к выводу, что для реализации поставленных задач наиболее всего подходит среда объектно-ориентированного программирования Delphi.

2. ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ

2.1 Решение задачи ручным способом

Таблица 2.1 - Исходные данные

Так как данная транспортная задача является открытой необходимо добавить столбец B5.

Таблица 2.2 - Оптимальный план

Исходное опорное решение получим, например, по правилу минимального элемента.

В полученном опорном плане число занятых клеток удовлетворяют правилу

m+n-1.

5+3-1=7

Найдем потенциал поставщиков и потребителей.

Определим оценки занятых клеток.

U1=0 U2=-4 U3=-3

V1=12 V2=16 V3=1 V4=10 V5=-4

Определим оценки свободных клеток по формуле:

Sij=Cij-(Ui+Vj) S12=16-0-15=1-мах S13=13-0-14=-1

S15=-4-0-0=-4 S23=13+4-18=-1 S24=10+4-17=-3

S31=12+3-19=-4 S32=16+3-21=-2 S35=-4+3-0=-1

Перспективной является клетка S12. Строим для клетки (1;2) цикл непосредственно в таблице. Для нового плана определим новые потенциалы и оценки свободных клеток.

Таблица 2.1 - Новый оптимальный план

Определим оценки занятых клеток.

U1=0 U2=-5 U3=-3

V1=11 V2=15 V3=13 V4=10 V5=-5

Определим оценки свободных клеток по формуле:

Sij=Cij-(Ui+Vj) S11=11-0-12=-1 S12=15-0-15=0

S15=13-0-14=-1 S15=-5+5-0=0 S24=10+5-17=-2

S31=11+3-19=-5 S32=15+3-21=-3 S35=-5+3-0=-2

Рассчитаем F(x).

F(x)= 10*30+16*20+20*25+18*0+5*0+16*35+13*10=1810.

2.2 Алгоритм программы

Структура меню приложения представлена в приложении А.

1. На форме "Курсовая работа тему "Метод потенциалов"" введены исходные данные.

2. Для запуска программы необходимо нажать на кнопку "Найти оптимальный план". После чего будет произведён расчет данных записанных в файле.

3. Так же вы можете найти свой Оптимальный план. Для этого вам необходимо ввести свои данные с клавиатуры и нажать кнопку "Найти Оптимальный план".

4. Чтобы просмотреть информацию о разработчике необходимо выполнить команду Информация и выбрать пункт "Об авторе".

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

6. Выход из программы осуществляется нажатием на кнопку "Выход".

2.3 Описание программы

Procedure Naxod_Poten - находим потенциал

Procedure Naxod_delta - находим дельта

Procedure Naxod_Plan - находим оптимальный план

Procedure Init_cikl; - подпрограмма в процедуре

3. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

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

Главное меню состоит из следующих пунктов и подпунктов:

1. Файл;

1.1. Помощь;

1.2. Выход.

При выборе пункта "Помощь" пользователь может выбрать подпункт "Об авторе" и просмотреть краткую информацию о разработчике. При выборе подпункта "Справка" пользователь может просмотреть краткую инструкцию по работе с данным приложением

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

При нажатии кнопки "Найти оптимальный план" появляются, ответы решения введенной задачи на метод потенциалов.

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

ЗАКЛЮЧЕНИЕ

Предложенный курсовой проект на тему "Метод потенциалов" наглядно показал использование компьютера в решении задач математического программирования.

В работе были описаны языки С++, Object Pascal, среда программирования Delphi, и теоретическая часть на тему "Метод Потенциалов". Так же была описана программа, дан пошаговый алгоритм программы. Для правильной работы с программой была составлена инструкция для пользователя. В приложение были включены: структура программы, текст, программы, макеты экранных форм.

Используя программу, пользователь может, вводя свои исходные данные, получить решение поставленной задачи.

СПИСОК ЛИТЕРАТУРЫ

1. Архангельский А.Я. "DELPHI_5 учебный курс" - М.: "Издательство Нолидж", 2000 г.

2. Терехов Л.Л. "Экономо-математические методы" - М.: "Высшая школа", 1971 г.

3. Кузнецов Ю.Н., Козубов В.И., Волощенко А.Б. "Математическое программирование" М.: "Высшая школа", 1980 г.

4. Федоров А.Г. "Delphi 3.0 для всех" - М.: "КомпьютерПресс", 1998г.

5 Питерцева Г. А. , Потапова А. С. , Толстов В. Н. "Учебное пособие по решению задач нелинейного программирования (Градиентные методы) " -М.: "Ротапринт МАИ", 1979 г.

Приложение А

(обязательное)

Структура программы

Приложение Б

(обязательное)

Текст программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Menus, ExtCtrls, jpeg;

type

TForm1 = class(TForm)

sgIsx: TStringGrid;

Label1: TLabel;

sgZap: TStringGrid;

Label2: TLabel;

sgPotr: TStringGrid;

Label3: TLabel;

Button1: TButton;

Label4: TLabel;

sgNac: TStringGrid;

Label5: TLabel;

sgOpt: TStringGrid;

Label10: TLabel;

Label6: TLabel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

Image1: TImage;

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure Image1Click(Sender: TObject);

procedure N4Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

C,x,delta:array [1..5,1..5] of real; Potr,beta:array[1..5] of real;

Zapas,alfa: array[1..4] of real; z,p:integer; //z-количество пунктов с запасами,p - с потребностями

zapol:array [1..5,1..5] of Boolean;

zakon:Boolean; // Флаг окончания итераций

implementation

uses Unit2, Unit3;

{$R *.dfm}

//распределение ресурсов начального плана происходит методом северо-западного угла

Procedure Naxod_Poten;

Var i,j:integer;

vix:boolean;

Begin

For i:=1 to z do alfa[i]:=-MaxInt; // т.е все альфы не известны

For j:=1 to p do beta[j]:=-MaxInt; // т.е все бэты не известны

Repeat

alfa[1]:=0;

For i:=1 to z do

For j:=1 to p do

Begin

If zapol[i,j] then

if (alfa[i]=-MaxInt)and(beta[j]<>-MaxInt) then alfa[i]:=beta[j]-c[i,j]

else if (alfa[i]<>-MaxInt)and(beta[j]=-MaxInt) then beta[j]:=c[i,j]+alfa[i];

End;

vix:=True;

For i:=1 to z do if alfa[i]=-MaxInt then vix:=False;

For j:=1 to p do if beta[j]=-MaxInt then vix:=False;

Until vix;

End;

Procedure Naxod_delta;

Var i,j:integer;

Begin

For i:=1 to z do

For j:=1 to p do

Begin

delta[i,j]:=beta[j]-alfa[i]-c[i,j];

End;

End;

Procedure Naxod_Plan;

var i,j,sv_i,sv_j,i_tek,j_tek,i_min,j_min:integer;

max,min:real;

znaki:array [1..5,1..5] of integer;

kol_v_stolbce:array[1..5] of integer;

kol_v_stroke: array[1..5] of integer;

zapol1:array [1..5,1..5] of Boolean;

Procedure Init_cikl; //подпрограмма в процедуре

var i,j:integer;

Begin

For i:=1 to z do

For j:=1 to p do

znaki[i,j]:=0;

// найдем количество заполненых ячеек в строках и столбцах

for i:=1 to z do kol_v_stroke[i]:=0;

For j:=1 to p do kol_v_stolbce[j]:=0;

for i:=1 to z do

For j:=1 to p do

if zapol1[i,j] then

begin

kol_v_stroke[i]:=kol_v_stroke[i]+1;

kol_v_stolbce[j]:=kol_v_stolbce[j]+1;

end;

i_tek:=sv_i;

j_tek:=sv_j;

znaki[i_tek,j_tek]:=1;

end;

Begin

max:=0;

For i:=1 to z do

For j:=1 to p do

if (delta[i,j]>max)and (Not(zapol[i,j])) then

begin

max:= delta[i,j];

sv_i:=i; sv_j:=j;

//Клетка (sv_i,sv_j) - новая заполняемая клетка

end;

if max=0 then // если не положительных дельта

begin

zakon:=True;

exit

end;

For i:=1 to z do

For j:=1 to p do // переписываем матрицу заполнения

zapol1[i,j]:=zapol[i,j];

// Теперь найдем цикл

Init_cikl;

Repeat

// переход по столбцу

for i:=1 to z do

if (i<>i_tek)and zapol1[i,j_tek] then

Begin

i_tek:=i;

znaki[i_tek,j_tek]:=-1;

break;

End;

if i_tek=sv_i then break;

// переход по строке

for j:=1 to p do

if (j<>j_tek)and zapol1[i_tek,j] then

Begin

j_tek:=j;

znaki[i_tek,j_tek]:=1;

break;

End;

if kol_v_stolbce[j_tek]<2 then // если зашли в тупик

begin

zapol1[i_tek,j_tek]:=False; // убираем последнюю ячейку

Init_cikl; // и начинаем сначала

end;

if kol_v_stroke[i_tek]<2 then // если зашли в тупик

begin

zapol1[i_tek,j_tek]:=False; // убираем последнюю ячейку

Init_cikl; // и начинаем сначала

end;

Until False;

// По матрице знаков находим минимальный элемент

min:=MaxInt; // заведомо большее число

for i:=1 to z do

for j:=1 to p do

if (znaki[i,j]=-1)and(x[i,j]<min) then

begin

min:=x[i,j];

i_min:=i; j_min:=j;

end;

// переходим к новому плану

zapol[i_min,j_min]:=False;

zapol[sv_i,sv_j]:=True;

for i:=1 to z do

for j:=1 to p do

x[i,j]:=x[i,j]+znaki[i,j]*min;

End;

procedure Updat;

var i,j:integer;

Begin

With Form1 do

Begin

For i:=1 to z do

for j:=1 to p do

sgOpt.Cells[j,i]:=FloatToStr(x[i,j]);

end;

End;

procedure TForm1.FormCreate(Sender: TObject);

var i,j:integer;

begin

for i:=1 to 4 do sgIsx.Cells[0,i]:=IntToStr(i);

for j:=1 to 5 do sgIsx.Cells[j,0]:=IntToStr(j);

sgIsx.Cells[1,1]:='12'; sgIsx.Cells[2,1]:='9';

sgIsx.Cells[3,1]:='10'; sgIsx.Cells[4,1]:='15';

sgIsx.Cells[1,2]:='14'; sgIsx.Cells[2,2]:='8';

sgIsx.Cells[3,2]:='13'; sgIsx.Cells[4,2]:='17';

sgIsx.Cells[1,3]:='18'; sgIsx.Cells[2,3]:='19';

sgIsx.Cells[3,3]:='20'; sgIsx.Cells[4,3]:='14';

sgIsx.Cells[1,4]:='17'; sgIsx.Cells[2,4]:='15';

sgIsx.Cells[3,4]:='18'; sgIsx.Cells[4,4]:='21';

sgZap.Cells[0,1]:='1500'; sgZap.Cells[0,2]:='500';

sgZap.Cells[0,3]:='700'; sgZap.Cells[0,4]:='900';

sgPotr.Cells[1,0]:='1000'; sgPotr.Cells[2,0]:='600';

sgPotr.Cells[3,0]:='800'; sgPotr.Cells[4,0]:='1100';

for i:=1 to 4 do sgNac.Cells[0,i]:=IntToStr(i);

for j:=1 to 5 do sgNac.Cells[j,0]:=IntToStr(j);

for i:=1 to 4 do sgOpt.Cells[0,i]:=IntToStr(i);

for j:=1 to 5 do sgOpt.Cells[j,0]:=IntToStr(j);

end;

procedure TForm1.Button1Click(Sender: TObject);

var i,j,shag:integer;

F,sum_zap,sum_potr:real;

begin

z:=4;p:=4;

zakon:=False;

For i:=1 to z do

Begin

for j:=1 to p do C[i,j]:=StrToFloat(sgIsx.Cells[j,i]);

Zapas[i]:=StrToFloat(sgZap.Cells[0,i]);

end;

For j:=1 to p do Potr[j]:=StrToFloat(sgPotr.Cells[j,0]);

sum_zap:=0;

sum_potr:=0;

For i:=1 to z do sum_zap:=sum_zap+zapas[i];

for j:=1 to p do sum_potr:=sum_potr+Potr[j];

if sum_zap<sum_potr then

Begin

z:=z+1;

for j:=1 to p do C[z,j]:=0;

zapas[z]:=sum_potr-sum_zap;

end;

if sum_zap>sum_potr then

Begin

p:=p+1;

for i:=1 to z do C[i,p]:=0;

potr[p]:=sum_zap-sum_potr;

end;

sgNac.RowCount:=z+1;

sgOpt.RowCount:=z+1;

sgNac.ColCount:=p+1;

sgOpt.ColCount:=p+1;

For i:=1 to z do

for j:=1 to p do

Begin

x[i,j]:=0;

zapol[i,j]:=False;

end;

// Начальное заполнение - метод северо-западного угла

i:=1;j:=1;

Repeat

if Zapas[i]>Potr[j] then

begin

x[i,j]:=Potr[j];

Potr[j]:=0;

Zapas[i]:=Zapas[i]-x[i,j];

end

else

begin

x[i,j]:=Zapas[i];

Zapas[i]:=0;

Potr[j]:=Potr[j]-x[i,j];

end;

Zapol[i,j]:=True;

if Potr[j]=0 then j:=j+1 // переход к след. клетке

else i:=i+1;

Until (i>z) or (j>p);

For i:=1 to z do

For j:=1 to p do sgNac.Cells[j,i]:=FloatToStr(x[i,j]);

// Основной цикл

shag:=0;

REPEAT

shag:=shag+1;

Naxod_Poten;

Naxod_delta;

Naxod_Plan;

Updat;

// найдем значение целевой функции

f:=0;

For i:=1 to z do

For j:=1 to p do

f:=f+x[i,j]*c[i,j];

if zakon then break;

label10.Caption:=FloatToStr(f);

UNTIL False;

end;

procedure TForm1.N2Click(Sender: TObject);

begin

close;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

form1.hide;

form2.show;

end;

procedure TForm1.Image1Click(Sender: TObject);

begin

form1.Close;

end;

procedure TForm1.N4Click(Sender: TObject);

begin

form3.Show;

form3.Memo1.Lines.LoadFromFile('instruct.txt');

end;

end.

unit Unit2;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, jpeg, ExtCtrls, StdCtrls;

type

TForm2 = class(TForm)

Image1: TImage;

Label1: TLabel;

Label2: TLabel;

Image2: TImage;

procedure Image2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form2: TForm2;

implementation

uses Unit1;

{$R *.dfm}

unit Unit3;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Buttons;

type

TForm3 = class(TForm)

Memo1: TMemo;

BitBtn1: TBitBtn;

procedure BitBtn1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form3: TForm3;

implementation

{$R *.dfm}

procedure TForm3.BitBtn1Click(Sender: TObject);

begin

hide;