Исследование и характеристика особенностей транспортной задачи, которая является частным случаем задачи линейного программирования. Ознакомление с математической моделью транспортной задачи. Рассмотрение преимуществ метода северо-западного угла.
Аннотация к работе
В данной дипломной работе рассматривается применение метода потенциалов для решения транспортной задачи с неправильным балансом. Составлена программа на языке Delphi, реализующая метод потенциалов. Линейная программирования развивалось в первую очередь в связи с задачами экономики, с поиском способов оптимального распределения и использования ограниченных ресурсов. Линейное программирование - целевая функция линейна, а множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера.Под моделью будем понимать условный образ какого-либо объекта, приближенно воссоздающий этот объект с помощью некоторого языка. Использование математического моделирования в экономике позволяет углубить количественный анализ. Можно выделить три основных этапа проведения экономико-математического моделирования. На втором этапе формируется математическая модель изучаемого объекта, осуществляется выбор (или разработка) методов исследования, проводится программирование модели на ЭВМ, подготавливается исходная информация. На третьем, основном, этапе экономико-математического моделирование осуществляется анализ математического модели, реализованной в виде программ для ЭВМ, проведение машинных расчетов, обработка и анализ полученных результатов.Запас ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таб. Итак, экономико-математическая модель задачи: найти такой план выпуска продукции X=(х1, x2), удовлетворяющий системе (1), и условию (2), при котором функция (3) принимает максимальное значение. Обозначим - число единиц продукции , запланированной к производству; - запас ресурса , - число единиц ресурса затрачиваемого на изготовление единицы продукции (числа часто называют технологическими коэффициентами);-прибыль от реализации единицы продукции . Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план выпуска продукции, удовлетворяющий системе Для формулировки задачи в общей постановке обозначим - число единиц корма n-го вида; - необходимый минимум содержание в рационе питательного вещества - число единиц питательного вещества в единицы корма j-го вида; - стоимость единицы корма j-го вида.Система (20) называется системой ограничений, а функция - линейной функцией, линейной формой, целевой функцией или функцией цели. Более кратко общую задачу линейного программирования можно представить в виде: При ограничениях: Оптимальное решение (или оптимальным планом) задачи линейного программирования называется решение система ограничений (20), удовлетворяющее условию (22), при котором линейная функция (21) принимает оптимальное (максимальное или минимальное) значение. При условии, что все переменные неотрицательны , система ограничений (20) состоит лишь из одних неравенств, - такая задача линейного программирования называется стандартной; если система ограничений состоит из одних уравнений, то задача называется канонической. Таким образом, стандартная задача (4) - (6) в канонической форме: найти такое решение , удовлетворяющее системе (26) и условию (5), пи котором функция (6) принимает максимальное значение. В первом случае, временно исключают из рассмотрения столбец, содержащий заполненную на данном шаге клетку, и рассматривают задачу, таблица условий которой, содержит на один столбец меньше, чем было перед этим шагом, но то же количество строк и соответственно измененные запасы груза в одном из пунктов отправления (в том, за счет запаса которого была удовлетворена потребность в грузе пункта назначения на данном шаге).При нахождении опорного плана транспортной задачи методом севера - западного угла на каждом шаге рассматривает первый из оставшихся пунктов отправления их первый из оставшихся пунктов назначения. Заполнения таблицы клеток условий начинается с левой верхней клетки для неизвестного («севера - западного угла») и заканчивается клеткой для неизвестного , идет как бы по диагонали таблицы. Этот груз требуется перевести в пять пунктов назначения 60, 70, 120, 130, и 100 ед. тарифы перевозок единицы груза каждого из пунктов отправления в соответствующие пункты назначения указаны в следующей таблице: Пункты отправления Пункты назначения запасы Заполнения таблицы начнем с клетки для неизвестного , т.е. попытаемся, удовлетворит потребности первого пункта назначения за счет запасов первого пункта отправления. Рассмотрим первый из оставшихся пунктов отправления и назначения , запасы пункта больше потребности пункта , положим , запишем этот значения в соответствующей клетке таблице и временно исключим из рассмотрения столбец .