Оптимизация плана перевозок распределительным методом

Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Теоретическая часть
• 1.1 Сущность транспортной задачи
• 1.2 Теоретическая суть метода потенциалов
• 1.2.1 Алгоритм метода потенциалов
• 2. Разработка программы
• 2.1 Практическая цель работы
• 2.2 Обоснование выбора языка программирования
• 2.3 Требования к системе
• 2.3.1 Системные требования
• 2.3.2 Интерфейс программы
• 2.3.3 Описание входных данных
• 2.4 Основные процедуры и функции программы
• 2.5 Блок-схема
• 2.6 Инструкция пользователю
• Заключение
• Список литературы
• Приложение А. Листинг программы
• Приложение Б. Блок-схемы
• Введение
• Люди издавна сталкивались с проблемой ограниченности ресурсов. Поэтому нужно было максимально эффективно использовать средства. Тем не менее, эта проблема делает жизнь более интересной. Для ее решения людям требовалось создать некий план. До 20-го века план создавался приблизительно, затем же появился раздел математики - математическое программирование, разработанный для точного планирования.
• Задачи мат. программирования очень трудоёмки по своей реализации, поэтому в большинстве случаев требуется применение ЭВМ. При этом для решения необходимо создать программу.
• История возникновения линейного программирования берёт своё начало с публикации работы Л.В. Канторовича под названием "Математические методы организации и планирования производства ". В ней были сформированы задачи с ограничениями и описан метод их решения. Именно это и легло в основу линейного программирования.
• Термин "Программирование" был сформулирован в 1940-х годах американским математиком Д. Данцигом, разработчиком симплекс-метода.
• Линейное программирование изучает материальные, информационные потоки, которые сопутствуют производственной деятельности.
• Методы решения транспортных задач позволяют найти базовое решение и затем получить наиболее эффективное решение.
• Цель транспортных перевозок осуществима посредством выполнения следующих положений: товар доставлен в оговоренное время и место, затраты на доставку минимальны, товар качественный и нужный.
• Транспортная задача позволяет распределить перевозки продукта покупателю с минимальными издержками и своевременно.
• Понятие "Транспортная задача" включает в себя различные задачи с одной и той же математической моделью. Транспортная задача - задача об экономном планировании перевозок однообразных или взаимозаменяемых продуктов из точки производства в точку сбыта.
• Классическую транспортную задачу чаще всего можно встретить в приложениях линейного программирования.
• Линейное программирование - один из разделов мат. планирования (раздел математики, который разрабатывает методы, способы и теорию решения многомерных задач с ограничениями).
• В настоящее время транспортная задача широко распространена в области применения в промышленности и на транспорте. Она имеет решающее значение в оптимизации планирования работы разнообразных видов транспорта и грузопотоков, а также рационализации поставок разновидностей сельскохозяйственной и промышленной продуктов.
• Транспортные задачи появляются в том случае, если ресурсов, имеющихся в наличии недостаточно для эффективного выполнения работы. Данная задача ориентирована на отыскание распределения ресурсов по работам, таким образом, при котором максимизируется конечный доход или минимизируются издержки производства.
• Множество различных видов перевозок усложняет нахождение экономного плана опытным или экспертным путем. Поэтому для достижения наибольшего экономического эффекта в планировании перевозок применяются вычислительные и математические методы. Существует множество способов решения транспортной задачи, наиболее известными из которых являются распределительный метод и метод потенциалов.
• При оптимизации данными методами следует сначала построить опорный план. Целью курсовой работы является создание оптимального плана перевозок методом потенциалов.
• Основные задачи курсовой работы: построение математической модели и создание алгоритма решения задачи, создание программы на языке Pascal для нахождения оптимального плана перевозок.
• Результатом выполнения курсовой работы будет программа для решения транспортной задачи методом потенциалов.
• 1. Теоретическая часть
• 1.1 Сущность транспортной задачи
• Классическая транспортная задача ЛП формулируется следующимобразом.
• Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины:
• - объем производства (запас) i-го поставщика, i=1, m ;
• - объем потребления (спрос) j-го потребителя, i=1, n ;
• - стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.
• Требуется составить такой план перевозок, при котором спросвсех потребителей был бы выполнен и при этом общая стоимость всехперевозок была бы минимальна.
• Математическая модель транспортной задачи.
• Переменными (неизвестными) транспортной задачи являются xij, i=1,2,...,m j=1,2,...,n - объемы перевозок от i-го поставщика каждому j-му потребителю.
• Эти переменные могут быть записаны в виде матрицы перевозок.
• (1)
• Так как произведение Cij*Xijопределяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:
• (2)
• По условию задачи требуется обеспечить минимум суммарных затрат.
• Следовательно, целевая функция задачи имеет вид:
• (3)
• Система ограничений задачи состоит из двух групп уравнений.
• Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:
• (4)
• Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:
• (5)
• В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.:
• (6)
• Такая задача называется задачей с правильным балансом, а модель задачизакрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи - открытой.
• Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие Уai=Уbj называется открытой. Для открытой модели может быть два случая:
• a) суммарные запасы превышают суммарные потребности Уai>Уbj
• b) суммарные потребности превышают суммарные запасы Уai<Уbj
• Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
• Нахождение минимального значения линейной функции:
• Z = Уcijxij(7)
• при ограничениях
• Уxij? ai, i = 1, 2, ..., m,(8)
• Уxij=bj, j = 1, 2, ..., n;
• Уxij=ai, i = 1, 2, ..., m, (9)
• Уxij? bj j = 1, 2, ..., n,
• Открытая модель решается приведением к закрытой модели.
• В случае (8), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого
• bn+1 =Уai-Уbj
• В случае (9), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого
• am+1 =Уbj-Уai .
• Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
• После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных
• 1.2 Теоретическая суть метода потенциалов
• транспорт грузоперевозка алгоритм pascal
• Метод потенциалов - наиболее точный метод решения транспортной задачи. Он был предложен в 1949г. М.К. Гавуриным и Л.В. Канторовичем. Этот метод является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Не смотря на это, он изложен таким образом, что не имеет связи с общими методами линейного программирования. Аналогичный алгоритм был разработан Данцигом. Метод потенциалов за рубежом называют модифицированный распределительный метод.
• Метод потенциалов позволяет с помощью базисного плана перевозок найти решение транспортной задачи за некоторое число итераций (этапов, шагов).
• Каждая итерация состоит в том, что каждому поставщику и потребителю присваивается показатель - его предварительный потенциал. Потенциалы распределяются таким образом, что
• ui+vj = Cij,(10)
• где ui - потенциал строки (поставщика) Ai,vj - потенциал столбца(потребителя) Bj.
• Если разность потенциалов для каждой клетки AiBj меньше или равна Cij, то этот такой план перевозок является решением задача, а потенциалы являются потенциалами задачи. Если существует AiBj, для которой разность потенциалов больше Cij, то находится план с меньшими транспортными издержками. Таким образом, через некоторое количество итераций строится оптимальный план.
• i,j- предварительный потенциал.
• План обладающий свойством i,j= сi,j (для всех базисных клеток) и i,j сi,j (для всех незаполненных клеток) называется потенциальным планом, а соответствующие ему платежи (uiи vj) - потенциалами пунктов Ai и Bj. Таким образом, любой потенциальный план является оптимальным. Для решения транспортной задачи методом потенциалов нужно построить потенциальный план.
• В транспортной задаче обозначим цикл (контур) как некоторые заполненные клетки, которые при соединении ломаной линией образуют прямоугольник.
• Циклы могут быть различными, они представлены на рисунке 1.
• Рисунок 1 - Разновидности циклов
• Все циклы имеют чётное количество вершин и чётное количество звеньев. В клетках, где потребуется уменьшить количество перевозок будем ставить в верхнем правом углу знак "-", а в клетках, где увеличить, ставится знак "+". Цикл, в котором расставлены знаки, называется означенным. Перенос перевозок означает уменьшение перевозок в отрицательных клетках и увеличение на такое же количество перевозок в положительных клетках.
• Сумма перевозок в столбцах равна спросу потребителей, сумма в строках равна запасам поставщика.
• План можно построить методом последовательных приближений, задаваясь произвольной системой платежей, удовлетворяющей условию i,j= сi,j. В каждой базисной клетке будет сумма платежей, равная стоимости перевозок в этой ячейке. При улучшении плана меняют систему платежей так, что они приближаются к потенциалам. При улучшении опорного плана следует руководствоваться одним из свойств стоимостей и потенциалов: для каждой свободной клетки цена цикла равна разности между стоимостью и потенциалом в данной клетке, т.е.
• i,j=сi,j - i,j.
• Основным достоинством метода потенциалов перед распределительным методом является то, что не нужно искать циклы с отрицательной ценой
• 1.2.1 Алгоритм метода потенциалов
• Стоимость доставки единицы груза от поставщиков к потребителям задана матрицей тарифов (таблица 1).
• Таблица 1 - Матрица тарифов

	B1 30	B2 30	B310	B420
