СОДЕРЖАНИЕ
ВВЕДЕНИЕ 5
1. ОБЩАЯ ЧАСТЬ 8
1.1 Математическая постановка задачи 8
1.2 Алгоритм решения задачи 11
1.3 Блок-схема (алгоритм решения) 25
2. Формы входной информации 27
3. Формы выходной информации 28
4. Инструкция для пользователя 29
5. Инструкция для программиста 30
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 34
ПРИЛОЖЕНИЕ А 35
ВВЕДЕНИЕ
Математика необходима вповседневной жизни, следовательно определенные математические навыки нужныкаждому человеку. Нам приходится в жизни считать(например, деньги), мыпостоянно используем(часто не замечая этого) знания о величинах, характеризующихпротяженности, площади, объемы, промежутки времени, скорости и многое другое.Все это пришло к нам на уроках арифметики и геометрии и пригодилось дляориентации в окружающем мире.
Математические знания инавыки нужны практически во всех профессиях, прежде всего, конечно, в тех, чтосвязаны с естественными науками, техникой и экономикой. Математика являетсяязыком естествознания и техники и потому профессия естествоиспытателя иинженера требует серьезного овладения многими профессиональными сведениями,основанными на математике.
Хорошо сказал об этомГалилей:
«Философия (на нашемязыке- физика) написана в величайшей книге, которая постоянно открыта вашемувзору, но понять ее может лишь тот, кто сначала научится понимать ее язык и толковатьзнаки, которыми она написана. Написана же она на языке математики».
Сегодня несомненнанеобходимость применения математических знаний и математического мышленияврачу, лингвисту, историку, и людям других специальностей. Но особенно знаниематематики необходимы людям точных профессий — финансистам, экономистам.
Профессиональный уровеньэкономиста во многом зависит от того, освоил ли он современный математическийаппарат и умеет ли использовать его при анализе сложных экономических процессови принятий решений. Поэтому в подготовке экономистов широкого профиля изученияматематики занимает значительное место. Математическая подготовка экономистаимеет свои особенности, связанные со спецификой экономических задач, а также сшироким разнообразием подходов к их решению.
Задачи практической итеоретической экономики очень разносторонни. К ним относятся, в первую очередь,методы сбора и обработки статической информации, а также оценка состояния иперспективы развития экономических процессов. Применяются различные способыиспользования полученной информации — от простого логического анализа досоставления сложных экономико-математических моделей и разработкиматематического аппарата их исследования.
Неопределенностьэкономических процессов, значительный случайный разброс и большой объемполучаемой информации обуславливают необходимость привлечения к исследованиюэкономических задач теории вероятностей и математической статистики.
Наряду с моделированиемэкономистам необходимо изучать теорию оптимизации, которая представленаматематическими методами исследования операций, в том числе линейнымпрограммированием.
Отмеченные направлениятребуют знания основополагающего математического аппарата: основ линейнойалгебры и математического анализа, теории вероятностей и математического программирования.
Таким образом, математикаи математическое образование нужны для подготовки к будущей профессии.
Один из классов математическихмоделей- задачи линейного программирования. Одной из задач линейногопрограммирования является транспортная задача- задача составления оптимальногоплана перевозок, позволяющего минимизировать суммарный километраж. Транспортнаязадача, как и задача линейного программирования была впервые поставленасоветским экономистом А.Н.Толстым в 1930 году. Разработка общих методов решениязадачи линейного программирования и их математическое исследование связано сименем советского ученого Л.В.Канторовича. В 1939 году методам решения задачилинейного программирования посвящено также большое число работ зарубежныхученых. Основной метод решения задачи линейного программирования –симплексметод- был опубликован в 1949 году Дандигом. Симплекс метод дает решение любойзадачи линейного программирования, но если переменных очень много, то решениевесьма затруднительно и для более сложных задач симплекс метод сталимодифицировать.
Транспортная задачаделится на два вида: транспортная задача по критерию стоимости- определениеплана перевозок, при котором стоимость груза была бы минимальна; транспортнаязадача по критерию времени- более важным является выигрыш по времени.
Транспортная задача покритерию стоимости является частным случаем задачи линейного программирования иможет быть решена симплексным методом. Однако в силу особенностей задачи, онарешается намного проще.
1. ОСНОВНАЯ ЧАСТЬ
1.1 МАТЕМАТИЧЕСКАЯПОСТАНОВКА ЗАДАЧИ
Транспортная задача-
Однородный грузсосредоточен у т поставщиков в объемах />.
Данный груз необходимодоставить п потребителям в объемах />.
Известны />(i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составитьтакой план перевозок, при котором запасы всех поставщиков вывозятся полностью,запросы всех потребителей удовлетворяются полностью и суммарные затраты наперевозку всех грузов минимальны.
Исходные данныетранспортной задачи записываются в таблице вида
Таблица 1
/>
/>
…
/>
/>
/>
/>
…
/>
/>
/>
/>
…
/>
…
…
…
…
…
/>
/>
/>
…
/>
Переменными(неизвестными)транспортной задачи являются />(i=1,…,m;i=1,2,…,n)- объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могутбыть записаны в матрице перевозок />
Математическая модельтранспортной задачи в общем случае имеет вид
/> (1.1)
/> i=1,2,…,m, (1.2)
/> j=1,2,…,n, (1.3)
/> i=1,2,…,m; j=1,2,…,n. (1.4)
Целевая функция задачи (1.1)выражает требования обеспечить минимум суммарных затрат на перевозку всехгрузов. Первая группа из т уравнений (1.2) описывает тот факт, чтозапасы всех т поставщиков вывозятся полностью. Вторая группа из n уравнений (1.3) выражает требованияполностью удовлетворить запросы всех n потребителей. Неравенства (1.4) являются условиями неотрицательностивсех переменных задачи.
Таким образом,математическая формулировка транспортной задачи состоит в следующем: найтипеременные задачи
/> i=1,2,…,m; j=1,2,…,n,
удовлетворяющее системеограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающееминимум целевой функции (1.1).
В рассмотренной моделитранспортной задачи предполагается, что суммарные запасы поставщиков равнысуммарным запросам потребителей, т.е.
/>.
Такая задача называетсязадачей с правильным балансом, а ее модель- закрытой. Если же это неравенствоне выполняется, то задача называется задачей с неправильным балансом, а еемодель- открытой.
Для того чтобытранспортная задача линейного программирования имела решение, необходимо идостаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросампотребителей, т.е. задача должна быть с правильным балансом.
Пример 1:
Составить математическуюмодель транспортной задачи перевоза груза из двух складов в 3 магазина:
Таблица 2
/>
/> 50 70 80 90 9 5 3 110 4 6 8
Решение. Введемпеременные задачи(матрицу перевозок)
/>
Запишем матрицустоимостей
/>.
Целевая функция задачиравна сумме произведений всех соответствующих элементов матриц С и Х:
/>
Данная функция,определяющая суммарные затраты на все перевозки, должна достигать минимальногозначения.
Составим системуограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы Х,должна равняться запасам первого поставщика, а сумма перевозок во второй строкематрицы Х – запасам второго поставщика:
/>
Это означает, что запасыпоставщиков вывозятся полностью.
Суммы перевозок, стоящихв каждом столбце матрицы Ч, должны быть равны запросам соответствующихпотребителей:
/>
Это означает, что запросыпотребителей удовлетворяются полностью.
Необходимо такжеучитывать, что перевозки не могут быть отрицательными:
/> i=1,2,…,m; j=1,1,…,n.
Ответ: математическаямодель задачи формулируется следующим образом: найти переменные задачи,обеспечивающие минимум функции
/>
и удовлетворяющие системеограничений
/>
и условиямнеотрицательности
/> i=1,2,…,m j=1,2,…,n.
1.2 АЛГОРИТМ РЕШЕНИЯТРАНСПОРТНОЙ ЗАДАЧИ
1.2.1 СБАЛАНСИРОВАННОСТЬТРАНСПОРТНОЙ ЗАДАЧИ
Транспортная задачаявляется сбалансированной, если суммарные запасы поставщиков равны суммарнымзапросам потребителей, т.е.
/>.
Если транспортная задачане сбалансирована, то возникают особенности в ее решении.
Особенности решениятранспортных задач с неправильным балансом:
1.Если суммарные запасыпоставщиков превосходят суммарные запросы потребителей, т.е.
/>
то необходимо ввестификтивного (n+1)-го потребителя с запросами /> равными разности суммарныхзапасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозокединиц груза />
2. Если суммарные запросыпотребителей превосходят суммарные запасы поставщиков, т.е.
/>
то необходимо ввестификтивного (m+1)-го поставщика с запасами /> равные разности суммарныхзапросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозокединиц груза />
3. При составленииначального опорного решения в последнюю очередь следует распределять запасыфиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотряна то, что им соответствует наименьшая стоимость перевозок, равная нулю.
1.2.2 ОПОРНОЕ РЕШЕНИЕТРАНСПОРТНОЙ ЗАДАЧИ
Опорным решениемтранспортной задачи называется любое допустимое решение, для которого векторыусловий, соответствующие положительным координатам, линейно независимы.
Ввиду того, что рангсистемы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметьотличных от нуля координат больше, чем N.
Для проверки линейнойнезависимости векторов условий, соответствующих координатам допустимогорешения, используют циклы.
Циклом называется такаяпоследовательность клеток таблицы транспортной задачи /> в которой две и толькососедние клетки расположены в одной строке или столбце, причем первая ипоследняя также находятся в одной строке или столбце.
Система векторов условий транспортнойзадачи линейно независима тогда и только тогда, когда из соответствующих им клетоктаблицы нельзя образовать ни одного цикла. Следовательно, допустимое решениетранспортной задачи />, i=1,2,…,m; j=1,2,…,n является опорным только в томслучае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.
Метод вычеркивания. Дляпроверки возможности образования цикла используется так называемый методвычеркивания, который состоит в следующем.
Если в строке или столбцетаблицы одна занятая клетка, то она не может входить в какой-либо цикл, так какцикл имеет две и только две клетки в каждом столбце. Следовательно, можновычеркнуть все строки таблицы, содержащие по одной занятой клетке, затемвычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться кстрокам и продолжить вычеркивание строк и столбцов. Если в результатевычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клетоктаблицы нельзя выделить часть, образующую цикл, и система соответствующихвекторов условий является линейно независимой, а решение опорным. Если же послевычеркиваний останется часть клеток, то эти клетки образуют цикл, системасоответствующих векторов условий линейно зависима, а решение не являетсяопорным.
Метод минимальнойстоимости. Данный метод позволяет построить опорное решение, которое достаточноблизко к оптимальному, так как использует матрицу стоимостей транспортнойзадачи />, i=1,2,…,m; j=1,2…,n. Данный метод состоит из ряда однотипных шагов, на каждом изкоторых заполняется только одна клетка таблицы, соответствующая минимальнойстоимости />, и исключается израссмотрения только одна строка(поставщик) или один столбец(потребитель).Очередную клетку, соответствующую />,заполняют также. Поставщик исключается из рассмотрения, если его запасызаканчиваются. Потребитель исключается из рассмотрения, если его запросыудовлетворены полностью. На каждом шаге исключается либо один поставщик, либоодин потребитель. При этом если поставщик не исключен, но его запасы равнынулю, то на том шаге, когда от него требуется поставить груз, в соответствующуюклетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения.Аналогично поступают с потребителем.
Пример 2:
Используя методминимальной стоимости, построить начальное опорное решение транспортной задачи,доставки лекарств из трех складов в четыре аптеки.
Таблица 3
/>
/> 80 120 160 120 120 1 3 4 2 160 4 5 8 3 200 2 3 6 7
Решение. Запишем отдельноматрицу стоимостей для того, чтобы удобнее было выбирать стоимости, вычеркиватьстроки и столбцы:
/>/>/>
1 4 6 3
среди элементов матрицыстоимостей выбираем наименьшую стоимость />.Это стоимость перевозки груза от первого поставщика первому потребителю. Всоответствующую клетку (1,1) записываем максимально возможную перевозку /> (табл 4). Запасы первогопоставщика уменьшаем на 80, />.Исключаем из рассмотрения первого потребителя, так как его запросыудовлетворены. В матрице С вычеркиваем первый столбец.
Таблица 4
/>
/> 80 120 160 120 120
1
80 3 4
2
40 160 4 5
8
80
3
80 200 2
3
120
6
80 7
В оставшейся матрицы Снаименьшей является стоимость />,максимально возможная перевозка, которую можно осуществить от первогопоставщика к четвертому потребителю, равна />.В соответствующую летку таблицы записываем перевозку />. Запасы первого поставщикаисчерпаны, исключаем его из рассмотрения. В матрице С вычеркиваем первуюстроку. Запросы четвертого потребителя уменьшаем на 40 />
В оставшейся частиматрицы С минимальная стоимость />.Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку (2,4)запишем />. Запросы четвертогопотребителя удовлетворены полностью, исключаем его из рассмотрения, вычеркиваемчетвертый столбец в матрице С. Уменьшаем запасы второго поставщика />
В оставшейся частиматрицы С минимальная стоимость />.Запишем в клетку таблицы (3,2) перевозку /> Исключаемиз рассмотрения второго потребителя, а из матрицы С второй столбец. Вычисляем />
В оставшейся частиматрицы С наименьшая стоимость /> Запишемв клетку таблицы (3,3) перевозку />Исключаемиз рассмотрения третьего поставщика, а из матрицы С третью строку. Определяем />.
В матрице С осталсяединственный элемент />. Записываем вклетку таблицы (2,3) перевозку />.
Проверяем правильностьпостроения опорного решения. Число занятых клеток таблицы равно N=m+n-1=3+4-1=6.Применяя метод вычеркивания, проверяем линейную независимость векторов условий,соответствующих положительным координатам решения. Порядок вычеркивания показанна матрице Х:
/>/>/>
1 2 5 6
Решение является«вычеркиваемым» и, следовательно, опорным.
Переход от опорногорешения к другому. В транспортной задаче переход от оного опорного решения кдругому осуществляется с помощью цикла. Для некоторой свободной клетки таблицыстроится цикл, содержащий часть клеток, занятых опорным решением. По этомуциклу перераспределяются объемы перевозок(осуществляется сдвиг по циклу).Перевозка «загружается» в выбранную свободную клетку и освобождается одна иззанятых клеток, получается новое опорное решение.
Если таблица транспортнойзадачи содержит опорное решение, то для любой свободной клетки таблицысуществует единственный цикл, содержащий эту клетку и часть клеток, занятыхопорным решением.
Для удобства вычисленийвершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-».Такой цикл называется означенным.
/>
Сдвигом по циклу навеличину /> называется увеличениеобъемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», иуменьшение объемов перевозок на ту же величину /> вовсех не четных клетках, отмеченных знаком «-».
1.2.3 МЕТОД ПОТЕНЦИАЛОВ
Широко распространеннымметодом решения транспортных задач является метод потенциалов.
Если допустимое решение />, i=1,2,…,m; j=1,2,…n транспортной задачи является оптимальным, то существуютпотенциалы (числа) поставщиков /> i=1,2,…,m и потребителей /> j=1,2,…,n, удовлетворяющее следующим образом:
/>
Группа равенств (2.1)используется как система уравнений для нахождения потенциалов. Данная системауравнений имеет m+n неизвестных /> i=1,2,…,m и /> j=1,2,…,n.Число уравнений системы, как и число отличных от нуля координат невырожденногоопорного решения, равно m+n-1. Так как число неизвестных системына единицу больше числа уравнений, то одной из них можно задать значениепроизвольно, а остальные найти из системы.
Группа неравенств (2.2)используется для проверки оптимальности опорного решения. Эти неравенстваудобнее представить в следующем виде:
/> (2.3)
Числа /> называются оценками для свободныхклеток таблицы (векторов условий) транспортной задачи.
Опорное решение являетсяоптимальным, если для всех векторов условий (клеток таблицы) оценкинеположительные.
Оценки для свободныхклеток транспортной таблицы используются при улучшении опорного решения. Дляэтого находят клетку (l,k) таблицы, соответствующую />. Если />, то решение оптимальное.Если же />, то для соответствующейклетки (l,k) строят цикл и улучшаю решение, перераспределяют груз
/>/> по этому циклу.
Алгоритм решениятранспортных задач методом потенциалов:
1. Проверитьвыполнение необходимого и достаточного условия разрешимости задачи. Если задачаимеет неправильный баланс, то вводится фиктивный поставщик или потребитель снедостающими запасами или запросами и нулевыми стоимостями перевозок.
2. Построитьначальное опорное решение (методом минимальной стоимости или каким-либо другимметодом), проверить правильность его построения по количеству занятых клеток(их должно быть m+n-1) и убедиться в линейнойнезависимости векторов условий (используется метод вычеркивания).
3. Построить системупотенциалов, соответствующих опорному решению. Для этого решают системууравнений:
/>
которая имеет бесконечноемножество решений. Для нахождения частного решения системы одному изпотенциалов (обычно тому, которому соответствует большее число занятых клеток)задают произвольно некоторое значение (чаще нуль). Остальные потенциалыоднозначно определяются по формулам:
/>
если известен потенциал />, и
/>
если известен потенциал />
4. Проверитьвыполнения условия оптимальности для свободных клеток таблицы. Для этоговычисляют оценки для всех свободных клеток по формулам
/>
и те из них, которыебольше нуля, записываются в левые нижние углы клеток. Если для всех свободныхклеток />, то вычисляют значениецелевой функции и решение задачи заканчивается, так как полученное решениеявляется оптимальным. Если же имеется хотя бы одна клетка с положительнойоценкой, опорное решение не является оптимальным.
5. Перейти к опорномурешению, на котором значение целевой функции будет меньше. Для этого находятклетку таблицы задачи, которой соответствует наибольшая положительная оценка
/>
Строят цикл, включающий всвой состав данную клетку и часть клеток, занятых опорным решением. В клеткахцикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке снаибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза)по циклу на величину />/>. Клетка со знаком «-», вкоторой достигается /> остается пустой.Если минимум достигается в нескольких клетках, то одна из них остается пустой,а в остальных проставляют базисные нули, чтобы число занятых клеток оставалосьравным />.
Далее перейти к пункту 3данного алгоритма.
1.2.4 МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
Согласно данному методузапасы очередного поставщика используются для обеспечения запросов очередныхпотребителей до тех пор, пока не будут исчерпаны полностью, после чегоиспользуется запасы следующего по номеру поставщика.
Заполнение таблицытранспортной задачи начинается с левого верхнего угла и состоит из рядаоднотипных шагов. На каждом шаге, исходя из запасов очередного поставщика изапросов очередного потребителя, заполняется только одна клетка исоответственно исключается из рассмотрения один поставщик или потребитель. Приэтом нулевые перевозки принято заносить в таблицу только в том случае, когдаони попадают в клетку (i,j), подлежащую заполнению, т.е. втаблицу заносятся только базисные нули />,остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок послепостроения начального опорного решения необходимо проверить, что число занятыхклеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейнонезависимы.
Необходимо иметь в виду,что метод северо-западного угла не учитывает стоимость перевозок, поэтому,опорное решение, построенное по данному методу, может быть далеким отоптимального.
Пример 3:
Составить опорное решениеметодом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5потребителей. данные записаны в таблице 6
Таблица 6
/> />
В1
50
В2
40
В3
30
В4
20
В5
10
А1
10
А2
20
А3
30
А4
40
А5
50
Решение:
Распределяем запасыпервого поставщика. Так как его запасы /> меньшезапросов первого потребителя />, то вклетку (1,1) записываем перевозку /> иисключаем из рассмотрения первого поставщика. Определяем оставшиесянеудовлетворенными запросы первого потребителя />.
Распределяем запасывторого поставщика. Так как его запасы />,меньше запросов первого потребителя />, тозаписываем в клетку (2,1) перевозку />/> и исключаем израссмотрения второго поставщика. Определяем оставшиеся неудовлетвореннымизапросы первого потребителя />.
Распределяем запасытретьего поставщика />. Так как егозапасы больше запросов первого потребителя />,то записываем в клетку (3,1) перевозку /> иисключаем из рассмотрения первого потребителя. Определяем оставшиесянеудовлетворенными запросы третьего поставщика />.
Распределяем запасытретьего поставщика />. Так как егозапасы меньше запросов второго потребителя />,то в клетку (3,2) записываем перевозку /> иисключаем из рассмотрения третьего поставщика. Определяем оставшиесянеудовлетворенными запросы второго потребителя />.
Распределяем запасычетвертого поставщика />. Так как егозапасы больше запросов второго потребителя />,то записываем в клетку (4,2) перевозку /> иисключаем из рассмотрения второго потребителя. Определяем оставшиесянеудовлетворенными запросы четвертого поставщика />.
Распределяем запасычетвертого поставщика />. Так как егозапасы меньше запросов третьего потребителя />,то в клетку (4,3) записываем перевозку /> иисключаем из рассмотрения четвертого поставщика. Определяем оставшиесянеудовлетворенными запросы третьего потребителя />.
Распределяем запасыпятого поставщика. Так как его запасы /> большезапросов третьего потребителя />, то вклетку (5,3) записываем перевозку /> иисключаем из рассмотрения третьего потребителя. Определяем оставшиесянеудовлетворенными запасы пятого поставщика/>.
Распределяем запасыпятого поставщика. Так как его запасы /> большезапросов четвертого потребителя />, то вклетку (5,4) записываем перевозку /> иисключаем из рассмотрения четвертого потребителя. Определяем оставшиесянеудовлетворенными запасы пятого поставщика/>.
Распределяем запасыпятого поставщика. Так как его запасы /> равнызапросам пятого потребителя />, то вклетку (5,5) записываем перевозку /> иисключаем из рассмотрения пятого поставщика и пятого потребителя.
Ввиду того, что задача справильным балансом, запасы всех поставщиков исчерпаны и запросы всехпотребителей удовлетворены.
Результаты построенияопорного решения приведены в таблице 7.
/> />
В1
50
В2
40
В3
30
В4
20
В5
10
А1
10 10 - - - -
А2
20 20 - - - -
А3
30 20 10 - - -
А4
40 - 30 10 - -
А5
50 - - 20 20 10
1.3 БЛОК-СХЕМА (АЛГОРИТМРЕШЕНИЯ)
/>
нет нет
да
/>
Метод
северо-
— западного
угла
метод
потенциалов
2. ФОРМЫ ВХОДНОЙИНФОРМАЦИИ
Входные данные вводятся склавиатуры
· Запасы i-го поставщика
· запросы j-го потребителя
В данном примере
· запасыпоставщиков(10; 20; 30; 40; 50)
· запросыпотребителей(50; 40; 30; 20; 10)
3. ФОРМЫ ВЫХОДНОЙИНФОРМАЦИИ
Информация выводится наэкран в виде таблицы с введенными данными и допустимый начальный базис
/> />
В1
50
В2
40
В3
30
В4
20
В5
10
А1
10 10 - - - -
А2
20 20 - - - -
А3
30 20 10 - - -
А4
40 - 30 10 - -
А5
50 - - 20 20 10
4. ИНСТРУКЦИЯ ДЛЯПОЛЬЗОВАТЕЛЯ
Общие сведения:
Программа производитвычисления допустимого начального базиса
Задача являетсясбалансированной. Поиск начального базиса происходит методом «северо-западногоугла»
Управление:
Данные вводятся склавиатуры:
Пользователь вводитзапасы i-го потребителя. После нажатияклавиши «0» пользователь вводит запросы j-го поставщика. Далее на экране после нажатия клавиши «Enter» появляется таблица с вводимымиданными и начальный базис.
5. ИНСТРУКЦИЯ ДЛЯПРОГРАММИСТА
Данная программареализуется с помощью процедурного языка Turbo Pascal 7.0, используется текстовый режим.
5.1 ТРЕБУЕМЫЕИНФОРМАЦИОННО–ВЫЧИСЛИТЕЛЬНЫЕ СРЕДСТВА:
1) техническоеобеспечение: IBM PC\XT совместимыемашины
а) оперативная память –не менее 8Мб
б) свободное место нажестком диске – не менее 60Кб
в) центральный процессор– от Intel 8088 до семейства Pentium или совместимых с ним
2) информационныесредства для нормального функционирования программы достаточно иметьинформационную систему MS DOS
5.2 ТИПЫ ПЕРЕМЕННЫХ,ИСПОЛЬЗОВАННЫХ В ПРОГРАММЕ:
const n=20 (строки)
m=20 (столбцы)
a:array [1..n] of integer; {массивзапасов}
b:array [1..m] of integer; {массивпотребностей}
a1:array[1..n] of integer; {вспомогательный массив запасов}
b1:array[1..m] of integer; {вспомогательный массив потребностей}
c:array[1..n,1..m] of integer; {основной массив в который производится записьбазисного решения}
i,j,k,x,y,s1,s2:integer;
5.3 ПРОЦЕДУРЫ
procedure vvod_klav;(вводданных с клавиатуры)
begin
i:=1;
k:=0;
s1:=0;
while (k=0) and (i
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
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
begin
writeln('ошибка ввода,проверьте баланс');
readln;
halt;
end;
if (s2
begin
writeln('ошибка ввода,проверьте баланс');
readln;
halt; end;
x:=i;
y:=j;
end;
ЗАКЛЮЧЕНИЕ
Мне была поставленазадача составить программу для расчета начального базиса сбалансированнойтранспортной задачи, где суммарные запасы поставщиков равны суммарным запросампотребителей.
Программа реализована наязыке программирования Паскаль.
Все вводимые данные иначальный базис выводятся в виде таблицы.
В программе удобный ипонятный пользовательский интерфейс. Для ввода данных используется клавиатура.Данные, выводимые программой, соответствуют тем, что получены при расчетах безиспользования компьютера. Таким образом, поставленная задача была выполнена.
СПИСОК ИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1 Общий курс высшейматематики для экономистов. Учебник / под ред В.И. Ермакова.- М.: ИНФА – М. –656 с. – (серия «высшее образование»).
2 Сборник задач иупражнений по высшей математике: математическое программирование: учебникпособие / А.В. Кузнецов, В.А. Сакович, Н.И. Холод и др; МН.: выш. ик., 2002. –447с.: ил.
3 Т.Л. Партыкина, И.И.Попов Математические методы: учебник. – М.: ФОРУМ: ИНФА-М, 2005. – 464 с.: ил –(профессиональное образование)
4. И.Г. Семакин Основыпрограммирования: учебник для сред. проф. Образования / И.Г. Семакин,А.П.Шестаков. – 2-е изд., стер,- М.: Издательский центр «Академия», 2003.-432с.
5 Федосеев В.В. и др.Экономико-математические методы и прикладные модели: учебное пособие для ВУЗов.- М.: Юнити, 2002.
6 Коршунов Ю.М.математические основы кибернетики: учебное пособие для ВУЗов. – М.:Энергоатомиздат, 1987.
ПРИЛОЖЕНИЕА
Листингпрограммы
program sev_zap;
uses crt;{подключение модуля «crt»}
constn=5; {количество строк}
m=5;{количество столбцов}
var a:array [1..n] of integer; {массивзапасов}
b:array [1..m] of integer; {массивпотребностей}
a1:array [1..n] of integer; {вспомогательныймассив запасов}
b1:array[1..m] of integer; {вспомогательный массив потребностей}
c:array[1..n,1..m] of integer; {основной массив в который производится записьбазисного решения}
i,j,k,x,y,s1,s2:integer;
{ввод склавиатуры}
procedure vvod_klav;
begin
i:=1;
k:=0;
s1:=0;
while (k=0) and (i
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
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
begin
writeln('ошибка ввода,проверьте баланс');
readln;
halt;
end;
if (s2
begin
writeln('ошибка ввода,проверьте баланс');
readln;
halt;
end;
x:=i;
y:=j;
end;
begin
textcolor(white);
clrscr; {очистка экрана}
writeln(‘Построение начальногобазиса в сбалансированной транспортной задаче методом северо-западного угла’);
writeln;
writeln(‘Программу составил:Руднев Егор Николаевич’);
writeln;
vvod_klav;{процедура ввода с клавиатуры}
repeat
k:=0;
if (b[j]-a[i]
begin
c[i,j]:=b[j];
a[i]:=a[i]-b[j];
b[j]:=0;
j:=j-1;
k:=1;
end;
if (b[j]-a[i]>0) and (k=0) then
begin
c[i,j]:=a[i];
b[j]:=b[j]-a[i];
a[i]:=0;
i:=i-1;
k:=1;
end;
if (b[j]-a[i]=0) and (k=0) then
begin
c[i,j]:=a[i];
a[i]:=0;
b[j]:=0;
i:=i-1;
j:=j-1;
end;
if (i=0) or (j=0) then break;
untilfalse;
{выводна экран базисного решения}
clrscr;
textcolor(white);
for i:=1 to x do
begin
for j:=1 to y do
if j=y then write(c[i,j]:6,' │ ',a1[i])
else
write(c[i,j]:6);
writeln;
end;
write(' ');
for i:=1 to y*6-4 do
write(#196);
writeln('┘');
for j:=1 to y do
write(b1[j]:6);
readln;
end.