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

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

Министерство образования Республики Беларусь

Учреждение образования "Белорусский государственный университет

информатики и радиоэлектроники"

Факультет заочного обучения

Кафедра систем телекоммуникаций

Дисциплина: Основы оптимизационных методов

Пояснительная записка

к курсовому проекту

на тему

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

Минск 2015

Содержание

Введение

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

1.1 Случаи вырождения и способы их преодоления

2. Принцип построения опорных планов

2.1 Метод северо-западного угла

2.2 Метод наименьшей стоимости

2.3 Метод Фогеля

2.4 Оптимизация задачи методом потенциалов

Заключение

Список литературы

Введение

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

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

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

При постановке задачи оптимизации необходимо:

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

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

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

4. Учет ограничений.

Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности. Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

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

Цель работы.

В городе имеется четыре АТС со свободной номерной емкостью (1,2,3,4). Известно количество свободных телефонных номеров на каждой станции. Также имеется пять районов (1,2,3,4,5), которые требуют телефонизации. Известно также расстояние от каждой АТС до центра каждого района. Нужно разделить имеющуюся телефонную емкость между районами так, чтобы расход кабеля и стоимость всей операции были минимальными. (Номера от одной АТС могут попадать в разные районы).

Определение транспортной задачи.

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

Подсчитаем суммы номерных емкостей: количество необходимых номеров: 30+25+45+30+35=165; количество свободных номеров: 25+30+40+55=150. Т.к. в нашем случае число заявок превышает количество свободных номеров, то задача является открытой. Значит, какие-то районы недополучат требуемых телефонных номеров. Чтобы сбалансировать задачу, необходимо ввести фиктивную строку с нулевыми расстояниями. Тогда задачу можно представить в виде матрицы следующего вида: сверху в строку пишем районы, которые нуждаются в телефонизации, в первый столбец пишем станции 1,2,3,4,5, в нижней строке и соответствующем столбце пишем потребность районов в телефонных номерах. В последнем столбце пишем свободную номерную емкость. Матрица имеет вид:

Таблица 1

Телефонные станции	Районы	Свободные номера
	I	II	III	IV	V
1	1	2	6	3	2	25
2	6	2	2	1	3	30
3	2	1	2	1	3	40
4	2	5	6	4	6	55
5	0	0	0	0	0
Заявки	30	25	45	30	35

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

Поставим эту задачу как задачу линейного программирования. Обозначим xij - количество номеров, отдаваемых i-й телефонной станцией j-району. Неотрицательные переменные xij тоже можно записать в виде матрицы:

x11 x12 …x1n

x21 x22 …x2n (1)

…………….

xm1 xm2 ...xmn,

которая коротко обозначается (xij). Совокупность чисел (xij) называется "планом перевозок", а сами величины xij - "перевозками". Эти неотрицательные переменные должны удовлетворять следующим условиям:

1. Суммарное количество номеров, отдаваемых каждой АТС во все районы, должно равняться количеству свободных номеров в данной АТС. Это даст нам m условий-равенств:

x11+x12+…+x1n=a1,

x21+x22+…+x2n=a2, (2)

…………………..

xm1+xm2+…+xmn=am.

2. Суммарное количество номеров, отдаваемых в каждый район от всех АТС, должно быть равно заявке, поданной данным районом. Это даст нам n условий-равенств:

x11+x12+…+x1n=b1,

x21+x22+…+x2n=b2, (3)

…………………..

xm1+xm2+…+xmn=bm.

3. суммарная стоимость всех операций, т.е. сумма величин xij, умноженных на соответствующие стоимости сij, должна быть минимальной:

S=cijxij=min, (4)

i=1 j=1

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j.

У нас задача линейного программирования с условиями-равенствами (2), (3) и минимизируемой линейной функцией (4). Все коэффициенты в условиях (2), (3) равны единице. Условия-равенства (2), (3) не являются линейно-независимыми. Число линейно-независимых среди уравнений (2), (3) равно m+n-1. Общее число переменных xij в нашей задаче равно m*n, число базисных переменных будет равно m+n-1, а число свободных переменных k=m*n-(m+n-1)=(m-1)*(n-1).

Любой план перевозок называется допустимым, если он удовлетворяет условиям (2), (3) (все заявки удовлетворены, все запасы исчерпаны). Допустимый план будет называться опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны нулю. План будет называться оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок.

1.1 Случаи вырождения и способы их преодоления

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

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

2. Принцип построения опорных планов

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

2.1 Метод северо-западного угла

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