A1 50	1	2	4	1
A2 30	2	3	1	5
A3 10	3	2	4	4

• Проверим необходимое и достаточное условие разрешимости задачи.
• ?a = 50 + 30 + 10 = 90;
• ?b = 30 + 30 + 10 + 20 = 90.
• Запасы равны потребностям, следовательно, условие баланса соблюдается.

Нахождение опорного плана, например методом минимального элемента

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

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

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

Шаг описан в таблице 2.

Таблица 2 - Построение опорного плана методом минимального элемента.

	B130	B230	B310	B420
А 150	201	30 2	4	1
А 230	102	3	101	10 5
А 310	3	2	4	10 4

Опорный план является допустимым, соблюден баланс между спросом потребителя и предложением поставщика.

В этом плане

m + n- 1 = 6

заполненных клеток (m-- число строк,n - число столбцов транспортной таблицы). Опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 1*20 + 2*30 + 2*10 + 1*10 + 5*10 + 4*10 = 200

Для этого плана можно определить потенциалы строк и столбцов (iи j), так, чтобы в каждой базисной клетке выполнялось условие (10)

Данное условие выполняется всего m + n - 1, а количество неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n- 1 уравнений можно найти остальные платежи i, j, а по ним вычислить потенциалы:

i,j=i+ j