Заполнение таблицы начинаем с северо-западного угла, т.е. с клетки с координатами 1I. первая АТС не может полностью удовлетворить потребность первого района. Вписываем значение 25 в клетку х 11=25. Остаются неудовлетворенными еще 5 заявок. Полагаем х 21=5 и исключаем из рассмотрения первый район. На АТС 2 остается измененный запас в 25 номеров, а во втором районе как раз 25 заявок. Заполняем клетку 2II и исключаем из рассмотрения второй столбец. Далее северо-западным углом будет клетка 3III. На АТС 3 свободных 40 номеров. Она может частично удовлетворить заявки третьего заказчика. Полагаем х 33=40 и вписываем это значение в клетку 3III и исключаем из рассмотрения третью строку. На АТС 4 есть 55 свободных номеров. Третьему району не хватает 5 номеров, поэтому в клетку 4III записываем это значение и исключаем из рассмотрения третий столбец. На АТС 4 есть еще 50 свободных номеров. Району IV нужно 30 номеров, поэтому полагая х 44=30, вписываем это значение в клетку 4IV. Исключаем четвертый столбец из рассмотрения. Пятому району нужно 35 номеров. Частично удовлетворяем его потребность с помощью АТС 4 и исключаем четвертый столбец из рассмотрения. Затем вводим фиктивную строку 5 с нулевыми расстояниями и для пятого района выполняем недостающие 15 заявок, помещая их в клетку с координатами 5V. Число базисных переменных должно быть n+m-1=5+5-1=9. У нас получается 8, поэтому в одну из клеток добавим 0 номеров. Например, в 1III. И тогда получается 9 базисных переменных. Таким образом, опорный план составлен. Базис образован неизвестными х 11,x13,х 21,х 22,х 33,х 43,х 44,х 45,х 55.

Таблица 2

Телефонные станции	Районы	Свободные номера
	I	II	III	IV	V
1	1 25	2	6 0	3	2	25
2	6 5	2 25	2	1	3	30
3	2	1	2 40	1	3	40
4	2	5	6 5	4 30	6 20	55
5	0	0	0	0	0 15	15
Заявки	30	25	45	30	35

Стоимость плана:

S=1*25+6*0+6*5+2*25+2*40+6*5+4*30+6*20+0*15=455

2.2 Метод наименьшей стоимости

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

В данном случае заполнение таблицы начинаем с клетки с координатами 2IV, для которой мы имеем значение стоимости С 2IV=1. Ставим в эту клетку 30 и тем самым выполняем полностью заявки четвертого района, и исключаем из рассмотрения четвертый столбец. У АТС 4 все номера использованы, поэтому эту строку мы исключаем из дальнейшего рассмотрения. Отыскиваем наименьшее расстояние в таблице, заполняем соответствующую клетку (1I,25 номеров) и исключаем из рассмотрения первую строку, т.к. на АТС 1 свободных номер больше нет. У первого района осталось не удовлетворенными 5 заявок. Отыскиваем в первом столбце наименьшее из оставшихся расстояний (клетка 4I). В первом районе все заявки выполнены, исключаем первый столбец из рассмотрения. Отыскиваем наименьшее расстояние в оставшихся клетках таблицы, заполняем соответствующую клетку (3II,25 номеров). У второго района все заявки удовлетворены, исключаем второй столбец из рассмотрения. У АТС 3 осталось еще 15 свободных номеров. Отыскиваем наименьшее расстояние в оставшихся клетках строки, заполняем соответствующую клетку (3II,15 номеров). Исключаем третью строку из рассмотрения. На АТС 4 осталось 50 свободных номеров. III району нужны еще 30 номеров, заполняем оставшуюся клетку 4III на 30 номеров и остальные 20 номеров записываем в клетке 4V. В пятом районе остались не удовлетворенными 15 заявок, которые мы присваиваем фиктивной строке в клетку 5V. Число базисных переменных должно быть 9, а у нас их 8. Поэтому в одну из клеток добавим 0 номеров, например, в 2II.

Таблица 3

Телефонные станции	Районы	Свободные номера
	I	II	III	IV	V
1	1 25	2	6	3	2	25
2	6	2 0	2	1 30	3	30
3	2	1 25	2 15	1	3	40
4	2 5	5	6 30	4	6 20	55
5	0	0	0	0	0 15
Заявки	30	25	45	30	35

Стоимость плана:

S=1*25+2*0+1*30+1*25+2*15+2*5+6*30+6*20+0*15=420

2.3 Метод Фогеля

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

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

Таблица 4

Телефон. станции	Районы	Свободн номера
	I	II	III	IV	V
1	1	2	6	3	2 25	25	1	1	1	1	-	-	-	-
2	6	2	2 25	1 5	3	30	1	1	1	1	1	1	-	-
3	2	1 25	2 5	1	3 10	40	1	1	1	1	1	1	1	2
4	2 30	5	6	4 25	6	55	2	1	2	-	-	-	-	-
5	0	0	0 15	0	0	15	0	0	0	0	0	0	0	0
Заявки	30	25	45	30	35
	1	1	0	0	0
	-	1	0	0	0
	-	-	0	0	0
	-	-	0	0	0
	-	-	0	0	0
	-	-	0	-	0
	-	-	2	-	3
	-	-	2	-	-