для каждой свободной клетки.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi, по базисным клеткам таблицы, в которых ui + vi = cij, принимая u1 = 0.

u1 + v1 = 1; 0 + v1 = 1; v1 = 1

u2 + v1 = 2; 1 + u2 = 2; u2 = 1

u2 + v3 = 1; 1 + v3 = 1; v3 = 0

u2 + v4 = 5; 1 + v4 = 5; v4 = 4

u3 + v4 = 4; 4 + u3 = 4; u3 = 0

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

Заносим полученные данные в таблицу 3.

Таблица 3 - Нахождение предварительных потенциалов

	B1 30	B230	B3 10	B420	uj
А 1 50	201	30 2	4	1	u1 = 0
А 230	10 2	3	101	105	u2 = 1
А 310	3	2	4	104	u3 = 0
vi	v1 = 1	v2 = 2	v3 = 0	v4 = 4

Опорный план не является оптимальным, так как существуют оценки небазисных клеток, для которых ij> cij

Такой клеткой является A1B4. Сумма предварительных потенциалов для неё равна

u1 + v4 =14=4 > 1;

От этой клетки, аналогично распределительному методу, строим прямоугольный цикл. Каждому из этих значений в цикле, начиная с пустой клетки, ставим знак "+" или "-" по очереди. Суммируем или вычитаем их во всем цикле в зависимости от знака.

В свободную клетку А 1B4 таблицы ставим знак "+", а в остальные поочередно знаки "-", "+", "-". Цикл - прямоугольник, состоящий из вершин А 1B4;A1B1;A2B1;A2B4.

Шаг описан в таблице 4.

Таблица 4 - Нахождение цикла перемещения

	B1 30	B230	B3 10	B420	uj
А 1 50	201[-]	30 2	4	1[+]	u1 = 0
А 230	10 2[+]	3	101	105[-]	u2 = 1
А 310	3	2	4	104	u3 = 0
vi	v1 = 1	v2 = 2	v3 = 0	v4 = 4

Цикл представляет собой прямоугольник с вершинами (A1B4; A1B2; A2B2; A2B4).

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

Шаг описан в таблице 5.