Алгоритм метода включает следующие основные этапы:

1. Вычисление разностей в каждой строке и в каждом столбце матрицы между наименьшим расстоянием и ближайшим к ней величиной. Разности по строкам записываются справа в столбце разностей, разности по столбцам - внизу в строке разностей. У нас для строки 4 разность равна 1I-1IV =4-2=2 и т.д.

2. Находим из всех разностей максимальную. В примере это 2 в строке 4 (если их несколько, то берем любую из них).

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

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

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

Далее за максимальную разность принимаем 1 в столбце II. В клетку 2III c наименьшим расстоянием помещаем имеющееся количество заявок 25. И исключаем второй столбец из рассмотрения. Следующая максимальная разность 2 в четвертой строке. Для четвертой телефонной станции необходимо еще 25 номеров, их мы записываем в клетку 4IV и исключаем четвертую строку из рассмотрения. Далее за максимальную разность принимаем 1 в первой строке. Т.к. первый столбец исключен из рассмотрения, записываем количество свободных номеров в пятый столбец первой строки и исключаем ее из рассмотрения. Далее за максимальную разность принимаем 1 во второй строке. В клетке 2IV, имеющей минимальное расстояние записываем 5 номеров. Заявки четвертого столбца удовлетворены, исключаем его из рассмотрения. Далее за максимальную разность принимаем опять разность во второй строке. В клетке 2III пишем 25. Во второй строке свободных номеров больше нет, исключаем ее из рассмотрения. Далее максимальная разность у нас получилась в пятом столбце - 3. В клетке 3V пишем оставшиеся 10 заявок и исключаем столбец V из рассмотрения. Далее максимальная разность получается в третьей строке, равная 2. Записываем в клетке 3III оставшиеся свободными 5 номеров. Третьему столбцу не хватает еще 15 номеров. Их мы записываем в клетку 5III. Заявки все удовлетворены, свободных номеров больше нет. Рассчитываем стоимость плана.

Стоимость плана составляет:

S=2*25+2*25+1*5+1*25+2*5+3*10+2*30+4*25+0*15=330

2.4 Оптимизация задачи методом потенциалов

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

Допустимый план перевозок тогда и только тогда является оптимальным, когда каждому пункту отправления и назначения можно сопоставить величину, характеризующую уровень оценки груза в нем (потенциал) так, что множество этих потенциалов удовлетворяет следующим условиям:

1. Разность потенциалов пунктов назначения и отправления, между которыми запланированы перевозки, равна затратам по транспортировке единицы груза между этими пунктами.

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

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

Таблица 5

Телефонные станции	Районы	Свободные номера
	I	II	III	IV	V
1	1	2	6	3	2 25	25
2	6	2	2 25	1 5	3	30
3	2	1 25	2 5	1	3 10	40
4	2 30	5	6	4 25	6	55
5	0	0	0 15	0	0	15
Заявки	30	25	45	30	35

Обозначим потенциалы пунктов отправления (АТС) как U1…U5, а потенциалы пунктов назначения (районы) как V1…V5. Изобразим стрелками направления телефонизации районов.

Исходя из того, что

Vj=Ui+Cij, Cij -

стоимость прокладки кабеля. Критерий оптимальности состоит в том, что разность потенциалов между пунктами назначения и отправления должна быть меньше стоимости перевозки: Vj-Ui-Cij0.

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

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

Пусть U3=10, тогда:

V2=U3+C32=10+1=11

V3=U3+C33=10+2=12 U2=V3-C23=12-2=10

V5=U3+C35=10+3=13 U1=V5-C15=13-2=11

V4=U2+C24=10+1=11 U4=V4-C44=11-4=7

V1=U4+C41=7+2=9 U5=V3-C53=12-0=12

Для всех пустых клеток проверим критерий оптимальности: Vj-Ui-Cij0.

X11: V1-U1-C11=9-11-1=-3

X12: V2-U1-C12=11-11-2=-2

X13: V3-U1-C13=12-11-6=-5

X14: V4-U1-C14=11-11-3=-3

X21: V1-U2-C21=9-10-6=-7

X22: V2-U2-C22=11-10-2-1

X25: V5-U2-C25=13-10-3=0

X31: V1-U3-C31=9-10-2=-3

X34: V4-U3-C34=11-10-1=0

X42:V2-U4-42=11-7-5=-1

X43: V3-U4-C43=12-7-6=-1

X45: V5-U4-C45=13-7-6=0

X51: V1-U5-C51=9-12-0=-3