Таблица 5 - Построение нового базисного плана

	B1 30	B230	B3 10	B420
А 1 50	101	302	4	10 1
А 230	202	3	101	5
А 310	3	2	4	104

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi, по базисным клеткам таблицы, в которых ui + vi = cij, принимая u1 = 0.

u1 + v1 = 1; 0 + v1 = 1; v1 = 1

u2 + v1 = 2; 1 + u2 = 2; u2 = 1

u2 + v3 = 1; 1 + v3 = 1; v3 = 0

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u1 + v4 = 1; 0 + v4 = 1; v4 = 1

u3 + v4 = 4; 1 + u3 = 4; u3 = 3

Заносим данные в таблицу 6.

Таблица 6 - Нахождение потенциалов для нового опорного плана

	B1 30	B230	B3 10	B420	uj
А 1 50	101	30 2	4	10 1	u1 = 0
А 230	20 2	3	101	5	u2 = 1
А 310	3	2	4	104	u3 = 3
vi	v1 = 1	v2 = 2	v3 = 0	v4 = 1

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

ui + vi > cij

Такими клетками являются A3B1, A3B2. Сумма предварительных потенциалов для них равна:

u3 + v1 = 31 = 3 + 1, стоимость c31 =4 > 3;

u3 + v2 = 32 = 3 + 2, стоимость c32 =5 > 2.

Выбираем клетку с наибольшей разностьюij - cij. Такой клеткой является A3B2.

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

Шаг описан в таблице 7.

Таблица 7 - Отыскание контура перемещения

	B1 30	B230	B3 10	B420	uj
А 1 50	101	30 2[-]	4	10 1[+]	u1 = 0
А 230	20 2	3	101	5	u2 = 1
А 310	3	2[+]	4	104[-]	u3 = 3
vi	v1 = 1	v2 = 2	v3 = 0	v4 = 1

Цикл представляет собой прямоугольник с вершинами (A3B2; A1B2; A1B4; A3B4).

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

Шаг описан в таблице 8.

Таблица 8 - Построение третьего опорного плана

	B1 30	B230	B3 10	B420
А 1 50	101	202	4	20 1
А 230	202	203	101	5
А 310	3	102	4	4

u1 + v1 = 1; 0 + v1 = 1; v1 = 1

u2 + v1 = 2; 1 + u2 = 2; u2 = 1

u2 + v3 = 1; 1 + v3 = 1; v3 = 0

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u3 + v2 = 2; 2 + u3 = 2; u3 = 0

u1 + v4 = 1; 0 + v4 = 1; v4 = 1

В таблице 9 описан оптимальный план задачи.

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

	B1 30	B230	B3 10	B420	uj
А 1 50	301	2	4	20 1	u1 = 0
А 230	2	20 3	101	5	u2 = 1
А 310	3	10 2	4	4	u3 = 0
vi	v1 = 1	v2 = 2	v3 = 0	v4 = 1

Опорный план является оптимальным, так как существуют оценки свободных клеток, для которых

ui + vi > cij.

Минимальные затраты составят:

F(x) = 1*30 + 1*20 + 3*20 + 1*10 + 2*10 = 140

2. Разработка программы

2.1 Практическая цель работы

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

2.2 Обоснование выбора языка программирования

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

Язык программирования Pascal (назван в честь выдающегося французского математика и философа Блеза Паскаля (1623 - 1662)), разработан в 1967 - 1971гг. Никлаусом Виртом, профессором, директором института информатики Швейцарской высшей политехнической школы. Язык Pascal, созданный первоначально для обучения программированию как систематической дисциплине, скоро стал широко использован для разработки программных средств в профессиональном программировании.

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

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

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

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

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

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

2.3 Требования к системе

2.3.1 Системные требования

Минимальные системные требования:

- IBM PC совместимый персональный компьютер

- Pentium 100 или выше,

- 16 Мб Оперативной памяти (рекомендуется 32 Мб),

- 64 МБ свободного пространства на жестком диске,

- 16-битная Windows-совместимая звуковая плата,

- мышь, клавиатура, колонки или наушники.

2.3.2 Интерфейс программы

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

2.3.3 Описание входных данных

Для создания оптимального плана методом потенциалов в программу вводятся следующие данные:

- Количество потребителей;

- Количество поставщиков;

- Количество запасов;

- Стоимость перевозок.

2.4 Основные процедуры и функции программы

Procedure Nul - обнуление массива данных;

Procedure PrintS - вывод строки S;

Procedure Print - вывод числа А;

Procedure Rid - процедура ввода числа X;

Procedure Goriz, Wertic -вывод распределительной таблицы на экран;

Procedure Tabl - расстановка знаки "+" и "-" в контуре перемещения и вывод таблицы;

Procedure W_W - ввод в таблицу количества продукции поставщика и потребителя;

Function FF - вычисление стоимости плана;

Function A_B - вычисление потенциалов ui и vj;

Procedure W_p - вывод плана распределения;

Function kkk - расчёт коэффициентов в свободных клетках;

Procedure div_mod - перевод одномерного массива в двумерный;

Procedure Rek - рекурсивная процедура;

Procedure kontur - нахождение контура перемещения;

Procedure Pauza - программа завершает свою работу при нажатии любой клавиши.

2.5 Блок - схема

Блок схема работы программы представлена на рисунке 3

Рисунок 3 - Блок-схема программы

2.6 Инструкция пользователю

Для эксплуатации программы требуется запустить её файл с расширением.pas, который называется Potential.pas. Это действие описано на рисунке 4.

Рисунок 4 - Запуск файла программы

После запуска данного файла на экране появится окно конструктора программы TurboPascalс кодом программы. Это показано на рисунке 5.

Рисунок 5 - Окно TurboPascal

Для запуска программы необходимо зажать комбинацию клавиш Ctrl +F9. Затем на экране появится окно компилятора, запрашивающее ввод количества поставщиков и потребителей. Ввод значений подтверждается нажатием клавиши Enter.Изображение представлено на рисунке 6.



Рисунок 6 - Запрос количества поставщиков и потребителей

После этого на экран выводится таблица заданной размерности и предложение ввести количество запасов и стоимости перевозок (рисунок 7).

Рисунок 7 - Заполнение распределительной таблицы

После этого при нажатии клавиши Enterбудет построен опорный план методом минимального элемента, а также указан тип задачи(открытая или закрытая).Процесс описан на рисунке 8.

Рисунок 8 - Опорный план методом минимального элемента

Затем находится контур перемещения и происходит расстановка знаков в нем. Происходит перераспределение ресурсов до тех пор, пока не будет найдено оптимальное решение, представленное на рисунке 9.

Рисунок 9 - Оптимальное решение

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

Заключение

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

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

Решение является адекватным, может использоваться для решения практических задач.

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

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

Приложение А. Листинг программы

Uses Crt;

Label l1;

Const N=6;

n1=7; n2=7;

Sa:longint=0;

Sb:longint=0;

Type predpr=Array [1..N] of longint;

rasp=Array [1..N,1..N] of longint;

Var A,B,v,u,B_d,x:predpr;

c,p:rasp;

f,f0,x_min,Sp:longint;

Nt,x_p,r,r_min,ki,kj,Na,Nb,h,l,i,j:byte;

d:char;

z:Array[1..N*N] of byte;

Procedure Nul (var a:predpr); {Obnuliaet massiv}

var i:byte;

Begin

for i:=1 to N do a[i]:=0;

End;

Procedure PrintS (x,y:byte; s:string; c:byte);

Begin {vivod stroki s}

TextColor(c);

GotoXY(x,y);

Write(s);

End;

Procedure Print (x,y:byte; n:byte; a:longint; c:byte);

Begin {vivod chisla a}

TextColor(c);

GotoXY(x,y); Write(' ':n);

GotoXY(x,y); Write(a);

End;

Procedure Rid (var x:longint; y:byte); {procedura vvoda chisla x}

var i:integer;

s:string;

c:char;

j,k:byte;

Begin

s:=''; i:=1;

TextColor(11);

Repeat

c:=ReadKey;

Case ord(c) of

48..57: begin s:=s+c;

Write(c);

inc(i);

end;

8: if i>1 then begin dec(i);

Delete(s,i,1);

Write(chr(8),' ',chr(8));

end;

end;

j:=WhereX;

GotoXY(60,1); ClrEOL;