X52: V2-U5-C52=11-12-0=-1

X54: V4-U5-C54=11-12-0=-1

X55: V5-U5-C55=13-12-0=1

Максимальное положительное значение получили в клетке Х 55. то говорит о том, что построенный план неоптимальный. В этом месте добавим в таблицу перевозку К. Это вызывает нарушение баланса по столбцу 5, следовательно, в нем необходимо отнять К (клетка 3V). В строке 3 прибавим К (клетка 3III). Для соблюдения баланса по третьему столбцу и строке 5 отнимем К в клетке 5III.

Таблица 6

Телефонные станции	Районы	Свободные номера
	I	II	III	IV	V
1	1	2	6	3	2 25	25
2	6	2	2 25	1 5	3	30
3	2	1 25	2 5+К	1	3 10-К	40
4	2 30	5	6	4 25	6	55
5	0	0	0 15-К	0	0 +К	15
Заявки	30	25	45	30	35

Так как все расстояния положительны, то при распределении ресурсов К выбираем равным наименьшему числу от которого отнимаем. В данном случае К=10. Новая таблица имеет вид:

Таблица 7

Телефонные станции	Районы	Свободные номера
	I	II	III	IV	V
1	1	2	6	3	2 25	25
2	6	2	2 25	1 5	3	30
3	2	1 25	2 15	1	3	40
4	2 30	5	6	4 25	6	55
5	0	0	0 5	0	0 10	15
Заявки	30	25	45	30	35

Стоимость нового плана равна:

S=2*25+2*25+1*5+1*25+2*15+2*30+4*25+0*5+0*10=320 единиц.

Для новой матрицы строим новый рисунок:



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

Пусть U3=10, тогда:

V2=U3+C32=10+1=11

V3=U3+C33=10+2=12 U2=V3-C23=12-2=10

V4=U2+C24=10+1=11 U4=V4-C44=11-4=7

V1=U4+C41=7+2=9 U5=V3-C53=12-0=12

V5=U5+C55=12+0=12 U1=V5-C15=12-2=10

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

X11: V1-U1-C11=9-10-1=-2

X12: V2-U1-C12=11-10-2=-1

X13: V3-U1-C13=12-10-6=-4

X14: V4-U1-C14=11-10-3=-2

X21: V1-U2-C21=9-10-6=-7

X22: V2-U2-C22=11-10-2=-1

X25: V5-U2-C25=12-10-3=-1

X31: V1-U3-C31=9-10-2=-3

X34: V4-U3-C34=11-10-1=0

X35: V5-U3-C35=12-10-3=-1

X42:V2-U4-42=11-7-5=-1

X43: V3-U4-C43=12-7-6=-1

X45: V5-U4-C45=12-7-6=-1

X51: V1-U5-C51=9-12-0=-3

X52: V2-U5-C52=11-12-0=-1

X54: V4-U5-C54=11-12-0=-1

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

Ввести m,n

Задать начальные значения элементам

Xij, Cij, Ai, Bj, Ui, Vj

Вычислить базисное допустимое решение

Вычислить коэффициенты Ui и Vj для Перейти к базисному

Базисного допустимого решения допустимому решению

Найти Cij для небазисных переменных

Проверка

условия Cij>0

Получение оптимального плана

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

procedure vvod_dan; (ввод данных с клавиатуры)

begin

i:=1;

k:=0;

s1:=0;

while (k=0) and (i<n) do

begin

write('введите запaсы ',i,'-того поставщика: ');

readln(a[i]);

if a[i]=0 then

begin

k:=1;

i:=i-1;

end

else

begin

a1[i]:=a[i];

s1:=s1+a1[i];

i:=i+1;

end;

end;

j:=1;

k:=0;

s2:=0;

textcolor(5);

while (k=0) and (j<m) do

begin

write('введите запрос ',j,'-того потребителя: ');

readln(b[j]);

if b[j]=0 then

begin

k:=1;

j:=j-1;

end

else

begin

b1[j]:=b[j];

s2:=s2+b1[j];

j:=j+1;

end;

end;

textcolor(yellow);

k:=0;

if s1<s2 then

begin

writeln('ошибка ввода, проверьте баланс');

readln;

halt;

end;

if (s2<s1) and (k=0) then

begin

writeln('ошибка ввода, проверьте баланс');

readln;

halt; end;

x:=i;

y:=j;

end;

Заключение

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

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

Список литературы

1. Методические указания к лабораторным работам по курсу "Основы оптимизационных методов в СТК". О.А. Хацкевич - Мн.: БГУИР, 2006.

2. Методические указания по контрольной работе по курсу "КТ в СТК" на тему "Транспортная задача линейного программирования". О.А. Хацкевич - Мн.: БГУИР, 2007.

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