if i>y then begin

TextColor(4);

Write('ne bolee ');

for k:=1 to y-1 do Write('9');

TextColor(11);

end;

GotoXY(j,1);

Until (ord(c)=13) and (i<y+1);

val(s,x,i);

End;

Procedure goriz (a,b,c,d,e:char); {proceduri goriz, wertic}

var i,j:byte; {i Tabl vivodiat tablicy}

Begin

Write(a);

for i:=1 to n2 do Write(b);

Write(c);

for i:=1 to Nb do begin

for j:=1 to n1 do Write(b);

if i<>Nb then Write(d) else Write(c);

end;

for i:=1 to 4 do Write(b);

Write(e);

End;

Procedure wertic;

var i:byte;

Begin

Write('¦',' ':n2,'¦');

for i:=1 to Nb-1 do Write(' ':n1,'¦');

WriteLn(' ':n1,'¦',' ' :4,'¦');

End;

Procedure Tabl;

Begin

ClrScr;

TextColor(1);

h:=6+Na*3;

l:=14+Nb*7;

GotoXY(1,3);

for i:=3 to h do wertic;

GotoXY(1,2);

goriz('+','-','-','-','+');

for i:=1 to Na+1 do begin

GotoXY(1,i*3+2);

if (i=1) or (i=Na+1)

then goriz(':','-','+','+',':')

else goriz('+','-','+','+',':');

end;

GotoXY(1,h+1);

goriz('+','-','-','-','+');

TextColor(9);

for i:=1 to Na do begin

GotoXY(5,i*3+3);

Write('A',i);

end;

for i:=1 to Nb do begin

GotoXY(i*(n1+1)+n2-2,3);

Write('B',i);

end;

l:=Nb*(n1+1)+n2+3;

h:=Na*3+6;

PrintS(4,3,'\Bj',9);

PrintS(4,4,'Ai\',9);

PrintS(1,1,''Tablica N1',14);

PrintS(l,4,'v',9);

PrintS(3,h,'u',9);

End;

Procedure W_W (var a:predpr; b:byte; c:char); {vvod v tablicy}

var i,l,m:byte; {kol-va prodykcii}

Begin {postavshika i potreb.}

for i:=1 to b do begin

TextColor(3);

GotoXY(32,1);

ClrEOL;

Write(c,i,'= ');

Rid(a[i],n1);

TextColor(14);

Case c of

'A': GotoXY(n2-trunc(ln(a[i])/ln(10)),i*3+4);

'B': GotoXY(n2+i*(n1+1)-trunc(ln(a[i])/ln(10)),4);

end;

Write(a[i]);

end;

End;

Function FF:longint; {vichislenie stoimosti plana }

var i,j:byte;

f:longint;

Begin

f:=0;

for i:=1 to Na do

for j:=1 to Nb do

if p[i,j]>0 then inc(f,c[i,j]*p[i,j]);

GotoXY(65,Nt+2);

TextColor(10);

Write('F',Nt,'=',f);

FF:=f;

End;

Function a_b:boolean; {raschet potencialov}

var k,i,j:byte; {Ui i Vj}

Z_a,Z_b:predpr;

d:boolean;

Begin

Nul(Z_a); Nul(Z_b);

v[1]:=0; Z_a[1]:=1; k:=1;

Repeat

d:=1=1;

for i:=1 to Na do

if Z_a[i]=1 then

for j:=1 to Nb do

if (p[i,j]>-1) and (Z_b[j]=0) then begin

Z_b[j]:=1;

u[j]:=c[i,j]-v[i];

inc(k);

d:=1=2;

end;

for i:=1 to Nb do

if Z_b[i]=1 then

for j:=1 to Na do

if (p[j,i]>-1) and (Z_a[j]=0) then begin

Z_a[j]:=1;

v[j]:=c[j,i]-u[i];

inc(k);

d:=1=2;

end;

Until (k=Na+Nb) or d;

if d then begin

i:=1;

While Z_a[i]=1 do inc(i);

j:=1;

While Z_b[j]=0 do inc(j);

p[i,j]:=0;

Print((j+1)*(n1+1)+n2-8,i*3+4,1,p[i,j],7);

end;

a_b:=d;

End;

Procedure W_p; {Vivod plana raspredeleniya}

var i,j,h,l,k:byte;

c_max:longint;

Begin

k:=0;

for i:=1 to Na do begin

h:=i*3+4;

for j:=1 to Nb do begin

l:=j*(n1+1)+n2-5;

GotoXY(l,h);

Write(' ':n1);

if p[i,j]>0 then begin

inc(k);

Print(l-trunc(ln(p[i,j])/ln(10))+5,h,1,p[i,j],14);

end

else if p[i,j]=0 then begin

Print(l+n1-2,h,1,p[i,j],14);

inc(k);

end;

end;

end;

While a_b do inc(k);

if k>Na+Nb-1 then PrintS(40,1,'k > n+m-1',12);

End;

Function kkk(var ki,kj:byte):integer; {raschet koeff}

var i,j:byte; {v svobodnih kletkah}

k,k_min:integer;

b:boolean;

Begin

b:=1=1;

for i:=1 to Na do

for j:=1 to Nb do

if p[i,j]=-1 then begin

k:=c[i,j]-v[i]-u[j];

if b then begin

b:=1=2;

ki:=i; kj:=j; k_min:=k;

end else

if k<k_min then begin

k_min:=k;

ki:=i; kj:=j;

end;

TextColor(6);

GotoXY(j*(n1+1)+n2-5,i*3+4);

Write('(',k,')');

end;

if k_min<0 then PrintS(kj*(n1+1)+n2,ki*3+4,'X',12);

kkk:=k_min;

End;

Procedure div_mod(c:byte; var a,b:byte); {perevod}

Begin {odnomernogo massiva }

b:=c mod Nb; a:=c div Nb +1; {v dvumernii}

if b=0 then begin

b:=Nb; dec(a);

end;

End;

Procedure Rek(Xi,Yi:byte; var z:boolean; var c:byte);

var i,j:byte;

Begin {rekursivnaya procedura .}

z:=1=2; {nahojdenie kontura}

Case c of

1: for i:=1 to Na do

if i<>Xi then

if p[i,Yi]>-1 then begin

if u[(i-1)*Nb+Yi]=0 then begin

u[(Xi-1)*Nb+Yi]:=(i-1)*Nb+Yi;

c:=2;

Rek(i,Yi,z,c);

if z then exit;

end;

end

else if (i=ki) and (Yi=kj) then begin

u[(Xi-1)*Nb+Yi]:=(ki-1)*Nb+kj;

z:=not z;

exit;

end;

2: for i:=1 to Nb do

if i<>Yi then

if p[Xi,i]>-1 then begin

if u[(Xi-1)*Nb+i]=0 then begin

u[(Xi-1)*Nb+Yi]:=(Xi-1)*Nb+i;

c:=1;

Rek(Xi,i,z,c);

if z then exit;

end;

end

else if (Xi=ki) and (i=kj) then begin

u[(Xi-1)*Nb+Yi]:=(ki-1)*Nb+kj;

z:=not z;

exit;

end;

end;

u[(Xi-1)*Nb+Yi]:=0;

c:=c mod 2 +1;

End;

Procedure kontur; {nahojdenie kontura peremesheniya}

var i,j,k,mi,mj,l:byte;

z:boolean;

p_m:longint;

Begin

for i:=1 to N*N do u[i]:=0;

l:=1;

Rek(ki,kj,z,l);

i:=ki; j:=kj;

k:=u[(i-1)*Nb+j];

div_mod(k,i,j);

mi:=i; mj:=j; l:=1;

Repeat

inc(l);

k:=u[(i-1)*Nb+j];

div_mod(k,i,j);

if l mod 2=1 then

if p[i,j]<p[mi,mj] then begin

mi:=i; mj:=j;

end;

Until (i=ki) and (j=kj);

i:=ki; j:=kj; l:=0;

p_m:=p[mi,mj];

Repeat

if l mod 2=0 then begin

inc(p[i,j],p_m);

PrintS((n1+1)*j+n2-1,i*3+3,'(+)',12);

end else begin

dec(p[i,j],p_m);

PrintS((n1+1)*j+n2-1,i*3+3,'(-)',12);

end;

if l=0 then inc(p[i,j]);

k:=u[(i-1)*Nb+j];

div_mod(k,i,j);

inc(l);

Until (i=ki) and (j=kj);

p[mi,mj]:=-1;

End;

Procedure Pauza;

var d:char;

Begin

TextColor(6);

GotoXY(40,1);

Write('Press any Key');

d:=ReadKey;

GotoXY(40,1);

ClrEOL;

End;

BEGIN

Nul(v); Nul(u);

Nt:=1;

ClrScr;

TextColor(10);

Repeat

Write('vvedite kol-vo postavshikov (2<=Na<=',N-1,') ');

ReadLn(Na);

Write('vvedite kol-vo potrebitelei (2<=Nb<=',N-1,') ');

ReadLn(Nb);

Until (Na>1) and (Na<=N-1) and (Nb>1) and (Nb<=N-1);

Tabl;

(******************* vvod nachalnix dannix ******************)

PrintS(1,1,'vvedite kol-vo prodykcii:',3);

W_W(A,Na,'A');

W_W(B,Nb,'B');

TextColor(3);

GotoXY(1,1); ClrEOL;

Write('vvedite stoimost perevozki');

for i:=1 to Na do

for j:=1 to Nb do begin

TextColor(3);

GotoXY(29,1); ClrEOL;

Write('A',i,' - B',j,' ');

Rid(c[i,j],5);

Print((n1+1)*j+n2-4,i*3+3,1,c[i,j],11);

end;

(**********************************************************)

GotoXY(1,1);

ClrEOL;

TextColor(14);

Write('Tabl N1');

for i:=1 to Na do Sa:=Sa+A[i];

for i:=1 to Nb do Sb:=Sb+B[i];

if Sa<>Sb then begin {esli zadacha otkritaya}

PrintS(20,1,'Otkritaya zadacha(Press Any Key)',7);

d:=ReadKey;

if Sa>Sb then begin

inc(Nb);

B[Nb]:=Sa-Sb;

for i:=1 to Na do c[i,Nb]:=0;

end else begin

inc(Na);

A[Na]:=Sb-Sa;

for i:=1 to Nb do c[Na,i]:=0;

end;

Tabl;

for i:=1 to Na do

for j:=1 to Nb do Print((n1+1)*j+n2-4,i*3+3,1,c[i,j],11);

for i:=1 to Na do

Print(n2-trunc(ln(A[i])/ln(10)),i*3+4,1,A[i],14);

for i:=1 to Nb do

Print(n2+i*(n1+1)-trunc(ln(B[i])/ln(10)),4,1,B[i],14);

PrintS(20,1,'Otkritaya zadacha',7);

end

else PrintS(20,1,'Zakritaya zadacha',7);

(************** sostavlenie opornogo plana ­ ****************)

for i:=1 to Nb do B_d[i]:=B[i];

for i:=1 to Na do begin

for j:=1 to Nb do x[j]:=j;

for j:=1 to Nb-1 do begin

x_min:=c[i,x[j]];

r_min:=j;

for r:= j+1 to Nb do

if (x_min>c[i,x[r]]) or

((x_min=c[i,x[r]]) and (B[x[r]]>b[x[r_min]])) then

begin

x_min :=c[i,x[r]];

r_min:=r;

end;

x_p:=x[r_min];

x[r_min]:=x[j];

x[j]:=x_p;

end;

Sp:=0;

for j:=1 to Nb do begin

p[i,x[j]]:=B_d[x[j]];

if p[i,x[j]]>A[i]-Sp then p[i,x[j]]:=A[i]-Sp;

inc(Sp,p[i,x[j]]);

dec(B_d[x[j]],p[i,x[j]]);

end;

end;

Приложение Б. Блок-схемы

РисунокБ-1 - ПроцедураNul

РисунокБ-2 - ПроцедураPrintS

РисунокБ-3 - ПроцедураPrint



РисунокБ-4 - ПроцедураRid



РисунокБ-5 - ПроцедураGoriz

РисунокБ-6 -ПроцедураWertic



РисунокБ-7 - ПроцедураTabl



РисунокБ-8 - ПроцедураW_W

РисунокБ-9 - ФункцияF_F

Размещено на Allbest.ru

...